Tourenplanung

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.
 

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, Michel ; Laporte, Gilbert ; Seguin, Rene: Stochastic vehicle routing. In: European Journal of Operational Research (1996), S. 3-12.

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

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

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

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

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

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

Autor