Modeling Driver Lunch & Rest Breaks in VRPTW with OR-Tools

This page solves one modeling gap that turns an optimal plan into an illegal one: the solver schedules a driver straight through the shift with no lunch and no federally mandated rest break, producing a route that looks efficient and cannot legally be driven.

A vehicle routing problem with time windows (VRPTW) that ignores breaks will happily pack service into every minute, then hand a driver a plan that violates both a labor meal period and the 49 CFR 395 hours-of-service rest rule. The fix is not a post-hoc gap inserted by hand — it is a first-class constraint. OR-Tools models a break as a time interval attached to the vehicle’s time dimension: it consumes schedule, pushes later stops out, and must fall inside an allowed window, but it services no node. This is the break-modeling layer of the Time Window Constraints sub-system, and it composes with the strict service windows covered in Solving VRPTW with Strict Pickup Windows — the same time dimension carries both.

Environment & Data Prerequisites

Break modeling needs only the pinned solver and the standard library:

python -m pip install \
  ortools==9.11.4210 \
  pytest==8.2.0

Two data shapes drive the solve: the service stops with their windows, and the per-vehicle break rules. All times are whole minutes from shift start as int, matching the integer arithmetic of the time dimension.

Field	Type	Unit / range	Role
`stop_id`	`str`	e.g. `BIN_03`	audit key
`service_min`	`int`	≥ 0	dwell consumed at the stop
`window`	`[int, int]`	minutes, `start ≤ end`	hard arrival bound on the Time dimension
`break.earliest_start`	`int`	minutes	earliest legal break start
`break.latest_start`	`int`	minutes	latest legal break start
`break.duration_min`	`int`	> 0	mandatory break length

A break rule is a legal envelope, not a fixed time: a 30-minute meal that must start between minute 210 and 270 gives the solver freedom to place it where it least disrupts service, while still guaranteeing it happens and lasts long enough.

Step-by-Step Implementation

Step 1 — Typed stops and break rules

Model the two inputs as frozen dataclasses so a malformed window or a zero-duration break fails loudly at construction rather than silently producing a break that consumes no time.

from __future__ import annotations
from dataclasses import dataclass
import math


@dataclass(frozen=True)
class Stop:
    stop_id: str
    lat: float
    lon: float
    service_min: int
    window: tuple[int, int]

    def __post_init__(self) -> None:
        if self.window[1] < self.window[0]:
            raise ValueError(f"{self.stop_id}: window end precedes start")


@dataclass(frozen=True)
class BreakRule:
    label: str
    earliest_start: int
    latest_start: int
    duration_min: int

    def __post_init__(self) -> None:
        if self.duration_min <= 0:
            raise ValueError(f"{self.label}: break duration must be positive")
        if self.latest_start < self.earliest_start:
            raise ValueError(f"{self.label}: latest_start precedes earliest_start")


STOPS: list[Stop] = [
    Stop("DEPOT",  40.7128, -74.0060, 0, (0, 600)),
    Stop("BIN_01", 40.7180, -74.0020, 8, (60, 240)),
    Stop("BIN_02", 40.7205, -74.0110, 8, (60, 300)),
    Stop("BIN_03", 40.7090, -74.0150, 8, (120, 360)),
    Stop("BIN_04", 40.7060, -74.0030, 8, (180, 420)),
    Stop("BIN_05", 40.7220, -73.9950, 8, (240, 480)),
    Stop("BIN_06", 40.7040, -74.0120, 8, (300, 540)),
]

# One vehicle, one mandatory 30-minute meal break starting between minute 210 and 270
BREAK_RULES: dict[int, list[BreakRule]] = {
    0: [BreakRule("lunch", earliest_start=210, latest_start=270, duration_min=30)],
}
SPEED_M_PER_MIN = 400

Step 2 — Build the time matrix and register the Time dimension

Travel time plus service dwell is the transit the time dimension accumulates. A break must live on this dimension, so it has to exist before any break is attached.

def build_time_matrix(stops: list[Stop]) -> list[list[int]]:
    n = len(stops)
    t = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            mean_lat = math.radians((stops[i].lat + stops[j].lat) / 2)
            dlat = stops[i].lat - stops[j].lat
            dlon = (stops[i].lon - stops[j].lon) * math.cos(mean_lat)
            metres = 111_320 * math.hypot(dlat, dlon)
            t[i][j] = int(metres / SPEED_M_PER_MIN)
    return t

Step 3 — Attach break intervals to the time dimension

This is the crux. SetBreakIntervalsOfVehicle takes three arguments: the list of break interval variables, the vehicle index, and node_visit_transits — a vector of length routing.Size() giving the service time consumed at each index. The solver needs the visit transits so it can reason about where in the route a break fits without overlapping a service dwell. The break itself is a FixedDurationIntervalVar: a start range, a fixed duration, and a performed flag of False meaning mandatory (it must be performed).

The 49 CFR 395 rest rule requires a 30-minute break before eight cumulative hours of driving; a local labor meal period imposes its own window. Both are expressed as the start-range envelope below.

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def solve_with_breaks(stops: list[Stop], num_vehicles: int = 1,
                      horizon: int = 600, time_limit_s: int = 5):
    n = len(stops)
    tmat = build_time_matrix(stops)
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, 0)
    routing = pywrapcp.RoutingModel(manager)

    def time_cb(a: int, b: int) -> int:
        i, j = manager.IndexToNode(a), manager.IndexToNode(b)
        return tmat[i][j] + stops[i].service_min

    tc = routing.RegisterTransitCallback(time_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(tc)
    routing.AddDimension(tc, horizon, horizon, False, "Time")
    time_dim = routing.GetDimensionOrDie("Time")

    for i, s in enumerate(stops):
        if i == 0:                                   # depot has no service window
            continue
        time_dim.CumulVar(manager.NodeToIndex(i)).SetRange(*s.window)

    # node_visit_transits: service time consumed at every index (length == routing.Size())
    node_visit_transits = [0] * routing.Size()
    for idx in range(routing.Size()):
        node_visit_transits[idx] = stops[manager.IndexToNode(idx)].service_min

    solver = routing.solver()
    vehicle_breaks: dict[int, list] = {}
    for v in range(num_vehicles):
        intervals = []
        for rule in BREAK_RULES.get(v, []):
            bi = solver.FixedDurationIntervalVar(
                rule.earliest_start, rule.latest_start,   # start range
                rule.duration_min,                         # fixed duration
                False,                                     # mandatory (must be performed)
                f"brk_{v}_{rule.label}",
            )
            intervals.append(bi)
            routing.AddIntervalToAssignment(bi)            # keep it in the solution
        if intervals:
            time_dim.SetBreakIntervalsOfVehicle(intervals, v, node_visit_transits)
            vehicle_breaks[v] = intervals

    p = pywrapcp.DefaultRoutingSearchParameters()
    p.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    p.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    p.time_limit.FromSeconds(time_limit_s)

    sol = routing.SolveWithParameters(p)
    if sol is None:
        return None
    return routing, manager, time_dim, vehicle_breaks, sol

Step 4 — Read the break placement out of the solution

Because each break interval was registered with AddIntervalToAssignment, its solved start, duration, and end are readable from the assignment with StartValue, DurationValue, and EndValue.

def read_schedule(stops, num_vehicles, solved) -> dict:
    routing, manager, time_dim, vehicle_breaks, sol = solved
    out = {"routes": [], "breaks": []}
    for v in range(num_vehicles):
        idx, leg = routing.Start(v), []
        while not routing.IsEnd(idx):
            node = manager.IndexToNode(idx)
            leg.append({"stop": stops[node].stop_id,
                        "arrive_min": sol.Value(time_dim.CumulVar(idx))})
            idx = sol.Value(routing.NextVar(idx))
        out["routes"].append({"vehicle": v, "legs": leg})
        for bi in vehicle_breaks.get(v, []):
            out["breaks"].append({
                "vehicle": v,
                "label": bi.Name(),
                "start_min": sol.StartValue(bi),
                "duration_min": sol.DurationValue(bi),
                "end_min": sol.EndValue(bi),
            })
    return out


if __name__ == "__main__":
    import json
    solved = solve_with_breaks(STOPS)
    print(json.dumps(read_schedule(STOPS, 1, solved), indent=2))

Compliance Output

A solved plan reports each vehicle’s break placement alongside its route. On the example instance the mandatory lunch lands at minute 210 — the earliest legal start — for its full 30 minutes:

{
  "breaks": [
    {
      "vehicle": 0,
      "label": "brk_0_lunch",
      "start_min": 210,
      "duration_min": 30,
      "end_min": 240
    }
  ]
}

Each field is load-bearing for a defensible driver log:

start_min — the solved break start, which must fall within the rule’s [earliest_start, latest_start] envelope. Under the hours-of-service rule (49 CFR 395.3(a)(3)(ii)), a driver must take a 30-minute break before eight cumulative hours of driving; the envelope encodes that ceiling, and the solved start proves the break happened in time.
duration_min — the break length actually scheduled. It must equal the rule’s mandated duration; a break shorter than 30 minutes does not satisfy the federal rest requirement, and a local meal-period statute (for example a state labor code’s 30-minute unpaid meal for a shift over six hours) imposes the same floor.
end_min — start + duration, the point the driver resumes service; downstream stop arrivals are all pushed past it, which is what makes the plan realistic rather than optimistic.

These break records reconcile against the duty-status accounting owned by the DOT/FMCSA Rule Mapping sub-system, and mandatory rest nodes — a distinct pattern where the break is a physical location rather than an in-place interval — are modeled in Modeling Mandatory Rest Nodes in VRP. The full duty log those fields feed is generated by the DOT Hours-of-Service Logging system.

Verification

The test proves the property that keeps the plan legal: a break of the mandated duration is scheduled, and it falls entirely inside its allowed window.

def test_break_of_required_duration_falls_in_window():
    solved = solve_with_breaks(STOPS)
    assert solved is not None                     # a feasible plan with the break exists
    schedule = read_schedule(STOPS, 1, solved)

    lunch = next(b for b in schedule["breaks"] if b["label"] == "brk_0_lunch")
    rule = BREAK_RULES[0][0]

    # duration matches the mandate exactly
    assert lunch["duration_min"] == rule.duration_min
    # start is inside the legal envelope
    assert rule.earliest_start <= lunch["start_min"] <= rule.latest_start
    # the whole break fits before the latest legal completion
    assert lunch["end_min"] == lunch["start_min"] + rule.duration_min


def test_break_is_mandatory_not_dropped():
    solved = solve_with_breaks(STOPS)
    schedule = read_schedule(STOPS, 1, solved)
    labels = {b["label"] for b in schedule["breaks"]}
    assert "brk_0_lunch" in labels                # a mandatory break can never be omitted

Common Errors

SolveWithParameters returns None once a break is added. Root cause: the break window and the service windows are jointly infeasible — a 30-minute break that must start by minute 270 collides with tight stop windows that leave no idle slot, so no legal schedule exists. Fix: widen the break’s [earliest_start, latest_start] envelope, relax the tightest service window, or add a vehicle so the driver has slack to break; a break is a hard constraint and the solver will report infeasibility rather than skip it.

node_visit_transits length mismatch raises inside SetBreakIntervalsOfVehicle. Root cause: the transits vector was built with one entry per node (len(stops)) instead of one per index (routing.Size()), so the solver receives a vector that does not align with its internal index space. Fix: size the vector to routing.Size() and fill it by mapping each index back with manager.IndexToNode(idx), exactly as Step 3 does — the two counts differ whenever there is more than one vehicle or a non-trivial depot layout.

The break appears in the output but never delays any stop. Root cause: the break was created with a duration of 0 — a zero-length interval satisfies “a break exists” while consuming no schedule, so downstream arrivals are unaffected and the plan is silently non-compliant. Fix: set a positive duration_min on every FixedDurationIntervalVar (the BreakRule.__post_init__ guard rejects zero), and assert in tests that duration_min equals the mandated length rather than merely that a break is present.

FAQ

Why model a break as an interval instead of a dummy node with a service time?

A dummy node forces a fixed location and a fixed position in the route, and it distorts the distance objective because the solver must travel to it. A break interval consumes time on the vehicle’s schedule wherever it best fits within its legal window, services no location, and adds nothing to distance — which is exactly the semantics of a lunch or rest break. Use a rest node only when the break genuinely must occur at a physical place, such as a mandated relief yard.

Can one vehicle carry more than one break?

Yes. SetBreakIntervalsOfVehicle takes a list, so a long shift can carry a mid-morning rest and an afternoon meal as separate FixedDurationIntervalVar entries, each with its own window and duration. The solver places all of them on the same time dimension and pushes service around every one, so a split shift stays both legal and feasible.

Up: Time Window Constraints

Time Window Constraints — the hard-window sub-system this break layer extends
Solving VRPTW with Strict Pickup Windows — the strict service windows the same time dimension carries
Modeling Mandatory Rest Nodes in VRP — the location-based alternative to an in-place break interval
DOT Hours-of-Service Logging — the duty log these break records feed