Routing and Time Windows
Routing couples assignment, ordering, and accumulated quantities. A route that visits every stop can still be infeasible because of vehicle capacity, depot rules, or arrival windows.
Prerequisites
Complete scheduling and resource allocation.
Learning goals
- Declare visit, vehicle, travel-time, waiting, and time-window units.
- Track accumulated time with a routing dimension.
- Validate visit coverage, arcs, and arrival windows from a returned route.
- Distinguish a feasible first solution from a globally optimal route.
Formulation before solver choice
One vehicle starts and ends at depot 0 and must visit stops 1, 2, and 3 exactly once. Travel times are integer minutes. Arrival must lie in window ; waiting is allowed. The model minimizes total travel minutes.
OR-Tools' routing engine combines constraint programming with routing-specific search. Here a fixed PATH_CHEAPEST_ARC first-solution strategy and a one-solution limit make the teaching run reproducible. ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED means a solution exists but search stopped at the declared limit; it is deliberately not relabeled as optimal.
Worked example
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
travel = [[0, 2, 4, 3],
[2, 0, 2, 4],
[4, 2, 0, 2],
[3, 4, 2, 0]] # minutes
windows = [(0, 0), (2, 4), (4, 7), (6, 10)]
manager = pywrapcp.RoutingIndexManager(len(travel), 1, 0)
routing = pywrapcp.RoutingModel(manager)
def transit(from_index, to_index):
return travel[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]
transit_index = routing.RegisterTransitCallback(transit)
routing.SetArcCostEvaluatorOfAllVehicles(transit_index)
routing.AddDimension(transit_index, 10, 20, True, "Time")
time_dimension = routing.GetDimensionOrDie("Time")
for node, (lower, upper) in enumerate(windows):
time_dimension.CumulVar(manager.NodeToIndex(node)).SetRange(lower, upper)
parameters = pywrapcp.DefaultRoutingSearchParameters()
parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
parameters.solution_limit = 1
solution = routing.SolveWithParameters(parameters)
status_names = {
1: "ROUTING_SUCCESS",
2: "ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED",
3: "ROUTING_FAIL",
4: "ROUTING_FAIL_TIMEOUT",
5: "ROUTING_INVALID",
6: "ROUTING_INFEASIBLE",
7: "ROUTING_OPTIMAL",
}
if solution is None:
raise RuntimeError(status_names.get(routing.status(), str(routing.status())))
route, arrivals = [], []
index = routing.Start(0)
while not routing.IsEnd(index):
route.append(manager.IndexToNode(index))
arrivals.append(solution.Value(time_dimension.CumulVar(index)))
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
arrivals.append(solution.Value(time_dimension.CumulVar(index)))
cost = sum(travel[a][b] for a, b in zip(route, route[1:]))
windows_ok = all(windows[node][0] <= arrival <= windows[node][1]
for node, arrival in zip(route[:-1], arrivals[:-1]))
print(f"status={status_names[routing.status()]} route={route} travel_minutes={cost}")
print(f"arrival_minutes={arrivals} windows_respected={windows_ok}")
print("optimality_proven=False termination=solution_limit_1")
Expected output:
status=ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED route=[0, 1, 2, 3, 0] travel_minutes=9
arrival_minutes=[0, 2, 4, 6, 9] windows_respected=True
optimality_proven=False termination=solution_limit_1
The returned route is feasible: each customer appears once, every arc exists, and each customer arrival lies inside its window. The first-solution termination status is evidence of feasibility only. For this four-node instance, the verifier enumerates all six customer orders and finds the same cost of 9, but that separate exhaustive check—not the routing status—establishes the small-instance optimum.
Limitations and common mistakes
- A solution window is not an observed arrival or a guarantee under traffic uncertainty.
- Travel-time matrices can be asymmetric and time-dependent; this tiny matrix is neither.
- Service duration, capacity, breaks, multiple depots, dropped visits, and road restrictions are omitted.
- A time or solution limit can return a useful feasible route without an optimality certificate.
- Vehicle-routing problems can become intractable quickly; this result makes no production-scale promise.
Practice
Tighten stop 3's window to [5, 5]. Enumerate every visit order and distinguish “no feasible order in this fixed one-vehicle model” from “the real delivery is impossible.”
Next steps
Use logical constraints and explicit termination cases in constraint programming.
Primary sources
Checked 2026-10-19: Google OR-Tools 9.15, vehicle routing with time windows, routing options and status meanings, and vehicle-routing scale limitations.