The Vehicle Routing Problem with Time Windows¶

This example illustrates a model for the Vehicle Routing Problem with Time Windows (VRPTW).

In the following, notation $c_*$ refers to the cost of entity $*$, and similarly $x_*$ refers to the variable, e.g., $c_e$ is the cost of edge $e$. Entity should be clear from context.

In the VRPTW the objective is to minimize the total cost of routing vehicles from a central depot to a set of customers. A vehicle must visit each customer exactly once arriving 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 open.

Let $g(V,E)$ be a 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 an end depot and $E$ is the set of 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_p^v \lambda_p = 1 & & v \in C \\ & \lambda_p \in \mathbb{B} && p \in P \end{aligned}$

where each path $p \in P$ is feasible in $g(V,E)$ (subject to time and demand constraints modeled as resources) with accumulated edge cost $c_p = \sum_{e \in p} c_e$ and $\alpha_p^v = \sum_{v \in p} 1$ expresses $p$'s visits to customer $v$.

The $\lambda$'s are not directly available for modelling.

The problem can in Flowty be modeled as

$\begin{aligned} \min & \sum_{e \in E} c_e x_e \\ \text{s.t. } & x_v = 1 & & v \in C \\ & 1 \leq x_k \leq |C| && k \in K\\ \end{aligned}$

with the graph and resource constraints described as above, and domain of each path binary. This model exploits that the vehicles are identical so that only one subproblem is needed, i.e., $K = \{0\}$. See the concepts section and modelling tour for more details.

Fetching data

To fetch the benchmark data check out the examples.

# Vehicle Routing Problem with Time Windows
import flowty
import fetch_vrptw
import sys

if len(sys.argv) == 2 and sys.argv[1] == "--help":
    print("Usage: python vrptw.py instanceName [logFile] [timeLimit]")
    sys.exit(1)

# from
# http://vrp.galgos.inf.puc-rio.br
# https://github.com/flowty/data/releases/tag/VRPTW
#
# C101...109, R101...112, RC101...108
# C201...208, R201...211, RC201...208
instance = "C101_25" if len(sys.argv) == 1 else sys.argv[1]
name, n, m, E, C, D, q, T, A, B, X, Y = fetch_vrptw.fetch(instance)

model = flowty.Model()
model.setParam("Master_Cut_UseSubsetRow", True)
model.setParam("PrimalHeu_DiveFrequency", 0)
model.setParam("MIPGap", 0)

# one graph with time and load resources, it is identical for all vehicles
time = {"E": [T], "V": [A, B]}, "time"
load = {"V": [D], "G": [q]}, "load"
timeRule = "Window", ["time"]
loadRule = "Capacity", ["load"]
rules = [timeRule, loadRule]

graph = model.addGraph(edges=E, edgeCosts=C, resources=[time, load], pathSense="S")
subproblem = model.addSubproblem(
    graph, source=0, target=n - 1, obj=0, lb=1, ub=n - 2, domain="B", rules=rules
)

# set partition constriants
for v in graph.vertices[1 : n - 1]:
    model += v == 1

if len(sys.argv) > 2:
    model.setParam("LogFilepath", sys.argv[2])
if len(sys.argv) > 3:
    model.setParam("TimeLimit", int(sys.argv[3]))

status = model.solve()
solution = model.getSolution()
if solution:
    print(f"Cost {round(solution.cost)}")
    for path in solution.paths:
        print(f"Path {path.subproblem.id}: {path.x}")
        for edge in path.edges:
            print(f"{edge}")