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