liveBook · Manning

Capacitated vehicle routing problem

As explained in Applied Reinforcement Learning

The capacitated vehicle routing problem is an optimization problem that assigns customer visits to vehicle routes while respecting vehicle capacities and minimizing total travel cost.

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

How Applied Reinforcement Learning covers it

How deep it goes
Defines the objective and capacity constraints, then models search states and an MCTS solution with rollout and route improvement.
Examples
Uses a delivery fleet with customer demands, limited truck capacity, a depot, and total travel distance.
What it assumes
Builds on a stated MCTS foundation and contrasts CVRP with the Traveling Salesman Problem.
What you can do after
Apply Monte Carlo tree search with greedy rollouts and 2-opt improvement to seek capacity-feasible, shorter routes.
How it connects
Compares CVRP with the Traveling Salesman Problem and connects it to Monte Carlo tree search and combinatorial optimization.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.