Tourenplanung: Hintergründe und Wissenswertes

• Einführung
• Das Problem des Handlungsreisenden
• Das Standardproblem der Tourenplanung
• Chinesische Briefträger und Königsberger Brücken

Einführung

Mit der Tourenplanung, also der Zusammenfassung von Transportaufträgen zu Touren, beschäftigen sich Menschen wahrscheinlich schon seit Jahrtausenden. Heute gilt es dabei, Personal, Fahrzeuge, Schiffe, Flugzeuge usw. möglichst ökonomisch einzusetzen, beispielsweise indem man die zurückgelegte Strecke oder die Fahrzeit minimiert.

Tourenplanungsprobleme findet man u. a. in der Einsammlung und Zustellung von Waren, Post und Zeitungen, beim Transport von Gütern, beim Einsatz von Servicepersonal für Reparaturen, Instandhaltung und Wartung oder bei speziellen Dienstleistungen wie etwa der Schneeräumung.

Die verstärkte wissenschaftliche Auseinandersetzung mit derartigen Problemstellungen begann in den 1950er Jahren durch die Disziplin des Operations Research. Damals wurden stark idealisierte mathematische Modelle formuliert und darauf aufbauende Optimierungsverfahren entwickelt. Zwischen den Anforderungen der Praxis mit ihren vielfältigen Restriktionen und den damals entwickelten Modellen und Methoden klaffte eine große Lücke. Ebenso war man nicht in der Lage, reale Problemstellungen mit hunderten oder gar tausenden Transportaufträgen zu lösen.

Damals war also an eine computergestützte Tourenplanung nicht zu denken. In den vergangenen etwa fünfzig Jahren sind jedoch in vielen für die Tourenplanung wichtigen Bereichen große Fortschritte erzielt worden:

• Dramatischer Anstieg der Computerleistung und Durchdringung des Geschäftslebens durch Computer
• Flexibilisierung der mathematischen Modelle zur Berücksichtigung vieler praxisrelevanter Anforderungen
• Starke Verbesserung der Lösungsverfahren
• Verfügbarkeit von Stamm- und Bewegungsdaten in Datenbanken und ERP-Systemen (z. B. SAP und Oracle)
• Verfügbarkeit von Geografischen Informationssystemen und elektronischen Landkarten zur Berechnung von Fahrzeiten, -strecken und Maut

In der Praxis werden jedoch weiterhin die meisten Tourenplanungsprobleme so gelöst wie vor fünfzig Jahren: von Hand. Meistens wird zwar dazu ein Computer und ein Tabellenkalkulationsprogramm wie z. B. MS Excel verwendet, aber kein dediziertes Tourenplanungsprogramm. Diese manuelle Art der Planung hat jedoch mehrere entscheidende Nachteile:

• Sie ist ineffizient, da der Planungsprozess sehr lange dauert.
• Sie ist fehleranfällig, da man die Zulässigkeit der erstellten Pläne nicht adäquat überprüfen kann.
• Sie ist unwirtschaftlich, da ein Mensch als Planer fast nie in der Lage ist, eine Menge von Transportaufträgen optimal auf Touren zu verplanen. (Versuchen Sie einmal, nur zwanzig in der Ebene verteilte Punkte so zu einer Tour zu verbinden, dass die zurückgelegte Strecke minimal wird!)
• Sie ist nicht kontrollierbar, da die Ergebnisse nicht mit vertretbarem Aufwand erfasst und weiterverarbeitet werden können.

Deshalb gehen immer mehr Unternehmen dazu über, Softwaresysteme für die Tourenplanung einzuführen. Solche Systeme unterstützen nicht nur den reinen Planungsprozess, sondern den gesamten Workflow von der Auftragserfassung bis hin zur Beauftragung des Personals, zur Ist-Daten-Erfassung und der abschließenden Analyse und dem Controlling.

Im Folgenden haben wir einige Informationen über klassische Probleme der Tourenplanung zusammengestellt. Der Fokus liegt dabei auf der wissenschaftlichen Auseinandersetzung mit diesen Problemen.

nach oben

Das Problem des Handlungsreisenden oder Travelling-Salesman-Problem

Der folgende Text ist weitgehend aus dem Buch: Optimierung im Transport II: Wege und Touren (Grünert und Irnich, 2005) entnommen.

Das Problem des Handlungsreisenden, Rundreiseproblem oder Travelling-Salesman-Problem (TSP) ist das am meisten untersuchte kombinatorische Optimierungsproblem überhaupt. Das liegt wohl daran, dass das TSP leicht zu formulieren und schwer zu lösen ist: Ein Handlungsreisender befindet sich an einem Ort und möchte weitere Orte aufsuchen. Die Abstände zwischen den Orten werden als bekannt vorausgesetzt. Das TSP stellt nun die Frage, in welcher Reihenfolge die Orte besucht werden sollten, so dass der Handlungsreisende alle Orte genau einmal besucht, zum Ursprungsort zurückkehrt und dabei die kürzestmögliche Strecke zurücklegt.

