Vehicle routing with time windows

A fleet leaves one depot to deliver to 100 customers. Each customer has a demand, a time window in which delivery must start, and a service time. A vehicle carries no more than its capacity, waits when it is early, and must be back before the depot closes. The total distance driven is as small as possible.

The data is Solomon's c101, a standard benchmark instance (Solomon, 1987): 25 vehicles of capacity 200 and 100 customers in clusters. Its best known solution drives 827.3 with 10 vehicles.

python vehicle_routing.py

The script solves the morning's 95 orders for 30 seconds and explains the score. Then five late orders arrive, and the script fits them in without changing the routes already loaded.

The model

A vehicle's visits is a list variable: the solver chooses which customers each vehicle serves, and in which order. A visit's arrival and departure are cascading shadows. When a route changes, they are recomputed from the change to the end of the route.

def arrival_time(visit: "Visit", previous: "Visit | None") -> int:
    """At the head of a route: when the depot opens plus the drive from it.
    Otherwise: when the previous visit is done plus the drive from there."""
    return (
        visit.vehicle.ready + visit.times[0]
        if previous is None
        else previous.departure + previous.times[visit.node]
    )


@planning_entity
@dataclass
class Visit:
    x: int
    y: int
    demand: int
    ready: int  # delivery may start from …
    due: int  # … and must start by
    service: int
    node: int  # this customer's number; the depot is 0
    times: list[int]  # the drive from here to each node, by node number
    vehicle: Annotated["Vehicle | None", InverseRelationShadow] = None
    previous: Annotated["Visit | None", PreviousElementShadow] = None
    next: Annotated["Visit | None", NextElementShadow] = None
    arrival: Annotated[int | None, CascadingShadow(arrival_time)] = None
    departure: Annotated[
        int | None, CascadingShadow(lambda visit, previous: max(visit.arrival, visit.ready) + visit.service)
    ] = None

Times and distances are integers in tenths: a distance is floor(10 × the straight-line distance), and a vehicle drives one unit per unit of time. Each visit carries its own row of drives to every node. A row cannot yet be read through a reference (visit.previous.times[…]). The model therefore uses the fact that c101's distances are symmetric, and reads its own row: visit.times[visit.previous.node]. A model with asymmetric drives can keep the matrix as a problem fact's list, which can be read through references.

The constraints

        # Hard: delivery starts by the customer's due time — penalized by the lateness.
        f.for_each(Visit)
        .filter(lambda visit: visit.arrival > visit.due)
        .penalize(HardSoftScore.ONE_HARD, lambda visit: visit.arrival - visit.due)
        .as_constraint("Arrival after due time"),

The others are in vehicle_routing.py. They are the terms of Heusor's own Rust implementation of this problem (the typed VRPTW), term for term:

Constraint	Level	What one match is	Typed VRPTW term
Visit assigned	hard	a customer on no route: −1	unassigned
Vehicle capacity	hard	a vehicle whose load exceeds its capacity: −(load − capacity)	overload
Arrival after due time	hard	a visit reached after its due time: −(arrival − due)	time-window lateness
Back after depot closes	hard	a route's last visit, when the vehicle returns after the depot closes: −(return − close)	depot-return lateness
Distance	soft	a visit: −(its drive in, plus the drive home if it is last)	distance

This follows Solomon's rule: delivery must start by the due time. The Timefold vehicle-routing quickstart instead requires the service to finish by its end time, and has no depot-return constraint. Its scores are therefore not comparable with these.

Solving and explaining

heusor.score returns each constraint's share of the score. From one run of the script (30 s on the morning's 95 orders, release build, an Intel i7-1255U):

Score: HardSoftScore(hard=0, soft=-8186)
  Visit assigned             HardSoftScore(hard=0, soft=0)
  Vehicle capacity           HardSoftScore(hard=0, soft=0)
  Arrival after due time     HardSoftScore(hard=0, soft=0)
  Back after depot closes    HardSoftScore(hard=0, soft=0)
  Distance                   HardSoftScore(hard=0, soft=-8186)
  10 vehicles, 818.6 distance

Late orders

The morning's plan covers 95 orders. Five more arrive after the first vehicles are loaded. The loaded vehicles' routes are pinned (PlanningPin on the vehicle), so the solver leaves them exactly as they are. The late orders go into the other routes or into spare vehicles:

    plan = copy.deepcopy(planned)
    plan.visits += copy.deepcopy(late)
    for vehicle in [v for v in plan.vehicles if v.visits][:keep]:
        vehicle.pinned = True
    return heusor.solve(plan, define_constraints, time_limit=time_limit, step_limit=step_limit, seed=seed)

In the run above:

After five late orders, with the first five routes already loaded:
Score: HardSoftScore(hard=0, soft=-8608)
  Visit assigned             HardSoftScore(hard=0, soft=0)
  Vehicle capacity           HardSoftScore(hard=0, soft=0)
  Arrival after due time     HardSoftScore(hard=0, soft=0)
  Back after depot closes    HardSoftScore(hard=0, soft=0)
  Distance                   HardSoftScore(hard=0, soft=-8608)
  11 vehicles, 860.8 distance
  Loaded, unchanged: vehicles [0, 1, 2, 3, 4]
  Order 96 → vehicle 10
  Order 97 → vehicle 10
  Order 98 → vehicle 10
  Order 99 → vehicle 10
  Order 100 → vehicle 10

The five late customers lie 2 to 9 units from customers 93 and 95, on vehicle 10's route, which is not loaded. All five join that route, and the five loaded routes stay as they were.

In this run the pins cost little. The same 10 s repair with nothing pinned drove 858.5, also with 11 vehicles, against 860.8 with five routes pinned. Both are above the 827.3 of the best plan for all 100 customers. A 10 s repair of a 95-order plan is not a re-plan of all 100.

How it is verified

test_vehicle_routing_example.py holds the example to what this page says.

• The typed VRPTW. c101_typed.json records what Heusor's typed (Rust) VRPTW does on c101 with its own solver configuration: the configuration, the best score, the step count and every route. A test in Heusor's own Rust suite recomputes the record and fails if the file is stale, or if this folder's c101.txt differs from the Rust implementation's copy. Solved with that configuration, this Python model returns the same score, the same step count and the same routes.
• For this to hold, the visit's first fields are in the typed domain's order: x, y and demand. The configuration's nearby moves read the coordinates by position, and its construction reads the demand.
• A plain-Python scorer. It is written from the table above, walks every route itself, and computes distances from the coordinates. Heusor's score, each constraint's share, and each vehicle's and visit's matches and cost are equal to it in these cases:
• random routes;
• crowded routes (100 customers on 3 vehicles);
• routes with a fifth of the customers unrouted;
• a solved plan.
• Late orders. The test pins 5 routes, then pins every route in use. In the second case the late orders must take spare vehicles, although an existing route is cheaper (an earlier version's construction put them on a pinned route). It asserts that no loaded route changes, that every order is routed, that no hard constraint is broken, and that the plan it was given does not change.
• This page. Every python block here is a verbatim part of vehicle_routing.py, and the table names exactly the constraints that the code defines, in their order.

Measured on one machine

Release build, Intel i7-1255U, seed 0, all 100 customers. These are single runs, not benchmarks:

Solve time	Score
construction and one step	0hard/−10 236soft (0.12 s)
5 s	0hard/−8 475soft
30 s	0hard/−8 273soft: 827.3 with 10 vehicles, the best known

Download

• c101.txt
• vehicle_routing.py