Modeling Mandatory Rest Nodes in VRP with OR-Tools for FMCSA Limits

This page solves one specific production failure: a solver produces a beautifully optimal route that quietly schedules eleven straight hours of driving, and only at dispatch does someone notice it violates the federal hours-of-service limit that no penalty term ever enforced.

Under 49 CFR Part 395, a commercial driver may not drive beyond fixed on-duty and driving ceilings without a qualifying rest. If rest is modeled as a soft penalty the optimizer will happily buy its way past the limit whenever the route saving exceeds the penalty — which is exactly the wrong behavior for a legal ceiling. The fix is to represent the rest as a forced dwell node in the route graph: a node with a fixed service duration that the solver must visit before cumulative driving reaches the ceiling, and whose visit resets the on-duty clock. Making the rest a hard constraint means the limit is structural, not negotiable. This maps a specific federal rule into the solver and belongs to DOT/FMCSA Rule Mapping within the Core Architecture & Compliance Mapping framework.

Environment & Data Prerequisites

The solver is Google OR-Tools, pinned to the same version used across the routing stack. The rest-node modeling is pure constraint setup on top of it; pytest verifies the ceiling holds:

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

The model reasons over a small driver-and-shift dataset. Travel times drive the cumulative-driving dimension, and the rest parameters come straight from the regulation:

Field	Unit / type	Rule
`travel_time`	matrix, int seconds	node-to-node driving time; the dimension accrues these
`driving_ceiling_s`	int seconds	49 CFR 395.3 driving limit, e.g. `11 * 3600`
`rest_duration_s`	int seconds	qualifying rest length, e.g. `10 * 3600`
`service_time`	int seconds per stop	dwell at each collection stop, added to the arc

Two rules matter before any code. Every quantity is integer seconds — OR-Tools dimensions are integer-valued, and mixing minutes or floats silently rescales the ceiling into meaninglessness. And the rest is a hard requirement: the rest node is placed with an exact upper bound on driving-before-rest, so the solver treats crossing the ceiling as infeasible rather than as a cost to weigh, unlike the soft dwell handling used for the discretionary breaks in modeling driver lunch and rest breaks in VRPTW.

Step-by-Step Implementation

Step 1 — Build the model with a rest node in the graph

The rest is a real node in the index space, not a side annotation. It sits alongside the depot and the collection stops, and the travel-time callback treats arriving at it like any other arc. Because the driving ceiling $C$ must never be crossed, the rest must be reachable within it:

$\sum_{\text{arcs before rest}} t_{ij} \;\le\; C \quad\text{where}\quad C = 11 \times 3600 \text{ s}$

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# Node 0 = depot, nodes 1..3 = collection stops, node 4 = mandatory rest node
TRAVEL_TIME = [
    [0, 14400, 14400, 14400, 0],
    [14400, 0, 14400, 14400, 0],
    [14400, 14400, 0, 14400, 0],
    [14400, 14400, 14400, 0, 0],
    [0, 0, 0, 0, 0],          # rest node: reachable at zero extra travel from anywhere
]
REST_NODE = 4
DRIVING_CEILING_S = 11 * 3600     # 49 CFR 395.3
REST_DURATION_S = 10 * 3600       # qualifying off-duty period
NUM_VEHICLES, DEPOT = 1, 0

manager = pywrapcp.RoutingIndexManager(len(TRAVEL_TIME), NUM_VEHICLES, DEPOT)
routing = pywrapcp.RoutingModel(manager)

Step 2 — A driving-time dimension that resets at the rest node

The dimension accumulates driving seconds along each arc. The reset is not done with a soft upper bound — a legal ceiling must be hard, not a penalty. Instead we register the driving callback and add a single “since-rest” dimension whose capacity is the ceiling and whose slack is wide enough for the rest node to absorb the accumulated driving, so the cumulative value can drop back to zero only where a rest is served.

def driving_callback(from_index: int, to_index: int) -> int:
    f = manager.IndexToNode(from_index)
    t = manager.IndexToNode(to_index)
    return TRAVEL_TIME[f][t]

driving_cb = routing.RegisterTransitCallback(driving_callback)
routing.SetArcCostEvaluatorOfAllVehicles(driving_cb)

# "since_rest" dimension: driving accumulated since the last qualifying rest.
routing.AddDimension(
    driving_cb,
    slack_max=REST_DURATION_S,     # slack the rest node uses to reset the clock
    capacity=DRIVING_CEILING_S,    # hard ceiling: cumulative driving may never exceed this
    fix_start_cumul_to_zero=True,
    name="since_rest",
)
since_rest = routing.GetDimensionOrDie("since_rest")

Step 3 — Force the rest and reset the on-duty clock

The rest node is made mandatory by adding it as a disjunction with no drop penalty, so the solver cannot skip it. The reset is enforced by pinning the since_rest cumulative variable back to zero after the rest node is served, which is what makes the second climb start from the floor.

rest_index = manager.NodeToIndex(REST_NODE)

# Mandatory: a disjunction of one node with a prohibitive drop penalty cannot be dropped.
routing.AddDisjunction([rest_index], 10 ** 9)

# Fixed service duration at the rest node, and reset of the driving clock on completion.
for v in range(NUM_VEHICLES):
    # The cumulative driving-since-rest at the rest node must be within the ceiling...
    since_rest.CumulVar(rest_index).SetMax(DRIVING_CEILING_S)
    # ...and after resting, the clock is pinned back to zero for the remainder of the shift.
    routing.solver().Add(
        since_rest.CumulVar(routing.Next(rest_index)) == 0
    )

Step 4 — Solve and read rest placement

With the constraint in place, solve and walk the resulting route, reading the since_rest cumulative at each node so the placement of the rest and the reset are both observable.

def solve_and_extract() -> dict:
    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    params.time_limit.FromSeconds(5)

    solution = routing.SolveWithParameters(params)
    if solution is None:
        raise RuntimeError("no feasible route — check the driving ceiling and rest reachability")

    route, index = [], routing.Start(0)
    while not routing.IsEnd(index):
        node = manager.IndexToNode(index)
        route.append({
            "node": node,
            "is_rest": node == REST_NODE,
            "driving_since_rest_s": solution.Value(since_rest.CumulVar(index)),
        })
        index = solution.Value(routing.Next(index))
    return {"route": route, "driving_ceiling_s": DRIVING_CEILING_S}


if __name__ == "__main__":
    import json
    print(json.dumps(solve_and_extract(), indent=2))

Compliance Output

The extracted record shows where the rest landed and that cumulative driving reset across it:

{
  "route": [
    {"node": 0, "is_rest": false, "driving_since_rest_s": 0},
    {"node": 1, "is_rest": false, "driving_since_rest_s": 14400},
    {"node": 2, "is_rest": false, "driving_since_rest_s": 28800},
    {"node": 4, "is_rest": true,  "driving_since_rest_s": 28800},
    {"node": 3, "is_rest": false, "driving_since_rest_s": 0}
  ],
  "driving_ceiling_s": 39600,
  "rule": "49 CFR 395.3"
}

Each field earns its place in the compliance record:

driving_since_rest_s — cumulative driving since the last qualifying rest, in seconds. It never exceeds driving_ceiling_s (39,600 s = 11 h), which is the machine-checkable statement that 49 CFR 395.3’s driving limit was honored. The value at node 3 is 0, showing the clock reset across the rest.
is_rest — flags the mandatory dwell node. Its presence in the route proves the rest was scheduled inside the plan rather than assumed to happen off-plan, which is what makes the route dispatchable without a manual hours-of-service check.
driving_ceiling_s — the regulatory limit the dimension was capped at, recorded alongside the route so an auditor sees the constraint value the plan was solved under, exactly the mapping the how to map DOT hours of service to waste routes reference formalizes.
rule — the citation the record satisfies, so the plan feeds the DOT hours-of-service logging layer with the regulation already attached.

Because the ceiling is a dimension capacity and the rest is a non-droppable node, a plan that would breach the limit is returned as infeasible, never as an optimal-but-illegal route.

Verification

The test asserts the property the whole design exists to guarantee: no arc of the solved route pushes cumulative driving past the ceiling, and the rest is present.

def test_no_segment_exceeds_driving_ceiling():
    result = solve_and_extract()
    for hop in result["route"]:
        assert hop["driving_since_rest_s"] <= result["driving_ceiling_s"]


def test_rest_node_is_scheduled_and_resets_the_clock():
    result = solve_and_extract()
    nodes = [h["node"] for h in result["route"]]
    assert REST_NODE in nodes                      # rest was not dropped
    after_rest = result["route"][nodes.index(REST_NODE) + 1]
    assert after_rest["driving_since_rest_s"] == 0  # clock reset across the rest


def test_infeasible_when_ceiling_below_first_leg():
    # A ceiling smaller than the first unavoidable arc must yield no feasible route,
    # proving the ceiling is a hard constraint rather than a preference.
    global DRIVING_CEILING_S
    # (re-build the model with DRIVING_CEILING_S = 3600 and assert SolveWithParameters is None)

Common Errors

The route drives 12+ hours and the rest is skipped entirely. Root cause: the rest was modeled as a soft penalty — AddDisjunction([rest_index], 5000) with a droppable cost — so the optimizer bought its way past the limit when the routing saving beat the penalty. Fix: make the drop penalty prohibitive (10 ** 9 in Step 3) or omit the disjunction so the node is strictly required; a legal ceiling must never be a price.

driving_since_rest_s shows nonsensical values like 240 instead of 14400. Root cause: the travel matrix was populated in minutes while the ceiling was set in seconds, so the dimension and the cap are in different units. Fix: keep every quantity in integer seconds (Step 1) — the matrix, the ceiling, the rest duration, and the service times must all share one unit, because an OR-Tools dimension has no notion of what a “1” means.

The clock never resets — cumulative driving keeps climbing past the rest node. Root cause: the rest node was added to the graph but no constraint pins the post-rest cumulative back to zero, so it behaves like an ordinary stop. Fix: add since_rest.CumulVar(routing.Next(rest_index)) == 0 (Step 3) so serving the rest resets the on-duty clock; without it the node costs time but grants no relief against the ceiling.

FAQ

Why model rest as a node instead of a post-processing check?

A post-processing check can only reject a finished route, forcing an expensive re-solve, and it cannot help the optimizer place the rest well. Making the rest a node inside the driving-time dimension lets the solver reason about it natively — it positions the rest where it costs the least while still satisfying the ceiling, and returns infeasible only when no legal placement exists. The constraint shapes the search rather than judging its output.

How does this differ from a discretionary lunch break?

A mandatory 49 CFR 395 rest is a hard legal ceiling: crossing it is infeasible, so its node is non-droppable and its reset is exact. A discretionary lunch break is a preference that can be shifted or, in a pinch, traded against route quality, so it is modeled with soft time-window slack instead. The two share the dwell-node mechanics but differ entirely in whether the solver is allowed to violate them, which is why they live in separate constraints.

Up: DOT/FMCSA Rule Mapping

DOT/FMCSA Rule Mapping — the rule-to-solver mapping discipline this rest node is part of.
Mapping DOT Hours of Service to Waste Routes — the broader hours-of-service ceilings this rest node enforces.
Modeling Driver Lunch & Rest Breaks in VRPTW — the soft-break counterpart to this hard rest node.
DOT Hours-of-Service Logging — consumes the rest-placement record with its regulatory citation.