Vehicle Routing Problem (VRP)

VRP staat voor Vehicle Routing Problem. Het generaliseert het handelsreizigersprobleem (TSP), dat de kortste rondgang voor één voertuig zoekt, naar een heel wagenpark met beperkingen uit de praktijk: laadvermogen, levertijdvensters, werktijden van chauffeurs, voertuigtypen en meer. Dantzig en Ramser beschreven het in 1959 voor het eerst als het "truck dispatching problem", en het is nog altijd een van de meest bestudeerde problemen in de operations research.

De meeste praktijkproblemen zijn een variant. Het capacitated VRP (CVRP) begrenst wat elk voertuig kan vervoeren; het VRP met tijdvensters (VRPTW) voegt per stop een ophaal- of levervenster toe; het pickup-and-delivery-probleem (PDP) koppelt elke ophaling aan de bijbehorende levering op hetzelfde voertuig; en varianten met meerdere depots of een gemengde vloot laten voertuigen op verschillende plekken starten of verschillen in grootte en uitrusting.

Het VRP is NP-moeilijk: het aantal mogelijke oplossingen explodeert met elke extra stop. Eén voertuig met tien stops kan die al in 3.628.800 verschillende volgordes aandoen. Exacte methoden werken alleen voor kleine instanties, dus productiesolvers gebruiken heuristieken. Een constructiemethode zoals nearest neighbour of het savings-algoritme van Clarke en Wright bouwt een eerste haalbaar plan, en local search verbetert dat met zetten als 2-opt, relocate en swap, vaak gestuurd door een metaheuristiek zoals simulated annealing.

Voorbeeld: een distributeur heeft 3 bestelwagens met elk 1.000 kg laadvermogen en 45 leveringen, elk met een tijdvenster. Een planner kan met de hand een werkbaar plan maken; een solver respecteert elk venster en elk laadvermogen terwijl hij de totale afstand minimaliseert, en levert zijn plan binnen seconden. Leveringen die niet passen, worden als ongepland gemeld, zodat de planner capaciteit kan toevoegen of een venster kan verruimen.

De tripoptimalisatie van Transportial maakt de solver een platforminstelling: PTV OptiFlow, PTV xTour, OSRM voor de stopvolgorde van één voertuig, CloverOpt of de eigen solver van Transportial, die trips opbouwt met nearest-neighbour-constructie, ze verbetert met relocate-, swap-, merge- en split-zetten en elke route afwerkt met 2-opt. De optimizer respecteert tijdvensters, gewicht, voertuigtype en uitrustingseisen, kan wettelijke rijtijdpauzes in routes en ETA's invoegen, en levert een voorbeeld dat de planner aanpast voordat hij opslaat.