Skip to content

The Vehicle Routing Problem with Time Windows

This example illustrates a model for the vehicle routing problem with time windows (VRPTW).

In the VRPTW the objective is to minimize the total cost of routing vehicles from a central depot to a set of customers. Each customer must be visited exactly once within a specified time window to deliver their required demand, each customer has a service time it takes to unload the vehicle, and each vehicle has a maximum capacity of goods to deliver. If a vehicle arrives early it is allowed to wait for the customer's time window to start.

Let G(V,E)G(V,E) be graph with vertices V=C{0,n+1}V = C \cup \{0, n + 1 \} where C={1,,n}C = \{1, \dots, n \} are the customers such that the depot is split in a 'start' and and 'end' depot and EE is the edges connecting all customers with each other and the depot vertices. Edge (i,j)(i,j) is associated with a cost cijc_{ij} and a travel time tijt_{ij}. Vertex ii is associated with a time window [ai,bi][a_i,b_i] and a demand did_i. The vehicle capacity is denoted QQ.

Usually the problem is formulated as a path based model

minpPcpλps.t. pPαiλp=1iCλpBpP \begin{aligned} \min{ } & \sum_{p \in P} c_p \lambda_p \\ \text{s.t. } & \sum_{p \in P} \alpha_i \lambda_p = 1 & & i \in C \\ & \lambda_p \in \mathbb{B} && p \in P \end{aligned}

where paths pPp \in P are feasible paths in G(V,E)G(V,E) with accumulated edge cost cp=(i,j)Ecij(sp:s=(i,j)1)c_p = \sum_{(i,j) \in E} c_{ij} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big ) and αi=(i,j)δ+(i)(sp:s=(i,j)1)\alpha_i = \sum_{(i,j) \in \delta^+(i)} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big ) expresses if path pp visits customer ii.

The corresponding network model can be formulated as

min(i,j)Ecijxijs.t. (i,j)δ+(i)xij=1iCxij=pP(sp:s=(i,j)1)λp(i,j)E1pPλpCλpBpPxi,jB(i,j)E \begin{aligned} \min{ } & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t. } & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & & i \in C \\ & x_{ij} = \sum_{p \in P} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big ) \lambda_p & & (i,j) \in E \\ & 1 \leq \sum_{p \in P} \lambda_p \leq |C| \\ & \lambda_p \in \mathbb{B} && p \in P \\ & x_{i,j} \in \mathbb{B} && (i,j) \in E \end{aligned}

where pPp \in P are paths in a graph G(V,E)G(V,E) subject to time and demand constraints modeled as disposable resources. Demand with vertex consumption did_i and bounds [0,Q][0,Q] for all iVi \in V and time with edge consumption tijt_{ij} and vertex bounds [ai,bi][a_i,b_i] for all iVi \in V.

The problem is implemented as

min(i,j)Ecijxijs.t. (i,j)δ+(i)xij=1iCxi,jB(i,j)E \begin{aligned} \min{ } & \sum_{(i,j) \in E} c_{ij} x_{ij} \\ \text{s.t. } & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & & i \in C \\ & x_{i,j} \in \mathbb{B} && (i,j) \in E \end{aligned}

with the graph and resource constraints described above. See the modeling section for details.

# Vehicle Routing Problem with Time Windows
from flowty import Model, xsum
from or_datasets import vrp_rep

bunch = vrp_rep.fetch_vrp_rep("solomon-1987-r1", instance="R102_025")
name, n, E, c, d, Q, t, a, b, x, y = bunch["instance"]

m = Model()

# one graph, it is identical for all vehicles
g = m.addGraph(obj=c, edges=E, source=0, sink=n - 1, L=1, U=n - 2, type="B")

# adds resources variables to the graph.
# travel time and customer time windows
    graph=g, consumptionType="E", weight=t, boundsType="V", lb=a, ub=b, name="t"

# demand and capacity
    graph=g, consumptionType="V", weight=d, boundsType="V", lb=0, ub=Q, name="d"

# set partition constriants
for i in range(n)[1:-1]:
    m += xsum(x * 1 for x in g.vars if i == x.source) == 1

# packing set
for i in range(n)[1:-1]:
    m.addPackingSet([x for x in g.vars if i == x.source])

status = m.optimize()