The capacitated vehicle routing problem (CVRP) asks how to divide customer visits among a fleet so every customer is served once, no vehicle exceeds its carrying capacity, and total travel distance is minimized. section 7.4
A delivery plan must satisfy:
- Assign customers across multiple vehicles departing from a depot. section 7.4
- Keep each route’s combined customer demand within vehicle capacity. section 7.4
- Minimize the fleet’s cumulative travel distance. section 7.4
Unlike the Traveling Salesman Problem, CVRP must partition customers among vehicles as well as choose visit order. The treatment represents routes and unvisited customers as a search state, then applies Monte Carlo tree search with greedy rollouts and 2-opt improvement. section 7.4
Daily delivery planning
A delivery company assigns customers with different demands to trucks with limited capacity, seeking routes that serve everyone without exceeding loads or wasting travel distance. section 7.4
Figure 7.6 Capacitated Vehicle Routing Problem (CVRP) schema.
Use the schematic to visualize the fleet-routing problem. section 7.4
