Explorable · Tourenplanung
Ein Depot, ein paar Kunden, ein paar Fahrzeuge. Die Aufgabe klingt harmlos, aber schon bei zwanzig Stopps gibt es mehr mögliche Tourenpläne als Atome in einer Handvoll Sand. Unten stehen fünf Verfahren, die das Problem nicht lösen, sondern nur unterschiedlich geschickt umgehen. Schieb die Stopps herum, dreh an den Reglern und sieh zu, wo es klemmt.
Gesamtstrecke gegen den Aufwand, den das Verfahren dafür treibt. Die x-Achse zählt geprüfte Züge, logarithmisch — sonst verschwinden die schnellen Verfahren am linken Rand.
Jeder Lauf eine Zeile. Verbesserungsverfahren setzen auf dem Stand auf, der beim Start des Laufs auf der Karte lag.
| Verfahren | Strecke | Fahrz. | Auslastung | ZF-Verl. | Rechenzeit | Iter. |
|---|---|---|---|---|---|---|
| Noch nichts gerechnet. | ||||||
Rechenzeit misst nur den Solver, nicht die Animation.
Drei Dinge, die man an dieser Seite selbst nachstellen kann.
Zwanzig Stopps auf vier Fahrzeuge zu verteilen und je Fahrzeug zu sortieren, ergibt mehr als 1020 Tourenpläne. Kein Rechner probiert die durch, also probiert keiner sie durch — alle Verfahren hier raten systematisch.
Nearest Neighbour ist gierig und zahlt am Ende drauf: die übrig gebliebenen Stopps liegen verstreut. Clarke-Wright entscheidet stattdessen, welche Zusammenlegung am meisten Umweg spart, und liegt fast immer deutlich vorn — vor jeder Nachbesserung.
Kapazität bricht Touren auf, die Schichtdauer bricht sie noch früher auf, und Zeitfenster erzwingen eine Reihenfolge, die geometrisch unsinnig ist. Schalte die Zeitfenster ein und sieh zu, wie die Strecke steigt, während die Verletzungen fallen.