OR-Tools v9.9 regression: incorrect negative transit variables (with modulo > capacity) handling in heterogeneous VRP

[Yamp]

What version of OR-Tools and what language are you using?
Version: v9.9 only.
Language: Python

Routing Solver

Macos 13.4

I am using code like this to solve heterogeneous VRP with reloads. Like in this example
https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py
But my problem has different capacities for different vehicles.

  self.r.AddDimensionWithVehicleCapacity(
      evaluator_index=self.c[name],
      slack_max=int(self.p.max_c[index]),  # we are unloading max_cap but adding some slack
      vehicle_capacities=self.p.max_capacities[:, index].astype(int).tolist(),
      fix_start_cumul_to_zero=True,
      name="max_capacities" + str(index),
  )

Making negative capacities at reloads equal to the biggest possible capacity of my vehicle and then adding slack to landfills.
At version 9.8 it works, but at 9.9 it does not accept the initial solution and does not use landfills for vehicles with non-maximum capacities.

After some debugging, I realized that reload capacities say -100 are considered out of bounds for vehicles with maximum capacity say 80. So it cannot use reloads and ignores the initial solution. How to solve the same problem in the 9.9 version I don't know. I would consider this a bug.

[cyril23]

We can confirm this bug still exists in OR-Tools 9.14.6206 (latest) and have identified the exact root cause through source code analysis.

Root Cause

Commit: 847cfc9 (Dec 1, 2023)
Function: FinalizeAllowedVehicles() in ortools/constraint_solver/routing.cc
Problem: Incorrectly removes vehicles from allowed_vehicles_ sets when dimensions use negative transit values

Bug Mechanism

The function checks if abs(transit) > capacity for unary dimensions and removes vehicles that fail this check. This is incorrect for:

