Tourenplanung.
Touren für eine Flotte planen, die viele Standorte bedient, unter Zeitfenstern, Fahrzeugkapazitäten und Lenkzeitregeln.
Welches Fahrzeug fährt welchen Stopp in welcher Reihenfolge an, damit jede Lieferung in ihrem Zeitfenster ankommt und möglichst wenige Kilometer anfallen?
Das Tourenplanungsproblem (VRP) ist NP-schwer, ebenso seine Varianten. Dazu gehören Tourenplanung mit Kapazitäten und Zeitfenstern (CVRPTW), Abhol- und Lieferverkehre (PDPTW) und Touren mit mehreren Depots (MDVRP). kint formuliert sie als gemischt-ganzzahlige Programme und löst sie mit Branch and Bound und Schnittebenen. Ein Warmstart aus einem guten Tourenplan verkürzt die Suche. Anschließend weist der Solver aus, wie weit der Plan vom Optimum entfernt sein kann.
Wo Tourenplanung schwer wird.
Die Zahl möglicher Tourenpläne wächst faktoriell mit der Zahl der Stopps. Schon eine mittelgroße Flotte hat weit mehr Pläne, als sich einzeln prüfen lassen.
Zeitfenster, Kapazitäten und Lenkzeitregeln ziehen in verschiedene Richtungen. Wer eine Regel erfüllt, verletzt oft eine andere. Die zulässigen Pläne sind wenige und weit verstreut.
Stornierungen, neue Aufträge und Verkehr verändern das Problem im Lauf des Tages. Der beste Plan vom Morgen ist mittags vielleicht nicht mehr der beste.
Von den Regeln zur Schranke.
Der Decision Agent von kint schreibt das Modell aus der Beschreibung der Planer. Im Pilotprojekt prüfen die Forward Deployed Engineers von kint es mit den Fachleuten. Danach rechnet der Solver die folgenden Schritte.
Modell formulieren
Jede Wahl von Fahrzeug und nächstem Stopp wird zu einer Ja-Nein-Variablen. Kapazitäten, Zeitfenster und Lenkzeiten werden zu Nebenbedingungen. Die Zielfunktion ist die Gesamtstrecke oder die Gesamtkosten.
Mit Schnittebenen verschärfen
Zusätzliche gültige Ungleichungen verkleinern den Suchraum und schließen große Mengen schlechter Pläne aus, ohne sie einzeln zu bewerten.
Mit Warmstart suchen
Ein guter Startplan gibt dem Solver einen Bezugspunkt. Branch and Bound verbessert ihn und nähert sich dem Optimum.
Optimalitätslücke ausweisen
Die Optimalitätslücke gibt an, wie weit der Plan vom bestmöglichen entfernt sein kann. Bei einer Lücke von null gibt es für das Modell, wie es formuliert ist, keinen besseren Plan.
Ein Plan für Tourenplanung, mit seinen Gründen.
Unten stehen die Teile eines Ergebnisses für Tourenplanung. Die Planer prüfen sie, bevor der Plan freigegeben wird.
Der Aufbau einer Antwort- PlanEine Tour je Fahrzeug mit Stoppreihenfolge und geplanten Ankunftszeiten.
- bindende NebenbedingungZum Beispiel: Zwei enge Kundenzeitfenster bestimmen die Gesamtstrecke, nicht die Flottengröße.
- SensitivitätWas ein zusätzliches Fahrzeug oder ein breiteres Zeitfenster bei einem Kunden einsparen würde.
- Schranke und OptimalitätslückeSchranke und Optimalitätslücke, gespeichert mit dem Lauf.
- ProtokollDatenversion, Modellversion, wer das Modell geprüft hat und wer den Plan freigegeben hat.
Bringen Sie uns diese Entscheidung.
Bringen Sie eine wiederkehrende Entscheidung zu Tourenplanung mit ihren Regeln und Daten mit. Ihre Planer erhalten ein erstes Modell, das sie lesen können.
- Ergebnisse
- Plan, bindende Nebenbedingung, Sensitivität, Schranke und Optimalitätslücke, Protokoll
- Rechenzentren
- Betrieb in Deutschland oder in Ihrem eigenen Rechenzentrum
- alle Problemtypen
- Routen, Pläne, Bestände und Preise
- Kontakt
- hello@kint.pro