Glossar · approach
Kapazitierte Tourenplanung
Entwurf kostenminimaler Touren, die an einem einzigen Depot beginnen und enden, jeden Kunden genau einmal besuchen und deren Gesamtnachfrage pro Tour die Fahrzeugkapazität nicht überschreitet.
Capacitated Vehicle Routing ProblemCVRPKapazitiertes TourenplanungsproblemTruck Dispatching Problem
Das Capacitated Vehicle Routing Problem (CVRP) ist das Problem, eine kostenminimale Menge von Fahrzeugtouren zu entwerfen, die (a) an einem einzigen Depot beginnen und enden, (b) jeden Kunden genau einmal besuchen und (c) auf jeder Tour eine Gesamtnachfrage tragen, die die Fahrzeugkapazität nicht überschreitet. Es gibt keine Zeitfenster — diese Erweiterung heißt VRPTW. Die Kosten sind üblicherweise Gesamtstrecke, Gesamtzeit oder eine Kombination aus Kraftstoff und Fahrerlohn. CVRP ist NP-schwer und ist der kanonische Vorfahr der gesamten VRP-Familie; Dantzig und Ramser (1959) eröffneten es als 'The Truck Dispatching Problem'. Standardwerk: Toth und Vigo (2014). Praktische Lösungsmethoden reichen vom klassischen Clarke-Wright-Savings-Heuristik (1964 — auf mittleren Instanzen weiterhin Benchmark-Qualität) über 2-opt- und Or-opt-Verbesserung, moderne Branch-and-Cut-and-Price-Exaktalgorithmen (Fukasawa et al. 2006) bis zu ALNS-Metaheuristiken (Adaptive Large Neighborhood Search).
Örnek
Ein regionaler Distributor liefert täglich von einem Depot an 80 Kunden, deren Nachfrage in kg bekannt ist; jedes Fahrzeug trägt 2 t; die Frage ist, wie viele Fahrzeuge fahren, welche Kunden auf welchen Fahrzeug und in welcher Reihenfolge, um die Gesamtkilometer zu minimieren.