Skip to content

Vehicle Routing Problem with Time Windows

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. Vehicles have a maximum capacity.

min⁡∑p∈Pcpλps.t. ∑p∈Pαpvλp=1v∈Cλp∈Bp∈P \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 subject to time and demand resources. Vehicles are identical so only one subproblem is needed.

import flowty

model = flowty.Model()

# 4 customers (1-4) + depot split into start (0) and end (5)
n = 6
edges = [
    (0, 1), (0, 2), (0, 3), (0, 4),
    (1, 2), (1, 3), (1, 4), (1, 5),
    (2, 1), (2, 3), (2, 4), (2, 5),
    (3, 1), (3, 2), (3, 4), (3, 5),
    (4, 1), (4, 2), (4, 3), (4, 5),
]
costs = [
    10, 15, 20, 25,
    8, 12, 18, 10,
    8, 10, 14, 15,
    12, 10, 8, 20,
    18, 14, 8, 25,
]

# travel times (same structure as costs)
T = [
    3, 4, 6, 7,
    2, 4, 5, 3,
    2, 3, 4, 4,
    4, 3, 2, 6,
    5, 4, 2, 7,
]

# time windows [earliest, latest] per vertex
A = [0, 2, 3, 5, 4, 0]
B = [100, 10, 12, 15, 14, 100]

# demands per vertex and vehicle capacity
D = [0, 3, 2, 4, 3, 0]
q = 8

time = {"E": [T], "V": [A, B]}, "time"
load = {"V": [D], "G": [q]}, "load"
timeRule = "Window", ["time"]
loadRule = "Capacity", ["load"]

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

# each customer visited exactly once
for v in graph.vertices[1 : n - 1]:
    model += v == 1

status = model.solve()
solution = model.getSolution()
if solution:
    print(f"Cost: {solution.cost}")
    for path in solution.paths:
        print(f"Route {path.subproblem.id}: {path.x}")
        for edge in path.edges:
            print(f"  {edge.source} -> {edge.target}")