1. Reload dimensions (@Yamp 's original report): Negative values at landfills/depots
2. CARGO_LOAD dimensions (our use case): Negative constants used for cumulative load tracking

In our multi-class pickup/delivery scenario:

• CARGO_LOAD dimension uses transit = -max(capacities) for all nodes (e.g., -70,000)
• Smaller vehicles (capacity 50,000) fail the check: abs(-70,000) > 50,000
• These vehicles get incorrectly excluded from all nodes
• Solver is forced to use only the largest vehicles, dropping stops instead

Version Bisection

Comprehensive testing across OR-Tools versions 9.7 through 9.14:

Version	Status
9.7.2996	✅ Works (0 drops, multiple vehicle classes used)
9.8.3296	✅ Works (0 drops, multiple vehicle classes used)
9.9.3963	❌ Broken (14+ drops, only largest vehicles used)
9.10.4067	❌ Broken
9.11.4210	❌ Broken
9.12.4544	❌ Broken
9.13.4784	❌ Broken
9.14.6206	❌ Broken (current)

Regression introduced: Between v9.8.3296 and v9.9.3963

Standalone Reproduction Script

Click to expand test_ortools_version_standalone_codex.py

#!/usr/bin/env python3
"""
Standalone regression reproducer for the OR-Tools multi-class VRP bug.

Run this script with different OR-Tools versions to observe the behaviour:

    python3 -m pip install ortools==9.8.3296
    python3 test_ortools_version_standalone_codex.py
    # -> 3 tours, 0 dropped stops

    python3 -m pip install ortools==9.12.4544
    python3 test_ortools_version_standalone_codex.py
    # -> 1 tour, 13 dropped stops
"""

from __future__ import annotations

from dataclasses import dataclass

import ortools
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2


# OSRM travel-time matrix (seconds, rounded to int).
TIME_MATRIX = [
    [0, 0, 10, 10, 145, 206, 440, 599, 2354, 3772, 4567, 3740, 3740, 3878, 2086, 3070, 2075, 1361, 2651, 1858, 1232, 1576, 2338, 2296, 4111, 3216, 3215, 2451, 2257, 1578, 597, 597, 597, 597],
    [0, 0, 10, 10, 145, 206, 440, 599, 2354, 3772, 4567, 3740, 3740, 3878, 2086, 3070, 2075, 1361, 2651, 1858, 1232, 1576, 2338, 2296, 4111, 3216, 3215, 2451, 2257, 1578, 597, 597, 597, 597],
    [34, 34, 0, 0, 135, 196, 430, 589, 2343, 3762, 4557, 3729, 3729, 3868, 2076, 3060, 2065, 1351, 2641, 1848, 1222, 1565, 2328, 2286, 4101, 3206, 3205, 2441, 2246, 1567, 587, 587, 587, 587],
    [34, 34, 0, 0, 135, 196, 430, 589, 2343, 3762, 4557, 3729, 3729, 3868, 2076, 3060, 2065, 1351, 2641, 1848, 1222, 1565, 2328, 2286, 4101, 3206, 3205, 2441, 2246, 1567, 587, 587, 587, 587],
    [141, 141, 151, 151, 0, 210, 396, 636, 2238, 3657, 4452, 3624, 3624, 3763, 1971, 2955, 1960, 1246, 2536, 1743, 1197, 1541, 2303, 2261, 4076, 3182, 3180, 2416, 2222, 1543, 619, 619, 619, 619],
    [196, 196, 206, 206, 181, 0, 343, 531, 2390, 3790, 4584, 3757, 3757, 3895, 2103, 3087, 2092, 1378, 2668, 1884, 1145, 1488, 2251, 2208, 4023, 3129, 3128, 2364, 2169, 1490, 530, 530, 530, 530],
    [410, 410, 420, 420, 397, 352, 0, 435, 2279, 3660, 4455, 3627, 3627, 3766, 1974, 2958, 1963, 1249, 2539, 1877, 1015, 1359, 2121, 2079, 3894, 3000, 2998, 2234, 2040, 1361, 540, 540, 540, 540],
    [560, 560, 570, 570, 610, 522, 475, 0, 2536, 3916, 4711, 3884, 3884, 4022, 2230, 3214, 2219, 1505, 2784, 1970, 1272, 1615, 2378, 2335, 4150, 3256, 3255, 2490, 2296, 1617, 634, 634, 634, 634],
    [2345, 2345, 2355, 2355, 2234, 2393, 2248, 2513, 0, 1531, 2380, 2328, 2328, 2276, 1550, 2519, 1560, 2156, 3328, 3406, 2457, 2430, 2700, 2658, 2742, 1665, 1664, 1419, 1836, 1785, 2602, 2602, 2602, 2602],
    [3779, 3779, 3789, 3789, 3668, 3813, 3668, 3933, 1522, 0, 1459, 1607, 1607, 1555, 2103, 1983, 2092, 3061, 4270, 4297, 3750, 3723, 3752, 3710, 1255, 1422, 1421, 2200, 2617, 3078, 3853, 3853, 3853, 3853],
    [4615, 4615, 4625, 4625, 4504, 4649, 4504, 4769, 2376, 1445, 0, 1236, 1236, 1363, 2939, 2219, 2928, 3898, 5106, 5134, 4750, 4723, 4993, 4950, 2700, 2805, 2804, 3583, 4000, 4077, 4689, 4689, 4689, 4689],
    [3795, 3795, 3805, 3805, 3684, 3829, 3684, 3949, 2320, 1588, 1251, 0, 0, 205, 2109, 1050, 2100, 3077, 4279, 4313, 4096, 4439, 4937, 4894, 2843, 2749, 2748, 3527, 3944, 4021, 3869, 3869, 3869, 3869],
    [3795, 3795, 3805, 3805, 3684, 3829, 3684, 3949, 2320, 1588, 1251, 0, 0, 205, 2109, 1050, 2100, 3077, 4279, 4313, 4096, 4439, 4937, 4894, 2843, 2749, 2748, 3527, 3944, 4021, 3869, 3869, 3869, 3869],
    [3946, 3946, 3956, 3956, 3835, 3980, 3835, 4100, 2243, 1511, 1408, 202, 202, 0, 2173, 1114, 2164, 3228, 4343, 4464, 4247, 4590, 4860, 4817, 2766, 2672, 2671, 3450, 3867, 3944, 4020, 4020, 4020, 4020],
    [2200, 2200, 2210, 2210, 2089, 2234, 2089, 2354, 1507, 2164, 2959, 2131, 2131, 2228, 0, 1168, 108, 1483, 2750, 2719, 2501, 2845, 3607, 3565, 3419, 3092, 3091, 2926, 3343, 2847, 2274, 2274, 2274, 2274],
    [3146, 3146, 3156, 3156, 3035, 3180, 3035, 3300, 2497, 1924, 2319, 1112, 1112, 1201, 1107, 0, 1098, 2428, 3277, 3664, 3447, 3790, 4553, 4510, 3179, 3010, 3009, 3788, 4205, 3792, 3220, 3220, 3220, 3220],
    [2147, 2147, 2157, 2157, 2037, 2182, 2037, 2302, 1499, 2111, 2906, 2078, 2078, 2177, 86, 1118, 0, 1430, 2697, 2666, 2449, 2792, 3555, 3512, 3366, 3039, 3038, 2918, 3334, 2794, 2221, 2221, 2221, 2221],
    [1363, 1363, 1373, 1373, 1252, 1397, 1252, 1517, 2151, 3054, 3848, 3021, 3021, 3159, 1368, 2351, 1356, 0, 1342, 1717, 1664, 2007, 2770, 2728, 4309, 3620, 3618, 2883, 2688, 2009, 1448, 1448, 1448, 1448],
    [2616, 2616, 2626, 2626, 2505, 2668, 2551, 2795, 3336, 4317, 5111, 4281, 4281, 4369, 2672, 3310, 2661, 1376, 0, 1592, 2963, 3306, 4069, 4026, 5572, 4947, 4946, 4182, 3987, 3308, 2280, 2280, 2280, 2280],
    [1795, 1795, 1805, 1805, 1685, 1848, 1892, 1974, 3291, 4180, 4974, 4147, 4147, 4285, 2493, 3477, 2482, 1743, 1622, 0, 2675, 3019, 3781, 3739, 5434, 4660, 4658, 3894, 3700, 3021, 1459, 1459, 1459, 1459],
    [1184, 1184, 1194, 1194, 1154, 1109, 964, 1229, 2392, 3733, 4710, 4075, 4075, 4214, 2422, 3406, 2411, 1697, 2987, 2654, 0, 717, 1752, 1709, 3507, 2698, 2669, 1847, 1653, 974, 1317, 1317, 1317, 1317],
    [1510, 1510, 1520, 1520, 1480, 1435, 1290, 1555, 2380, 3721, 4697, 4402, 4402, 4540, 2748, 3732, 2737, 2023, 3313, 2980, 714, 0, 1571, 1533, 3495, 2685, 2657, 1835, 1640, 1055, 1643, 1643, 1643, 1643],
    [2246, 2246, 2256, 2256, 2217, 2172, 2027, 2292, 2609, 3743, 4926, 4874, 4874, 4822, 3485, 4468, 3473, 2760, 4050, 3716, 1687, 1593, 0, 96, 2699, 2378, 2350, 1590, 1168, 1428, 2380, 2380, 2380, 2380],
    [2182, 2182, 2192, 2192, 2152, 2108, 1962, 2228, 2544, 3679, 4862, 4810, 4810, 4758, 3420, 4404, 3409, 2695, 3986, 3652, 1623, 1534, 82, 0, 2635, 2314, 2286, 1526, 1104, 1363, 2316, 2316, 2316, 2316],
    [4143, 4143, 4153, 4153, 4113, 4068, 3923, 4188, 2773, 1291, 2750, 2898, 2898, 2846, 3394, 3274, 3383, 4352, 5561, 5588, 3541, 3514, 2748, 2705, 0, 1245, 1244, 1770, 2187, 2869, 4276, 4276, 4276, 4276],
    [3196, 3196, 3206, 3206, 3166, 3121, 2976, 3241, 1662, 1454, 2797, 2745, 2745, 2693, 3056, 3068, 3045, 3626, 4916, 4666, 2680, 2653, 2386, 2344, 1232, 0, 50, 909, 1325, 2007, 3329, 3329, 3329, 3329],
    [3195, 3195, 3205, 3205, 3165, 3120, 2975, 3240, 1661, 1453, 2796, 2744, 2744, 2692, 3056, 3067, 3044, 3625, 4915, 4665, 2651, 2624, 2358, 2315, 1231, 71, 0, 880, 1297, 1978, 3329, 3329, 3329, 3329],
    [2403, 2403, 2413, 2413, 2374, 2329, 2184, 2449, 1386, 2200, 3543, 3491, 3491, 3439, 2937, 3813, 2946, 2917, 4207, 3873, 1802, 1775, 1582, 1540, 1707, 897, 869, 0, 447, 1129, 2537, 2537, 2537, 2537],
    [2214, 2214, 2224, 2224, 2185, 2140, 1995, 2260, 1799, 2612, 3956, 3904, 3904, 3852, 3350, 4226, 3359, 2728, 4018, 3684, 1613, 1586, 1166, 1124, 2120, 1310, 1282, 460, 0, 940, 2348, 2348, 2348, 2348],
    [1556, 1556, 1566, 1566, 1526, 1481, 1336, 1601, 1682, 3023, 3999, 3947, 3947, 3896, 2794, 3778, 2783, 2069, 3359, 3026, 954, 1040, 1438, 1395, 2797, 1987, 1959, 1137, 942, 0, 1690, 1690, 1690, 1690],
    [551, 551, 562, 562, 612, 514, 558, 641, 2606, 3840, 4634, 3807, 3807, 3945, 2154, 3137, 2142, 1440, 2285, 1471, 1342, 1685, 2448, 2406, 4221, 3326, 3325, 2561, 2366, 1687, 0, 0, 0, 0],
    [551, 551, 562, 562, 612, 514, 558, 641, 2606, 3840, 4634, 3807, 3807, 3945, 2154, 3137, 2142, 1440, 2285, 1471, 1342, 1685, 2448, 2406, 4221, 3326, 3325, 2561, 2366, 1687, 0, 0, 0, 0],
    [551, 551, 562, 562, 612, 514, 558, 641, 2606, 3840, 4634, 3807, 3807, 3945, 2154, 3137, 2142, 1440, 2285, 1471, 1342, 1685, 2448, 2406, 4221, 3326, 3325, 2561, 2366, 1687, 0, 0, 0, 0],
    [551, 551, 562, 562, 612, 514, 558, 641, 2606, 3840, 4634, 3807, 3807, 3945, 2154, 3137, 2142, 1440, 2285, 1471, 1342, 1685, 2448, 2406, 4221, 3326, 3325, 2561, 2366, 1687, 0, 0, 0, 0],
]

PICKUP_VECTOR = [0, 0, 0, 0, 0, 0, 0, 0, 0, 10000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
DELIVERY_VECTOR = [
    -2000, -8000, -8000, -6000, -2000, -2000, -8000, -2000, -8000, 0,
    -6000, -2000, -6000, -6000, -6000, -2000, -6000, -2000, -6000, -8000,
    -8000, -6000, -6000, -8000, -2000, -8000, -2000, -6000, -8000, -8000,
    0, 0, 0, 0,
]
SERVICE_TIMES = [300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 0, 0, 0, 0]
CAPACITIES = [50000, 50000, 50000, 50000, 70000]
STARTS = [30, 30, 30, 30, 32]
ENDS = [31, 31, 31, 31, 33]
DROP_PENALTY = 600_000_000


@dataclass
class SolveResult:
    dropped: list[int]
    tours: list[list[int]]


def solve(time_limit_seconds: int = 60) -> SolveResult:
    """Builds and solves the routing model."""

    manager = pywrapcp.RoutingIndexManager(
        len(TIME_MATRIX),
        len(CAPACITIES),
        STARTS,
        ENDS,
    )
    routing = pywrapcp.RoutingModel(manager)

    def travel_time(from_index: int, to_index: int) -> int:
        return TIME_MATRIX[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

    transit_index = routing.RegisterTransitCallback(travel_time)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_index)

    pickup_index = routing.RegisterUnaryTransitCallback(
        lambda node_index: PICKUP_VECTOR[manager.IndexToNode(node_index)],
    )
    routing.AddDimensionWithVehicleCapacity(pickup_index, 0, CAPACITIES, True, "Pickup")

    delivery_index = routing.RegisterUnaryTransitCallback(
        lambda node_index: DELIVERY_VECTOR[manager.IndexToNode(node_index)],
    )
    routing.AddDimensionWithVehicleCapacity(delivery_index, 0, CAPACITIES, False, "Delivery")
    delivery_dim = routing.GetDimensionOrDie("Delivery")
    for vehicle_id, capacity in enumerate(CAPACITIES):
        delivery_dim.CumulVar(routing.Start(vehicle_id)).SetRange(capacity, capacity)

    max_capacity = max(CAPACITIES)
    load_index = routing.RegisterUnaryTransitCallback(lambda _: -max_capacity)
    routing.AddDimensionWithVehicleCapacity(load_index, max_capacity * 2, CAPACITIES, False, "Load")
    load_dim = routing.GetDimensionOrDie("Load")
    for vehicle_id, capacity in enumerate(CAPACITIES):
        load_dim.CumulVar(routing.Start(vehicle_id)).SetRange(capacity, capacity)

    def time_callback(from_index: int, to_index: int) -> int:
        node = manager.IndexToNode(from_index)
        return TIME_MATRIX[node][manager.IndexToNode(to_index)] + SERVICE_TIMES[node]

    time_index = routing.RegisterTransitCallback(time_callback)
    routing.AddDimension(time_index, 7200, 24 * 3600, False, "Time")

    for node in range(30):
        routing.AddDisjunction([manager.NodeToIndex(node)], DROP_PENALTY)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.SAVINGS
    search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC
    search_parameters.time_limit.seconds = time_limit_seconds
    search_parameters.log_search = True

    solution = routing.SolveWithParameters(search_parameters)
    if not solution:
        raise RuntimeError("No solution found.")

    dropped = sorted(
        node
        for node in range(30)
        if solution.Value(routing.NextVar(manager.NodeToIndex(node))) == manager.NodeToIndex(node)
    )

    tours: list[list[int]] = []
    for vehicle_id in range(len(CAPACITIES)):
        index = routing.Start(vehicle_id)
        tour = []
        while not routing.IsEnd(index):
            tour.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        tour.append(manager.IndexToNode(index))
        if len(tour) > 2:
            tours.append(tour)

    return SolveResult(dropped=dropped, tours=tours)


def main() -> None:
    result = solve()

    print(f"OR-Tools version: {ortools.__version__}")
    print(f"Tours found: {len(result.tours)}")
    print(f"Dropped customer stops: {len(result.dropped)} -> {result.dropped}")
    for tour_id, route in enumerate(result.tours, start=1):
        print(f"  Tour {tour_id}: {route}")


if __name__ == "__main__":
    main()

Testing Multiple Versions

Quick test across multiple OR-Tools versions:

for v in 9.7.2996 9.8.3296 9.9.3963 9.10.4067 9.11.4210 9.12.4544 9.13.4784 9.14.6206; do
  pip install ortools==$v --quiet && \
  python3 test_ortools_version_standalone_codex.py 2>&1 | grep -A 99 "OR-Tools"
done

Impact

This bug has been present for 20+ months (Dec 2023 - Oct 2025) and affects multiple routing scenarios:

• Heterogeneous VRP with reloads/landfills (your original report)
• Multi-class pickup/delivery with load tracking dimensions (our use case)
• Any scenario using dimensions with negative transit values for algorithmic purposes

The bug forces the solver to drop stops instead of utilizing available vehicles from smaller-capacity vehicle classes.

---

🤖 Generated with Claude Code

[lperron]

as said the PR, abs(transit) > max_capacity will make the node impossible to visit. Thus it will always be marked as unperformed.

The side effect of removing it early is that it changes the insertion heuristics.

Unfortunately, the proposed fix is incorrect.

[cyril23]

@lperron thanks for the feedback on the incorrect PR #4853.

I've submitted a new PR #4868 that properly bounds negative transits using capacity + slack_max rather than skipping them entirely.