Skip to main content

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 tijt_{ij} are integer minutes. Arrival aia_i must lie in window [li,ui][l_i,u_i]; 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.