Wenn ein Anbieter mit Benchmark-Ergebnissen wirbt, lohnt die Frage, was in diesen Benchmarks eigentlich modelliert ist. Die Antwort ist ernüchternd – und sie erklärt, warum technisch überlegene Software im Betrieb scheitern kann.
Was die Standard-Testfälle enthalten
Die Tourenplanungsforschung rechnet seit Jahrzehnten auf wenigen Instanzsammlungen. Die wichtigsten:
- Solomon (1987) – der Klassiker für Zeitfensterprobleme, in Größen von 25, 50 und 100 Kunden.
- Gehring & Homberger – die Erweiterung auf 200 bis 1.000 Kunden.
- CVRPLIB – die Sammelbibliothek, in der unter anderem die klassische E-Serie liegt. Einige dieser Instanzen stammen tatsächlich noch aus dem Gründungsaufsatz von Dantzig und Ramser aus dem Jahr 1959.
- Uchoa et al. (2017) – der moderne Ersatz, 100 Instanzen zwischen 100 und 1.000 Kunden.
Die Zielfunktion der Solomon-Sammlung ist zweistufig und lautet, wie das Forschungsrepositorium der SINTEF sie dokumentiert: erstens Fahrzeuganzahl minimieren, zweitens Gesamtdistanz minimieren. Die Entfernungen sind euklidisch – Luftlinie. Und weiter: „the value of travel time is equal to the value of distance between two nodes." Fahrzeit gleich Entfernung.
Noch aufschlussreicher ist, was das Dateiformat gar nicht ausdrücken kann. Es hat genau sieben Felder: Kundennummer, x, y, Bedarf, frühester Beginn, spätester Beginn, Servicezeit. Daraus folgt:
- Keine einzige der 56 Instanzen hat mehr als eine Servicezeit. Sie ist eine Konstante je Instanz – 90 in siebzehn Instanzen, 10 in den übrigen 39. Jeder Stopp dauert exakt gleich lang, unabhängig von Menge, Entladeaufwand oder Rampe.
- Alle 56 Instanzen haben 25 identische Fahrzeuge, über die gesamte Sammlung existieren nur drei verschiedene Kapazitäten.
- Es gibt kein Feld für ein zweites Zeitfenster, eine Fahrerpause, eine Qualifikation, einen Fahrzeugtyp oder eine Ladungsrestriktion.
Damit ist der Rahmen abgesteckt: kein Straßennetz, kein Verkehr, keine Fahrer, keine Kosten außer Fahrzeugen und Kilometern.
Die Forschung kritisiert sich selbst – deutlich
Man muss diese Kritik nicht selbst formulieren. Uchoa und Kollegen schreiben 2017 im Abstract ihres eigenen Benchmark-Papiers:
„The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suffer from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too artificial; (iii) are too homogeneous, not covering the wide range of characteristics found in real applications."
Zu (i) liefern sie ein bemerkenswertes Detail: Für die klassische Sammlung hätten Rochat und Taillard bereits 1995 veröffentlicht, was heute als optimal gilt – bis auf eine einzige Instanz mit 199 Kunden, bei der die damals gemeldete Lösung um 0,012 Prozent danebenlag. Ein Benchmark, der 22 Jahre vor Erscheinen des Kritikpapiers faktisch ausgereizt war, auf dem aber weiter publiziert wurde.
Zu (ii) nennen sie die Golden-Instanzen: Die Kunden liegen dort in konzentrischen Kreisen, Quadraten oder sechszackigen Sternen, die Bedarfe folgen symmetrischen Mustern. Zu (iii) genügt ein Satz: „there are no instances with clusters of customers." Keine Kundencluster – in einer Disziplin, deren Praxisproblem die ungleichmäßige Kundenverteilung ist.
Sechs Lücken zwischen Benchmark und Hof
Aus der Literatur lassen sich sechs konkrete Unterschiede benennen.
1. Die Zielfunktion ist zu einfach. Benchmarks minimieren Fahrzeuge und Kilometer. Eine reale Disposition wägt Fahrerstunden gegen Maut gegen Kraftstoff gegen Liefertreue ab – und zusätzlich gegen Dinge, die sich schlecht beziffern lassen, etwa gleichmäßige Auslastung der Fahrer.
2. Die Karte ist falsch – und der Fehler ist beziffert. Boyacı, Dang und Letchford haben 2021 dieselben Instanzen einmal euklidisch und einmal auf echten OpenStreetMap-Netzen von zwölf Großstädten gerechnet. Der Umwegfaktor – tatsächliche Straßenentfernung geteilt durch Luftlinie – reicht von 1,174 in Paris über 1,268 in London bis 1,403 in Mexiko-Stadt.
Entscheidend ist die Folge: Wer euklidisch plant und real fährt, zahlt beim Steiner-TSP 6,4 bis 35,3 Prozent Aufschlag, beim kapazitierten Problem 5,5 bis 31,4 Prozent. Und die Autoren nennen selbst den Punkt, der für Zeitfensterbetriebe entscheidend ist:
„a route that is feasible for the planar Euclidean version may become infeasible when the edges in the route are replaced with shortest paths in the road network […] especially if the time windows are narrow."
Der Plan wird also nicht nur teurer, sondern unzulässig. Ben Ticha und Kollegen bestätigen das Bild:
„Most approaches found in the literature address these problems using the so-called customer-based graph […] In many situations, this representation induces negative effects on the solution quality or efficiency."
3. Die Uhr ist falsch. Benchmarks kennen keinen Berufsverkehr. Zeitabhängige Fahrzeiten sind ein eigenes Forschungsfeld (Ichoua et al. 2003) und in Standardinstanzen nicht enthalten.
4. Der Fahrer kommt nicht vor. Das ist die größte Lücke für den europäischen Markt. Asvin Goel formulierte 2009 in einer Arbeit über Lenk- und Ruhezeiten:
„Regulations regarding drivers' working hours often have a big impact on total transit times […] Although of particular importance for many real-life applications, they have received only very little attention in the vehicle routing literature."
Ein Plan, der die EU-Verordnung 561/2006 nicht abbildet, ist nicht suboptimal – er ist rechtswidrig.
5. Die Welt hält nicht still. Ausfälle, Nachträge, Sperrungen: In der Realität ändert sich die Aufgabe während der Ausführung. Dynamische Tourenplanung ist ein eigenes Feld (Pillac et al. 2013), das in statischen Instanzen per Definition nicht vorkommt.
6. Synchronisation fehlt völlig. Michael Drexl hat die Fälle katalogisiert, in denen zwei Fahrzeuge sich treffen müssen, Wechselbrücken getauscht oder Ladungen umgeschlagen werden. In keinem Standard-Benchmark existiert so etwas.
Und dann noch die Rechenzeit
Selbst wenn ein Verfahren all das könnte, bliebe ein praktisches Problem. Die beiden Spitzenverfahren aus der Uchoa-Studie brauchten im Mittel 71,71 beziehungsweise 98,79 Minuten pro Instanz, im schlechtesten Fall über dreizehn Stunden. Ein Benchmark-Sieg wird in Stunden gemessen. Ein Disponent hat Minuten.
„Rich VRP" – der Begriff für das, was fehlt
Die Forschung hat für realitätsnahe Varianten einen eigenen Begriff geprägt. Caceres-Cruz und Kollegen fassen es 2014 in ACM Computing Surveys zusammen:
„The new tendency is mainly focused on applying this study case to real-life problems. Due to this trend, the Rich VRP arises: combining multiple constraints for tackling realistic problems."
Die für unsere Zwecke aufschlussreichste Arbeit stammt von Michael Drexl (2012). Er vergleicht systematisch den Stand der Forschung mit dem, was kommerzielle Tourenplanungssysteme tatsächlich können, und identifiziert daraus die offenen Lücken. Wer eine Software auswählt, findet dort die brauchbarste Systematik.
Was daraus für eine Softwareauswahl folgt
Die praktische Konsequenz ist keine Absage an Optimierung, sondern eine andere Prüfreihenfolge. Fragen Sie nicht zuerst nach Verfahren und Benchmarks, sondern nach Abbildbarkeit:
- Kann das System Ihr Wegenetz rechnen – oder nur Luftlinie mit Faktor? Der Umwegfaktor liegt je nach Stadt zwischen 1,17 und 1,40; ein pauschaler Faktor trifft ihn nirgends genau.
- Bildet es Lenk- und Ruhezeiten ab? Nicht als nachgelagerte Prüfung, sondern als harte Nebenbedingung während der Optimierung.
- Kennt es Ihre Fahrzeugprofile? Gewicht, Höhe, Breite, Länge – und prüft es diese gegen die Eigenschaften einzelner Wegsegmente?
- Was passiert bei einer Änderung um 6:30 Uhr? Ein Neulauf, eine lokale Reparatur oder gar nichts?
- Wie lange rechnet es auf Ihrer Instanzgröße? Nicht auf Solomon-100, sondern auf Ihren 320 Lieferstellen.
Die letzte Frage lässt sich nur beantworten, indem man es tut. Genau deshalb beginnt bei uns jedes Projekt mit einer Rechnung auf echten Kundendaten und nicht mit einer Präsentation – siehe Tourenoptimierungs-Check.
Die eigentliche Botschaft
Ein Solver, der Benchmarks gewinnt, hat bewiesen, dass er ein sauber definiertes mathematisches Problem gut löst. Er hat nicht bewiesen, dass Ihr Problem dieses Problem ist.
Der Unterschied liegt fast nie im Algorithmus. Er liegt im Modell – also darin, wie vollständig Ihre Regeln erfasst sind. Welche das im Einzelnen sind, haben wir in der Übersicht der Restriktionen zusammengetragen.
Wie ein Optimierungsprojekt von der ersten Datenlieferung bis zum belastbaren Ergebnis abläuft, steht im Leitfaden zur Tourenoptimierung. Wer vor der Frage steht, ob Standardsoftware oder ein eigenes Modell die passende Antwort ist, findet den Vergleich der Ansätze unter Tourenplanung Software.
Quellen
- Uchoa, E. u. a. (2017): New benchmark instances for the Capacitated Vehicle Routing Problem. EJOR 257(3), S. 845–858. doi.org/10.1016/j.ejor.2016.08.012
- Solomon, M. M. (1987): Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research 35(2), S. 254–265. doi.org/10.1287/opre.35.2.254
- Boyacı, B.; Dang, T. H.; Letchford, A. N. (2021): Vehicle routing on road networks: How good is Euclidean approximation? Computers & Operations Research 129, 105197. doi.org/10.1016/j.cor.2020.105197
- Ben Ticha, H.; Absi, N.; Feillet, D.; Quilliot, A. (2018): Vehicle routing problems with road-network information: State of the art. Networks 72(3), S. 393–406. doi.org/10.1002/net.21808
- Goel, A. (2009): Vehicle Scheduling and Routing with Drivers' Working Hours. Transportation Science 43(1), S. 17–26. doi.org/10.1287/trsc.1070.0226
- Ichoua, S.; Gendreau, M.; Potvin, J.-Y. (2003): Vehicle dispatching with time-dependent travel times. EJOR 144(2), S. 379–396. doi.org/10.1016/S0377-2217(02)00147-9
- Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L. (2013): A review of dynamic vehicle routing problems. EJOR 225(1), S. 1–11. doi.org/10.1016/j.ejor.2012.08.015
- Drexl, M. (2012): Rich vehicle routing in theory and practice. Logistics Research 5(1–2), S. 47–63. doi.org/10.1007/s12159-012-0080-2
- Drexl, M. (2012): Synchronization in Vehicle Routing – A Survey of VRPs with Multiple Synchronization Constraints. Transportation Science 46(3), S. 297–316. doi.org/10.1287/trsc.1110.0400
- Caceres-Cruz, J. u. a. (2014): Rich Vehicle Routing Problem: Survey. ACM Computing Surveys 47(2), Artikel 32, S. 32:1–32:28. doi.org/10.1145/2666003