Solve the vehicle routing problem (VRP) in Python

The vehicle routing problem — send a fleet of capacity-limited vehicles out from a depot so every customer is served and the total distance is smallest — is one of the most-searched optimization problems in Python, and the tutorials that answer it are almost all one specific library or a hand-rolled heuristic. With quicopt you model the capacitated VRP (CVRP) and get a provably optimal set of routes.

The naive approach

Nearest-neighbor or savings heuristics build routes greedily — fast, but no guarantee they are shortest, and awkward to extend with real constraints. Enumerating route splits explodes with customers and vehicles. Model it instead.

Model it as a MILP

Node 0 is the depot. A binary x[i,j] uses the arc i → j; each customer is entered and left once; exactly K vehicles leave and return to the depot. The per-node load variables u enforce capacity and eliminate subtours:

from ortools.math_opt.python import mathopt
from quicopt import Client
# Node 0 is the depot; 1..4 are customers with demands. K vehicles, capacity Q.
dist = [[0,5,6,5,6],[5,0,4,9,8],[6,4,0,8,9],[5,9,8,0,4],[6,8,9,4,0]]
demand = [0, 3, 3, 3, 3]
n, K, Q = 5, 2, 6
model = mathopt.Model(name="cvrp")
x = {(i,j): model.add_binary_variable(name=f"x_{i}_{j}") for i in range(n) for j in range(n) if i != j}
u = [model.add_variable(lb=0.0, ub=Q, name=f"u{i}") for i in range(n)]
for j in range(1, n):                                  # each customer entered/left once
    model.add_linear_constraint(sum(x[i,j] for i in range(n) if i != j) == 1)
    model.add_linear_constraint(sum(x[j,i] for i in range(n) if i != j) == 1)
model.add_linear_constraint(sum(x[0,j] for j in range(1, n)) == K)   # K routes leave depot
model.add_linear_constraint(sum(x[j,0] for j in range(1, n)) == K)   # K routes return
for i in range(1, n):
    for j in range(1, n):
        if i != j:                                     # MTZ load: subtour elim + capacity
            model.add_linear_constraint(u[j] >= u[i] + demand[j] - Q * (1 - x[i,j]))
    model.add_linear_constraint(u[i] >= demand[i])
model.minimize(sum(dist[i][j] * x[i,j] for i in range(n) for j in range(n) if i != j))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  30.0
├── x:          u0=0, u1=6, u2=3, u3=6, u4=3, x_0_1=0, …  (25 variables)
└── solve_time: 0.0177 s

What you get

status: optimal means total distance 30 is proven best — two routes, each carrying two customers within the capacity of 6, matching the brute-force optimum. The u loads (3 then 6 on each route) show the capacity filling up along the way and keep every route anchored to the depot.

Time windows, multiple depots, and per-vehicle costs are added as more linear constraints on the same model. This compact formulation targets small-to-medium instances; large fleets call for specialized routing methods. For the single-vehicle case, see the traveling salesman guide.

Next

• The problem class behind this: Mixed-integer linear (MILP)
• The single-tour version: Traveling salesman (TSP)
• Set up the client and solve your first model: Getting started

Reference: G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science, 1959.