Wenn heute jemand eine Tourenplanungssoftware kauft, kauft er das Ergebnis einer Forschungslinie, die 1959 begonnen hat. Ihr Gründungsdokument ist ein zwölfseitiger Aufsatz über die Belieferung von Tankstellen. Er lohnt sich zu lesen – nicht aus historischem Interesse, sondern weil erstaunlich viel von dem, was Disponenten heute beschäftigt, schon darin steht.
Ein Aufsatz über Tankwagen
George Dantzig und John Ramser veröffentlichten 1959 in Management Science einen Artikel mit dem nüchternen Titel „The Truck Dispatching Problem". Im Abstract steht der Satz, an dem sich das ganze Feld später abgearbeitet hat:
„The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal."
Ein Depot, viele Abnehmer, begrenzte Fahrzeugkapazität. Das ist bis heute die Grundform. Ihr Rechenbeispiel umfasste ein Terminal und zwölf Lieferstellen bei 6.000 Gallonen Fahrzeugkapazität. Ihre Lösung kam auf 294 Distanzeinheiten; das vermutete Optimum lag bei 290 – rund 1,4 Prozent darunter, wohlgemerkt ohne Beweis.
Bemerkenswert ist der letzte Satz des Abstracts:
„No practical applications of the method have been made as yet."
Das Gründungspapier der Tourenplanung wurde von seinen Autoren nie in der Praxis angewendet. Wer heute den Abstand zwischen Forschung und Hof beklagt, steht in einer langen Tradition.
Die Zahl, die alles erklärt
Dantzig und Ramser nennen auch schon den Grund, warum das Problem hart ist. Wörtlich:
„the total number of different routes through n points is ½n!. Even for small values of n the total number of routes is exceedingly large, e.g. for n = 15, there are 653,837,184,000 different routes."
653 Milliarden mögliche Rundtouren bei fünfzehn Stopps. Das ist keine Übertreibung aus einer Marketingbroschüre, sondern eine Rechnung aus dem Originalpapier, und sie stimmt: 15! geteilt durch 2 ergibt exakt diesen Wert.
Diese Kombinatorik ist der Kern. Sie erklärt, warum Erfahrung in der Disposition so wertvoll ist – ein Mensch findet in Minuten eine brauchbare von 653 Milliarden Varianten – und zugleich, warum Erfahrung allein nicht ausreicht: Sie kann nicht wissen, wie weit die gefundene Lösung vom Optimum entfernt liegt.
Drei Problemklassen, die man auseinanderhalten sollte
In der Literatur werden drei Stufen unterschieden, die in Gesprächen regelmäßig durcheinandergeraten:
- TSP (Travelling Salesman Problem): ein Fahrzeug, keine Kapazitätsgrenze, jeder Punkt genau einmal. Die reine Reihenfolgefrage.
- CVRP (Capacitated VRP): ein Depot, eine Flotte, jeder Kunde hat eine Menge, jedes Fahrzeug eine Kapazität. Jetzt muss zusätzlich entschieden werden, welcher Stopp auf welche Tour gehört. Das ist die eigentlich schwierige Frage.
- VRPTW (VRP with Time Windows): zusätzlich hat jeder Kunde ein Zeitfenster, in dem die Bedienung beginnen muss, dazu Standzeiten. Das Fahrzeug darf warten, wenn es zu früh ist.
Die meisten realen Dispositionen sind mindestens VRPTW – und darüber hinaus. Dazu gleich mehr.
Was „NP-schwer" für die Disposition bedeutet
Dass das Vehicle Routing Problem NP-schwer ist, wird gern zitiert und selten erklärt. Die korrekte Quelle dafür ist übrigens eine Übersichtsarbeit von Lenstra und Rinnooy Kan aus dem Jahr 1981, die bekannte Härteresultate zusammenträgt – kein einzelner Beweis.
Praktisch bedeutet NP-Härte nicht „unlösbar", sondern: Der Aufwand, Optimalität zu beweisen, wächst so schnell, dass er ab einer bestimmten Größe nicht mehr zu bezahlen ist. Wie schnell, lässt sich beziffern. Uchoa und Kollegen haben 2017 einen neuen Benchmark mit 100 Instanzen zwischen 100 und 1.000 Kunden vorgelegt und mit dem damals besten exakten Verfahren gerechnet. Ergebnis, in ihren Worten:
„The BCP could solve 40 out of the 100 new instances to optimality in reasonable times (maximum of 5 days, for X-n186-k15)."
Und weiter: „The BCP can solve most instances with up to 275 customers."
Bis etwa 275 Kunden lässt sich Optimalität beweisen – und das kann bis zu fünf Tage dauern. Ein Regionallager mit 320 Lieferstellen liegt bereits jenseits dieser Grenze.
Die gute Nachricht steht direkt daneben. Dieselbe Untersuchung ließ zwei moderne Heuristiken laufen: ILS-SP erreichte im Mittel 0,52 Prozent Abstand zur besten bekannten Lösung, UHGS 0,19 Prozent. Bezogen auf die nachweislich optimal gelösten Instanzen waren es 0,18 beziehungsweise 0,09 Prozent.
Das ist die eigentliche Botschaft für die Praxis: Man bekommt heute routinemäßig Lösungen, die einen Bruchteil eines Prozents vom Optimum entfernt liegen. Man bekommt nur keinen Beweis dafür. In einer Disposition, in der ohnehin Standzeiten geschätzt und Zeitfenster verhandelt werden, ist das ein hervorragender Tausch.
Was der Preis dieser Genauigkeit ist
Rechenzeit. Die 0,19 Prozent von UHGS wurden mit im Mittel 98,79 Minuten CPU-Zeit pro Instanz erkauft, im schlechtesten Fall 560 Minuten. ILS-SP brauchte im Mittel 71,71 Minuten, maximal 792 Minuten – über dreizehn Stunden.
Ein Disponent, der um 6:30 Uhr einen Fahrzeugausfall kompensieren muss, hat diese Zeit nicht. Genau hier verläuft die Trennlinie zwischen Benchmark-Optimierung und Betriebsoptimierung: Die Frage ist nicht, welches Verfahren nach zwei Stunden am besten ist, sondern welches nach drei Minuten gut genug ist. Das sind unterschiedliche Wettbewerbe.
Was aus 1959 heute noch trägt
Zwei Dinge aus dem Originalpapier haben überlebt.
Erstens die Modellstruktur. Dantzig und Ramser skizzieren in ihren Abschnitten 4 und 5 bereits mehrere Produkte – mit Kammertankwagen – und gemischte Flotten. Zu letzterem schreiben sie, das Problem werde dann eines der Minimierung von Gesamtkosten statt reiner Kilometer. Das ist exakt die Unterscheidung, an der heute Optimierungsprojekte gelingen oder scheitern.
Zweitens die Instanzen selbst. Die klassische E-Serie der Benchmark-Bibliothek CVRPLIB wird üblicherweise Christofides und Eilon zugeschrieben, doch wie Uchoa und Kollegen anmerken, stammen einige Instanzen tatsächlich aus dem Aufsatz von Dantzig und Ramser. Wer heute einen Solver testet, rechnet unter Umständen noch immer an den Tankstellen von 1959.
Was das für Ihre Planung heißt
Drei Schlussfolgerungen, die sich aus der Literatur ziehen lassen:
- Optimalität ist kein sinnvolles Ziel. Sie ist ab 275 Kunden nicht mehr beweisbar und wäre, selbst wenn sie es wäre, für einen Plan, der auf geschätzten Standzeiten beruht, eine Scheingenauigkeit.
- Die Zuordnung ist schwerer als die Reihenfolge. Der Sprung von TSP zu CVRP – welcher Stopp auf welche Tour – ist der eigentliche Komplexitätssprung. Wer nur Reihenfolgen optimiert, hebt den kleineren Teil.
- Rechenzeit ist eine Planungsgröße. Ein Verfahren, das in drei Minuten 2 Prozent schlechter ist als eines, das zwei Stunden braucht, ist im Tagesgeschäft das bessere Verfahren.
Wie groß der Abstand zwischen einer typischen manuellen Disposition und einem gerechneten Plan tatsächlich ist, haben wir an einem Simulationsbeispiel mit 320 Lieferstellen nachgerechnet. Welche Verfahren dabei zum Einsatz kommen, steht im Beitrag zu den Metaheuristiken; welches davon bei welcher Problemlage trägt, im Überblick Verfahren der Tourenoptimierung.
Was daraus in der betrieblichen Praxis folgt – von der Datenaufnahme bis zum Projektablauf – steht im Leitfaden zur Tourenoptimierung. Wer die Verfahren selbst einbinden will, findet die Bausteine unter Routing- und Optimierungs-API.
Quellen
- Dantzig, G. B.; Ramser, J. H. (1959): The Truck Dispatching Problem. Management Science 6(1), S. 80–91. doi.org/10.1287/mnsc.6.1.80
- Lenstra, J. K.; Rinnooy Kan, A. H. G. (1981): Complexity of vehicle routing and scheduling problems. Networks 11(2), S. 221–227. doi.org/10.1002/net.3230110211
- Uchoa, E.; Pecin, D.; Pessoa, A.; Poggi, M.; Vidal, T.; Subramanian, A. (2017): New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research 257(3), S. 845–858. doi.org/10.1016/j.ejor.2016.08.012
- Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E. (2017): Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation 9(1), S. 61–100. doi.org/10.1007/s12532-016-0108-8
- Laporte, G. (2009): Fifty Years of Vehicle Routing. Transportation Science 43(4), S. 408–416. doi.org/10.1287/trsc.1090.0301