Heute ist man in der Lage, große TSP (mit mehreren tausend Städten) exakt optimal zu lösen, benötigt dafür aber sehr aufwändige mathematische Optimierungsverfahren und teilweise starke parallele Rechnerpools. Fügt man jedoch weitere praxisrelevante Restriktionen zu diesem Problem hinzu, wie z. B. Zeitfenster, innerhalb derer der Handlungsreisende eine Stadt besuchen muss, so zeigt sich, dass bereits Problemstellungen mit 100 Städten nicht mehr exakt gelöst werden können. Deshalb verwendet man in der Praxis sog. Heuristiken und Metaheuristiken, die mit vertretbarem Aufwand eine möglichst gute Lösung berechnen. Selbstverständlich hängt dann die Qualität der gefundenen Lösung und die notwendige Rechenzeit von der Qualität der eingesetzten Heuristik ab.

Der Ursprung des TSP und seine Bezeichnung als Problem des Handlungsreisenden ist historisch ungeklärt. Die erste Erwähnung des TSP geht wahrscheinlich auf ein Buch von B. F. Voigt zurück, das 1832 mit dem Titel "Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften sicher zu sein." In diesem Buch wird tatsächlich das Problem der Wahl einer optimalen Rundreise beschrieben, ohne dass Lösungen dafür angeboten werden.

In den dreißiger Jahren des vorigen Jahrhunderts beschäftigte sich auch Menger mit einem ähnlichen Problem und stellte fest, dass die Nächster-Nachbar-Heuristik nicht zur optimalen Lösung führt. Einen wesentlichen wissenschaftlichen Beitrag zur Lösung des TSP lieferte die Arbeit jedoch nicht.

Die Untersuchung des TSP mit Hilfe von formalen mathematischen Methoden geht auf die Arbeit von Dantzig, Fulkerson und Johnson aus dem Jahre 1954 zurück. Sie versuchten, das TSP mit Hilfe der linearen Programmierung durch Hinzufügen von gültigen Ungleichungen zu lösen. Mit diesem Ansatz konnte das Optimum eines 42-Städte-TSP berechnet werden.

Die erste publizierte Heuristik für das TSP stammt von Flood aus dem Jahre 1956. Er schlug ein Kantenaustauschverfahren vor, das eine gegebene Tour verbessert, indem man zwei Verbindungen (Kanten) entfernt und durch zwei andere Verbindungen ersetzt. Im Jahre 1963 wurde zum ersten Mal die Terminologie Branch-and-Bound in einer Veröffentlichung von Little et al. verwendet. Allerdings waren Branch-and-Bound-Verfahren schon 1958 von Croes und Eastman vorgeschlagen worden. Die Anwendung der Lagrange-Relaxation zur Lösung von kombinatorischen Problemen geht auf die Arbeit von Held und Karp aus dem Jahre 1970 zurück. 1973 wurde die bisher erfolgreichste Heuristik für das TSP entwickelt, das variable Kantenaustauschverfahren von Lin und Kernighan. Damit konnte man gute Lösungen für Probleme mit mehreren hundert Städten finden.

Anfang der siebziger Jahre begannen Padberg und Grötschel die systematische Untersuchung der LP-basierten Methoden, die von Dantzig et al. 1954 zuerst vorgeschlagen worden waren. Die Idee war es, das Polyeder, das durch die zulässigen Lösungen des TSP aufgespannt wird, mit Hilfe von linearen Ungleichungen zu beschreiben. Dies führte zur Entwicklung der problemspezifischen Schnittebenen-Verfahren und schließlich zum sog. Branch-and-Cut in den achtziger Jahren.

Die Kombination von guten Heuristiken (Weiterentwicklungen des Lin-Kernighan-Verfahrens) mit Branch-and-Cut hat dazu geführt, dass man heute TSP in der Größenordnung bis zu einer Million Städten exakt oder nahezu exakt lösen kann. Dazu waren eine Reihe von komplexen Datenstrukturen und ein Netzwerk von parallelen Workstations mit Rechenzeiten von mehreren CPU-Jahren nötig. Die Lösung dieser großen Instanzen ist eher von akademischem Interesse, wenn man bedenkt, dass gute Heuristiken mit viel geringerem Aufwand Lösungen finden, die i. d. R. nur wenige Prozent vom Optimum abweichen.

nach oben

Das Standardproblem der Tourenplanung oder Vehicle-Routing-Problem

Der folgende Text ist weitgehend aus dem Buch: Optimierung im Transport III: Routing und Scheduling (Grünert und Irnich, erscheint 2008) entnommen.

Das Vehicle-Routing-Problem gilt als das Grundproblem der Tourenplanung. Identische Fahrzeuge mit einer bekannten Kapazität sind an einem Depot stationiert. Ihre Aufgabe ist es, unterschiedliche Mengen von Fracht, die bei verschiedenen Kunden lagern, abzuholen und zum Depot zu bringen. Zielsetzung ist dabei meistens, die zurückgelegte Strecke oder die Anzahl Fahrzeuge zu minimieren, wobei jeder Kunde nur einmal besucht werden darf. Dabei gilt es, die Kapazität der Fahrzeuge einzuhalten und in manchen Fällen auch, die Tourlänge einen Maximalwert nicht überschreiten zu lassen.

Die Struktur des VRP bewirkt, dass simultan entschieden werden muss,

• welches Fahrzeug welche Kunden bedient (Clusterung) und
• in welcher Reihenfolge die Kunden von den einzelnen Fahrzeugen bedient werden (Routing).

Dabei entspricht das Problem des Routings einem TSP für jedes Kundencluster. Vernachlässigt man andererseits die Routing-Komponente des Problems und fragt nach der minimalen Anzahl an Touren, so entsteht ein Bin-Packing-Problem (BPP). In diesem BPP entspricht der Bedarf eines Kunden einem Gegenstand, und ein Fahrzeug mit seiner Kapazität wird als Behälter mit entsprechender Kapazität modelliert. Die optimale Lösung des BPP gibt die minimale Anzahl Touren an, die eine Lösung des VRP aufweisen kann.

Die Ähnlichkeit zwischen dem VRP und dem TSP hat dazu geführt, dass die Lösungsansätze sich zum Teil ähneln. Das VRP ist jedoch aufgrund der Cluster-Problematik ein schwieriger zu lösendes Optimierungsproblem als das TSP. So können heute durchaus TSP mit mehreren tausend Städten exakt optimal gelöst werden, während die Grenze beim VRP bei etwa 30 bis 100 Kunden liegt.

Als Geburtsstunde dieser Teildisziplin des Operations Research gilt eine Veröffentlichung von Dantzig und Ramser aus dem Jahre 1959, die erstmals eine quantitative Untersuchung des VRP vornahm. In den sechziger Jahren wurden weitere wichtige Beiträge zur Modellierung und Lösung des VRP geleistet. Als Meilensteine sollen die Modellierung des VRP als Set-Partitioning-Modell in der Arbeit von Balinski und Quandt (1964) und die Veröffentlichung des Savings-Verfahrens durch Clarke & Wright (1964) genannt werden.

Eine Vielzahl von weiteren Modellen und Algorithmen wurden in den siebziger Jahren entwickelt, vgl. beispielsweise das Sweep-Verfahren von Gillett und Miller (1974), die Arbeiten von Golden et al. (1977) und Russell (1977) zur effizienten Implementierung von Heuristiken sowie die ersten erfolgversprechenden Ansätze von Christofides et al. (1979) zur exakten Optimierung. Ferner begann man mit der Untersuchung von Erweiterungen des VRP, z. B. auf den mehrperiodigen Fall und auf kombinierte Standort-Routing-Probleme.

In den achtziger Jahren begann eine nahezu explosionsartige Entwicklung des Bereichs der Touren- und Routenplanung. Für die knotenorientierten Probleme wurden neue heuristische Verfahren entwickelt, wie die bekannte Generalized-Assignment-Heuristik von Fisher und Jaikumar (1981). Ebenso begann man sich intensiv mit der Tourenplanung mit Zeitfenstern zu beschäftigen. Weiterhin begann in den achtziger Jahren die Untersuchung von verschiedenen Varianten des VRP, beispielsweise mit heterogenem Fuhrpark, Rückladungen, mehrfachen Depots und mehrfachen Perioden.

Ende der achtziger Jahre begann auch die Auseinandersetzung mit Metaheuristiken wie Tabu-Search, Simulated-Annealing und evolutionären Algorithmen für die Tourenplanung, die ersten wirklich guten Resultate wurden jedoch erst in den neunziger Jahren bzw. zum Beginn des neuen Jahrtausends veröffentlicht.

Die Entwicklung immer besserer Metaheuristiken für das VRP und seine Varianten stand im Vordergrund der Forschung in den neunziger Jahren. Andererseits wurden große Fortschritte bei der exakten Optimierung mittels der Technik des Column-Generation gemacht. Auch die Fortentwicklung klassischer Branch-and-Bound-Verfahren machte deutliche Fortschritte. Hier sind vor allem die Methoden der Lagrange-Relaxation, des Additive-Bounding und der Zustandsraum-Relaxation zu nennen.

nach oben

Chinesische Briefträger und Königsberger Brücken

Der folgende Text ist teilweise aus dem Buch: Optimierung im Transport II: Wege und Touren (Grünert und Irnich, 2005) entnommen.

Kantenorientierte Routing-Probleme werden in der deutschsprachigen Literatur häufig Briefträgerprobleme genannt. Diese intuitive Bezeichnung beschreibt folgende Aufgabenstellung: Ein Briefträger muss beim Zustellen von Briefen alle oder bestimmte Straßen seines Bezirks mindestens einmal durchlaufen. Gesucht ist ein entfernungsminimaler Rundweg.

Dies ist die Sicht auf das Problem als Minimierung des gesamten Rundwegs. Hält man sich vor Augen, dass diejenigen Straßen, welche mehr als einmal durchlaufen werden, Umwege darstellen, so ist das Problem äquivalent zur Frage nach dem minimalen Umweg oder der Minimierung der unproduktiven Strecken des Briefträgers.

Hinter den Begriffen der kantenorientierten Routing-Probleme (engl.: arc routing problems, ARP) oder Briefträgerprobleme (engl.: postman problems) verbergen sich im Operations Research eine große Klasse von Routing-Problemen. In dem zur Modellierung des realen Problems verwendeten Graphen müssen entweder alle oder nur bestimmte Kanten und Bögen durchlaufen werden. Im Gegensatz zum TSP oder VRP, bei denen die Nachfrage in den Knoten - also Kunden oder Städten - entsteht, tritt hier die Nachfrage an den Kanten bzw. Bögen auf. Den Kanten und Bögen entsprechen die zu bedienenden Straßenabschnitte, welche zwischen den Knoten, d. h. den Kreuzungspunkten der Straßenabschnitte, verlaufen.

Das berühmte Königsberger Brückenproblem, 1736 von Leonard Euler formuliert und (teilweise) beantwortet, lässt sich folgendermaßen in die heutige Sprache der Graphentheorie übertragen: Die Abbildung zeigt schematisch eine Ansicht auf Königsberg und die sieben Brücken über den Pregel. Euler stellte die Frage, ob es einen Rundweg oder überhaupt einen Weg durch Königsberg gibt, welcher alle sieben Brücken genau einmal überquert.

Um dieses Problem zu lösen, kann man aus der Kartenansicht einen Graphen bauen. Jedes Landstück, welches durch den Fluss Pregel begrenzt ist, wird durch einen Knoten modelliert. Brücken verbinden diese Landstücke und entsprechen den Kanten des Graphen. Ein Rundweg ist eine geschlossene Kantenfolge in diesem Graphen. Euler stellte fest, dass es folgende Bedingung für die Lösbarkeit des Problems gibt: Jeder Knoten muss mit einer geraden Anzahl an anderen Knoten (durch Kanten) verbunden sein. Dass diese Bedingung notwendig ist, erkennt man schnell. Denn in einem Rundweg wird ein Knoten bei jedem Besuch genau einmal erreicht und anschließend wieder verlassen. Er konnte allerdings nicht beweisen, dass diese Bedingung auch hinreichend ist, was aber Hierholzer 1873 gelang. Untersucht man die Abbildung von Königsberg als Graphen, so sieht man, dass es keinen Rundweg gibt, denn jeder Knoten ist mit genau drei oder fünf anderen Knoten verbunden.

Eine Erweiterung bzw. Verallgemeinerung der von Euler formulierten Frage ist diejenige nach einer kostenminimalen Rundtour in einem nicht-Eulerschen Graphen. Dies ist genau die Frage, die sich ein Briefträger auf seiner Zustellroute stellt: Wie kann ich alle Straßen meines Bezirks ablaufen, sodass der Umweg (also die Straßenabschnitte, die mehrmals durchlaufen werden müssen) minimal wird?

Der chinesische Mathematiker M. Guan (bzw. Kwan Mei-Ko) hat sich als erster mit diesem Typ von Optimierungsproblemen auseinandergesetzt. Der Begriff "Chinese-Postman-Problem" ist auf seine Arbeiten zurückzuführen. Auch dieses Problem lässt sich relativ leicht lösen, indem man den nicht-Eulerschen Graphen um zusätzliche Kanten so erweitert, dass der Umweg minimal wird. Dabei handelt es sich um ein sog. Minimalkosten-Matchingproblem, für dessen Lösung es eine Reihe von effizienten Optimierungsalgorithmen gibt. Erweitert man jedoch die kantenorientierten Probleme um weitere realitätsnahe Restriktionen (z. B. Einbahnstraßen, Bezirke, die nicht bedient werden müssen, mehrere Briefträger), so können die entstehenden Optimierungsprobleme i. d. R. nur noch mit Heuristiken gelöst werden.

nach oben