Fix issue #4133: Correct negative transit handling in FinalizeAllowedVehicles by cyril23 · Pull Request #4868 · google/or-tools
added 3 commits
October 13, 2025 09:27…ehicles with negative transits The FinalizeAllowedVehicles() function was using abs() on transit values to check against vehicle capacity, which incorrectly excluded vehicles when: - CARGO_LOAD dimensions use negative constants for cumulative load tracking - Reload dimensions use negative values at landfills/depots This fix modifies the capacity check to only apply to positive transit values, since negative transits are used for algorithmic purposes (reload semantics, load tracking) rather than actual cargo capacity requirements. Changes: - Lines 1414-1421: Pre-processing loop now only considers positive transits for max_node_transit calculation - Lines 1444-1448: Main capacity check now skips negative transits entirely This resolves the regression introduced in commit 847cfc9 (Dec 1, 2023) affecting OR-Tools versions 9.9.3963 through 9.14.6206. Fixes: google#4133 Testing: test_ortools_version_standalone_codex.py (multi-class VRP with load tracking)
…llowedVehicles The FinalizeAllowedVehicles() optimization incorrectly excluded vehicles from nodes with negative unary transits. The bug checked abs(transit) against capacity alone, but negative transits are feasible when abs(transit) <= capacity + slack_max (vehicle can absorb the negative transit via both capacity headroom and dimension slack). This caused heterogeneous VRP problems with reload/load-tracking dimensions to incorrectly exclude smaller vehicles, forcing suboptimal solutions with dropped stops. The fix properly bounds negative transits by combining capacity and slack_max, while positive transits continue to check capacity alone. Fixes google#4133
cyril23 added a commit to LogicsSoftwareGmbH/or-tools that referenced this pull request
Oct 13, 2025…n FinalizeAllowedVehicles (v9.12) Backports the fix from PR google#4868 to v9.12 branch. The FinalizeAllowedVehicles() optimization incorrectly excluded vehicles from nodes with negative unary transits. The bug checked abs(transit) against capacity alone, but negative transits are feasible when abs(transit) <= capacity + slack_max (vehicle can absorb the negative transit via both capacity headroom and dimension slack). This caused heterogeneous VRP problems with reload/load-tracking dimensions to incorrectly exclude smaller vehicles, forcing suboptimal solutions with dropped stops. The fix properly bounds negative transits by combining capacity and slack_max, while positive transits continue to check capacity alone. Changes: - Pre-processing now tracks max positive transit, min (negative) transit, and slack_max separately instead of using abs() on all transits - Capacity optimization check considers both positive and negative bounds - Per-node feasibility check uses proper bounds: transit <= capacity && transit >= min_allowed_transit Tested with regression script from issue google#4133. Fixes google#4133 Backport-of: google#4868
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters