Bibtex

@InCollection{,
  Year    = "2019", 
  Title    = "Tourenplanung", 
  Author    = "", 
  Booktitle    = "Gronau, Norbert ; Becker, Jörg ; Kliewer, Natalia ; Leimeister, Jan Marco ; Overhage, Sven (Herausgeber): Enzyklopädie der Wirtschaftsinformatik – Online-Lexikon",
  Publisher    = "Berlin : GITO",
  Url    = "https://wi-lex.de/index.php/lexikon/technologische-und-methodische-grundlagen/tourenplanung/", 
  Note    = "[Online; Stand 4. February 2023]",
}

Tourenplanung

Hier weiterverbreiten

Während für die effiziente Distribution von Gütern unter Einhaltung von Kundenzeitfenstern zahlreiche heuristische Verfahren exisitieren, gehören Berücksichtung von tageszeitabhängigen oder stochastischen Fahrzeiten, Ausnutzung von Umladungs- oder dynamischen Umplanungsmöglichkeiten sowie Gestaltung effizienter Marktmechnismen für die dezentrale Planung zu den aktuellen Herausforderungen. t

Als Grundproblem der Tourenplanung zählt das Traveling Salesman Problem (TSP) des Auffindens

eines kürzesten Hamiltonischen Zyklus in einem bewerteten Graphen – also der

kürzesten Rundreise – seit langem zu den meistuntersuchten diskreten

Optimierungsproblemen [Lawler et al. 1985]. Trotz NP-Vollständig­keit erlauben

Schnittebenen-Verfahren heute die optimale Lösung von Probleminstanzen mit

mehreren tausend Knoten.

Wichtige Generalisierungen und zusätzliche Nebenbedingungen

Sobald jedoch mehrere Fahrzeuge und zusätz­liche

Nebenbedingungen wie z.B. Fahrzeugkapazitäten in Vehicle-Routing-Problemen

(VRP) zu berücksichtigen sind, muss auf heuristische Verfahren ausgewichen

werden. Naturanaloge Meta­heuristiken wie Simulated Annealing, Genetische

Algorithmen, aber auch Tabu Search sowie Hybridverfahren unter Einbeziehung von

Constraint Propagation, kommen hier­bei zur Anwendung [vgl. z.B. Pisinger/Ropke 2007].

Gleiches gilt für die Generalisierung des VRP zum Pickup-and-Delivery-Problem

(PDP), in welchem die Beladung der Fahrzeuge nicht nur in einem oder mehreren

dedizierten Depots stattfindet, sondern Aufträge prinzipiell von jedem

Netzwerkknoten (Origin) zu jedem anderen Netzwerkknoten (Destination) zulässig

sind.

Praxisrelevant sind insbesondere die Erweiterungen des VRP oder

PDP um Zeitfenster, die bei Origin und

Destination eingehalten werden müssen und entweder als harte Nebenbedingungen

modelliert oder bei Verfehlung über Strafkosten in die Zielfunktion einbezogen

werden. [vgl. z.B. Soumis et al. 1998]

Stochastische, dynamische und dezentrale Tourenplanung

Während das VRP auch mit stochastischer

Kunden­nachfrage bereits häufiger untersucht wurde [Gendreau et al. 1996], finden tageszeitabhängige und/oder stochastische Fahrzeiten

in der Tourenplanung erst in jüngerer Zeit nennenswerte Beachtung [vgl. Kenyon/Morton 2003], Hierbei wird meist eine

strikte Trennung von Planungszeitraum und Ausfüh­rungs­zeitraum des Plans unterstellt, was

mit zunehmender Verfügbarkeit mobiler IT immer weniger begründet werden kann,

sondern durch Möglichkeiten der Planung und Umplanung während der Ausführung

ergänzt werden muss.

Selten behandelt wurde bisher

das Problem der Transshipments, also die Beförderung

einzelner Aufträge mittels mehrerer Fahrzeuge mit Umladung [vgl. Mitrovic-Minic/Laporte 2006], wenngleich die Verwendung

von Distributionszentren in der Praxis fast den Regelfall darstellt.

Unterstellt man im Gegensatz zu den bisherigen Ausführungen keine

zentrale Planungsinstanz, sondern versteht die Annahme oder den Austausch von

Beförderungsaufträgen zwischen einzelnen Touren als marktlichen Prozess, so

zeigt sich schnell, dass sich die Komplexität des Problems nun in der

Schwierigkeit der Berechnung adäquater Gebots-Preise widerspiegelt: Die

Verbundeffekte erfordern kombinatorische Auktionen zur Lösung des Problems

einer pareto-optimalen Allokation, wie folgende Abbildung andeutet.

Tourenplanung.jpg

Abb. 1:

Komplementaritäten beim Austausch von Lieferaufträgen

Besteht z.B. eine

Kapazitätsgrenze oder Kundenzeitfenster, so kann der simultane Tausch von

Auftragscluster C1 und C2 zwischen den beiden Touren ggf. zu Einsparungen führen,

die durch sukzessive „Veräußerung“ einzelner Aufträge nicht realisierbar wären.

Wie diese Einsparungen anreizkompatibel unter den Marktteilnehmern aufgeteilt

werden können, stellt eine wesentliche Herausforderung für das sog. Mechnism

Design dar [vgl. Krajewska/Kopfer 2006].


Literatur

Gendreau,r Michel ; Laporte, Gilbert ; Seguin,r Rene: Stochastic vehicle routing. In: European Journal of Operational Researchr (1996), S. 3-12.

Kenyon,r Astrid S. ; Morton, David P.: Stochastic Vehicle Routing with Random Travelr Times. In: Transportation Science 37 (2003), Nr. 1, S. 69-82.

Krajewska,r Marta Anna ; Kopfer, Herbert: Collaborating freight forwarding enterprises. In:r OR Spectrum 28 (2006), Nr. 3, S. 301-436.

Lawler,r E.L. ; Lenstra, J.K. ; Rinnooy Kan, A.H.G. ; Shmoys, D.B. ; eds.: The travelingr salesman problem. A guided tour of combinatorial optimization. (Hrsg.): Wiley-Interscience series inr discrete mathematics. John Wiley & Sons (1985).

Mitrovic-Minic, Snezana ; Laporte, Gilbertr : The pickup and delivery problem with time windows and transshipment. INFOR 44 (2006), S.r 217-227.

Pisinger,r David ; Ropke, Stefan: A general heuristic for vehicle routing problems. In:r Computers & Operations Research 34 (2007), S. 2403-2435.

Soumis,r Francois ; Lavigne, June ; Desaulniers, Guy: Multi-depot vehicle schedulingr problems with time windows and waiting costs. In: European Journal ofr Operational Research 111 (1998), S. 479-494

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert