Vehicle Routing Problem in Python — Core Concepts

The Vehicle Routing Problem (VRP) extends route optimization from one vehicle to many. A single-vehicle tour is the Traveling Salesman Problem. Add a fleet and capacity limits and you get the Capacitated VRP (CVRP) — the workhorse model behind most delivery logistics.

VRP variants

Each real-world constraint spawns a named variant:

• CVRP — each vehicle has a maximum load. A van carrying 200 kg cannot accept a 50 kg parcel if it is already at 180 kg.
• VRPTW — time windows restrict when each customer can be served. A lunch-delivery service must arrive between 11:30 and 13:00.
• MDVRP — multiple depots. Vehicles start from different warehouses and return to their origin.
• VRPPD — pickup and delivery pairs. A courier collects a parcel at location A and drops it at location B within the same route.
• OVRP — open routes. Vehicles do not return to the depot (common for field technicians heading home after their last job).

Most real systems combine several of these. A food distributor may need CVRP with time windows and multiple depots simultaneously.

How solvers approach VRP

Solving VRP exactly is computationally impractical beyond roughly 20 stops. Practical approaches:

1. Cluster-first, route-second — group stops geographically (K-Means or sweep algorithm), then solve a TSP within each cluster. Simple but misses cross-cluster efficiencies.
2. Route-first, cluster-second — solve one giant TSP, then split the tour into vehicle-sized segments. Often better for uniform demand.
3. Integrated metaheuristics — OR-Tools and similar solvers build an initial solution and iteratively improve it by moving stops between vehicles, reversing segments, and swapping pairs.

OR-Tools uses a combination of cheapest insertion for the initial solution and guided local search for improvement. The user controls time budgets and can prioritize solution quality versus speed.

Modeling in Python with OR-Tools

The workflow has four steps:

1. Index manager — maps location indices to solver indices.
2. Distance and demand callbacks — functions the solver calls to check travel cost and load at each stop.
3. Dimensions — capacity and time are modeled as cumulative dimensions along each route.
4. Search parameters — strategy selection and time limits.

The solver returns which stops belong to each vehicle and in what order. You extract routes by walking the solution’s NextVar chain for each vehicle.

Evaluating solution quality

Two metrics matter:

• Total distance (or time) — the sum across all vehicle routes. Lower is better.
• Balance — how evenly work distributes. If one driver works twelve hours while another works three, the solution may be optimal in distance but operationally unfair.

Adding a soft constraint that penalizes route-length variance helps balance workloads. OR-Tools supports this through dimension span penalties.

Common misconceptions

The biggest mistake is assuming that VRP solvers give perfect answers. For anything above 50 stops, the solutions are heuristic — good but not provably optimal. The practical question is whether the solver’s answer beats what a human dispatcher would do manually. In almost every case, it does by 10-30 percent.

Another trap is ignoring real driving conditions. A distance matrix built from straight-line calculations produces routes that look great on paper but fall apart on actual roads.

The one thing to remember: VRP assigns stops to vehicles and orders each vehicle’s route under capacity, time, and depot constraints — turning fleet dispatch from guesswork into a structured optimization.