CapaciteitsVRP

CapaciteitsVRP, often in Dutch referred to as capaciteitsVRP, is de capacitated vehicle routing problem. Het is een variant van het Vehicle Routing Problem (VRP) waarbij elke voertuig een maximale lading heeft. Het doel is om een set klanten te bedienen vanaf één depot met een fleet van identieke voertuigen, zodat alle klanten precies eenmaal worden bezocht en de totale afstand of kosten van de routes minimaal zijn, zonder de capaciteit van een voertuig te overschrijden.

Invoer en doelstelling: er is een depot, een aantal klanten met vraagvoorkeuren, en een groep voertuigen met een gezamenlijke of individuele capaciteitslimiet. De gegevens omvatten meestal een kosten- of afstandsmatrix tussen alle locaties. Het gewenste resultaat is een verzameling voertuigroutes die starten en eindigen bij het depot, alle klanten bedienen, en waarbij voor elke route de som van de klantvragen niet groter is dan de voertuigcapaciteit. De totale kosten van alle routes wordt geminimaliseerd, en vaak wordt ook het gebruik van voertuigen beperkt.

Formulering en concepten: CapaciteitsVRP kan worden geformuleerd als een integer lineair programmeermodel met binaire variabelen die aangeven of een rij verbinding tussen twee locaties wordt gebruikt. Belangrijke constraints zijn: elke klant wordt precies eenmaal bediend, elke route vormt een gesloten circuit vanaf het depot, en de lading langs een route blijft onder de capaciteitsgrens. Subtoureel-eliminatie is vaak nodig om ongeldige oplossingen te voorkomen.

Oplossingsmethoden en toepassingen: CapaciteitsVRP is NP-hard. Oplossingen worden gekozen via exacte methoden zoals branch-and-cut of branch-and-price, en via heuristieken en metaheuristieken zoals Clarke–Wrey-savings, genetische algoritmen, tabu search en simulatief evalueren. Toepassingen liggen in logistiek en distributie, last-mile levering en supply chain planning, waar sprake is van beperkte vrachten en efficiënte belading. Varianten omvatten tijdvensters (VRPTVRP), heterogene voertuigen, meerdere depots en splitsing van leveringen.