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)$ be graph with vertices $V = C \cup \{0, n + 1 \}$ where $C = \{1, \dots, n \}$ are the customers such that the depot is split in a 'start' and and 'end' depot and $E$ is the edges connecting all customers with each other and the depot vertices. Edge $(i,j)$ is associated with a cost $c_{ij}$ and a travel time $t_{ij}$. Vertex $i$ is associated with a time window $[a_i,b_i]$ and a demand $d_i$. The vehicle capacity is denoted $Q$.

Usually the problem is formulated as a path based model

$$\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 $p \in P$ are feasible paths in $G(V,E)$ with accumulated edge cost $c_p = \sum_{(i,j) \in E} c_{ij} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big )$ and $\alpha_i = \sum_{(i,j) \in \delta^+(i)} \Big ( \sum_{ s \in p: s = (i,j)} \mathbf{1} \Big )$ expresses if path $p$ visits customer $i$.

The corresponding network model can be formulated as

$$\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 $p \in P$ are paths in a graph $G(V,E)$ subject to time and demand constraints modeled as disposable resources. Demand with vertex consumption $d_i$ and bounds $[0,Q]$ for all $i \in V$ and time with edge consumption $t_{ij}$ and vertex bounds $[a_i,b_i]$ for all $i \in V$.

The problem is implemented as

$$\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.

Fetching data

To fetch the benchmark data using fetch_vrptw check out the examples.

# Vehicle Routing Problem with Time Windows
import flowty
import fetch_vrptw

name, n, E, C, D, q, T, A, B, X, Y = fetch_vrptw.fetch("Solomon", "R102", 25)

model = flowty.Model()

# one graph, it is identical for all vehicles
g = model.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
model.addResourceDisposable(
    graph=g, consumptionType="E", weight=T, boundsType="V", lb=A, ub=B
)

# demand and capacity
model.addResourceDisposable(
    graph=g, consumptionType="V", weight=D, boundsType="V", lb=0, ub=q
)

# set partition constriants
for i in range(1, n - 1):
    model += flowty.xsum(x for x in g.vars if i == x.source) == 1

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

status = model.optimize()

# get the variable values
#
if (
    status == flowty.OptimizationStatus.Optimal
    or status == flowty.OptimizationStatus.Feasible
):
    for path in model.solutions[0].paths:
        print(f"Path {path.idx}")
        for var in path.vars:
            print(f" {var.name}")