Congestion-Aware Branch-and-Price with Traffic Regimes as Branching Decisions

Fleet planners that route hundreds of vehicles through a city usually treat travel times as fixed inputs. Those inputs might be historical averages, or forecasts from a neural traffic model. This works as long as the fleet is a negligible fraction of traffic. It fails once the fleet is large enough to cause congestion itself, for example a ride-hailing operator, a freight consolidator, or an electric delivery fleet concentrated on a few corridors. Its own vehicles then slow each other down, and the effect spreads backward along the road as a queue grows. We propose an exact-style optimizer that plans the fleet's routes and the traffic it creates in the same model. It builds on branch-and-price, the standard method for large routing problems. That method splits the problem into a "master" program, which picks a combination of candidate routes, and a "pricing" search, which repeatedly invents new routes that the master's current prices say are worth adding. Our version adds a linear traffic-flow model inside the master. In that model each road segment in each time slot behaves in one of a few physical regimes (free-flowing, at capacity, or jammed), and the optimizer branches on these regimes the same way it branches on routing choices.

The two-sentence version is this. Road traffic is a hybrid system: within a fixed regime the flow equations are linear, and the only nonlinearity comes from switching between regimes. We put those linear equations into the branch-and-price master and treat each regime as a discrete branching variable. The fleet's routes and the congestion they cause are then optimized jointly, with valid bounds. Neural traffic forecasters supply the background demand and a guess at which regime each segment will be in. They are not used as the travel-time oracle.

Core Claim

The claim has three parts. First, the cell transmission model (a discretization of the Lighthill-Whitham-Richards kinematic-wave equation in which each road cell sends flow downstream at the minimum of its demand, its capacity, and the downstream cell's free space) becomes a set of linear constraints once the active term of each minimum is fixed. Second, these constraints can sit in a Dantzig-Wolfe master alongside route columns. Third, the resulting dual prices on road cells reach the pricing search as time-dependent arc surcharges, so pricing keeps the same structure.

For cell $i$ in time slot $t$, define the following quantities:

  • $\rho_{i,t}$ is the density.
  • $y_{i,t}$ is the flow passed to the next cell.
  • $v$ is the free-flow speed.
  • $Q$ is the cell capacity.
  • $w$ is the backward wave speed.
  • $\rho^{\text{jam}}$ is the jam density.

The true dynamics are

$$y_{i,t} = \min\{\, v\,\rho_{i,t},\; Q,\; w(\rho^{\text{jam}} - \rho_{i+1,t}) \,\}.$$

The obvious LP relaxation replaces "$=\min$" with "$\le$ each term." This relaxation is known to permit "holding back," where flow voluntarily waits in a free road. As a result it understates congestion and can report schedules that the physical system would not deliver. We make the regime $m_{i,t} \in \{\text{free}, \text{capacity}, \text{jammed}\}$ an explicit branching object. Within each branch the active term holds with equality, so the master stays linear and the relaxation becomes exact for the cells that have been branched on.

The fleet enters through the density terms: $\rho_{i,t}$ is background density plus the occupancy that the selected route columns place in cell $i$ at time $t$. The reduced cost of a route column $j$ is

$$\bar c_j = c_j - \pi^\top a_j - \sum_{i,t} \mu_{i,t}\, n_{j,i,t}.$$

Here:

  • $c_j$ is the route's direct cost.
  • $\pi$ are the duals on service-coverage and fleet constraints.
  • $a_j$ is the column's coverage pattern.
  • $\mu_{i,t}$ are the duals of the traffic constraints.
  • $n_{j,i,t}$ is the occupancy that route $j$ places in cell $i$ at time $t$.

The duals $\mu_{i,t}$ are where the hybrid physics shows up as prices. In a jammed regime, adding a vehicle to cell $i+1$ tightens the receiving constraint of cell $i$. A cell that has been branched to "jammed" therefore propagates its price upstream. This is the same directional asymmetry that RA-BiGN builds into graph message passing for forecasting, here derived exactly from optimization duality. The pricing problem stays a resource-constrained shortest path on a time-expanded graph, so the existing machinery carries over unchanged: bi-directional labeling, non-dominated charging arcs, and diving from Electric Vehicle Fleets, and cut-and-price from Branch-and-Cut-and-Price for Multi-Agent Pathfinding.

Positioning

Each nearby paper covers part of this problem.

The closest method source is Electric Vehicle Fleets: Scalable Route and Recharge Scheduling Through Column Generation. It solves electric vehicle scheduling with a continuous battery resource by branch-and-price. Its arc times and energy costs are static, so dispatch decisions never change network conditions. We keep its pricing and diving and remove that static assumption.

Branch-and-Cut-and-Price for Multi-Agent Pathfinding contributes the pattern we follow: agents interact only through master-level constraints on space-time cells, and conflict cuts are added lazily. Its interaction is binary collision on an empty grid with unit speeds. Ours is a capacity and spillback law driven by background flow.

On the hybrid-systems side, Differentiable Hybrid Traffic Simulation couples a macroscopic Aw-Rascle-Zhang flow model with microscopic car-following agents. It optimizes continuous controls such as signal timings and pace-car speeds by gradient descent. It cannot express discrete routing or service assignment, and it gives no bound. We use it only as an independent, higher-fidelity evaluator, so the optimizer is not graded by its own model.

Two papers motivate the gap rather than supply method. The hybrid-automata co-simulation of Bo et al. shows the continuous-discrete coupling but is purely descriptive. The file's survey of hybrid control notes that no decomposition schemes exist for multi-agent hybrid systems and that big-M mixed-integer formulations relax poorly. Our regime branching is a direct response to that looseness: we branch on modes instead of encoding them with big-M constraints.

The spatiotemporal forecasters play a supporting role. These are STAEformer, STGL, and RA-BiGN. They predict boundary inflows of background traffic. RA-BiGN's learned propagation weight also gives a natural initial guess for each cell's regime.

Research Program

The work has four parts.

The first is the formulation. We will write the coupled master as follows:

  • service coverage and fleet-size rows, as in the vehicle scheduling literature;
  • cell transmission constraints over a corridor network;
  • background flow as continuous master variables with fixed turning fractions;
  • fleet occupancy entering through columns.

We will prove that within any complete regime assignment, the LP relaxation over columns gives a valid lower bound for that assignment. We will also prove that branching on regimes, followed by branching on original arc-time variables, is complete.

The second is the pricing extension. Cell duals become time-dependent arc surcharges. We need to check that this preserves the dominance rules of the labeling algorithm, given that waiting has to be allowed in the time-expanded graph.

The third is regime branching strategy. Regime branching could make the tree explode, so we will initialize regimes from the forecaster's prediction. We will then branch first on the cells where the LP shows holding back, meaning a slack minimum term combined with a positive fleet-flow change. We will also test lazy separation, where regime equalities are added only for cells that the fleet's flow actually touches.

The fourth is a heuristic tier for scale: diving with regime fixing, mirroring Parmentier et al.'s strong-diving recipe. Exact search does not scale to 500 services even without traffic: the file reports it failing within 6 hours on static instances. The useful product at that size will therefore be diving solutions accompanied by a root bound, and we will evaluate it that way.

Baselines

The naive reference point uses free-flow travel times in the static branch-and-price of Electric Vehicle Fleets. It is solved on the same instances and then evaluated in the simulator. It shows how much ignoring traffic costs at all.

The strongest existing competitor uses forecast-driven exogenous times. We train the best available forecaster on the PeMS data behind our corridor (STAEformer, STGL, or RA-BiGN; whichever wins on the held-out period). Its predicted time-dependent travel times feed the same static branch-and-price pipeline. This is what a competent practitioner would build today, and it is very strong whenever the fleet is small. For the forecasting component, STGL reports MAE 20.06 on PEMS04 and 15.04 on PEMS08 STGL. RA-BiGN reports the best average rank on both datasets and a 4% relative MAPE gain over STAEformer on PEMS04, but the file gives no absolute value for it. For the routing component, the static diving heuristic is reported within 0.06% of the root LP bound and 38.38% cheaper than adaptive large neighborhood search on 500-service static instances Electric Vehicle Fleets. We found no reported result on Lacuna for any method on a coupled fleet-plus-traffic benchmark, so the head-to-head numbers will be ours.

Third is an iterated re-solve baseline. Solve static branch-and-price, run the simulator with the fleet inserted, update arc times, and repeat with step-size averaging, as in standard traffic-assignment practice.

Fourth is a simulator-in-the-loop large neighborhood search, given the same wall-clock budget.

All methods share the following conditions:

  • the same instances and the same forecaster outputs;
  • the same machine;
  • the same total time budget (we will report 10-minute and 1-hour budgets);
  • the same final evaluator, namely the Son et al. hybrid simulator calibrated to the corridor.

The key ablation removes regime branching and keeps the plain relaxed cell transmission LP in the master. This isolates whether exact mode handling, rather than merely having congestion in the master, drives any gain.

The method counts as beating the forecast-driven baseline if three conditions hold. Simulated total cost (fleet operating cost plus fleet lateness) must drop by a margin larger than the seed-to-seed variation of the simulator. The gap between the planned and simulated schedule must shrink. Both must hold at fleet shares where the baseline's planned schedules visibly break in simulation.

Why not just…?

Why not just plug the best forecaster's travel times into existing branch-and-price? Because the forecaster predicts traffic as if the fleet's own decisions were not happening. Below some fleet share this is harmless, and that is a real threat to the proposal. We will settle it by sweeping fleet share from roughly 1% to 30% of corridor flow and reporting where, if anywhere, the curves cross. If the joint model never beats the forecast-driven baseline below a share that real fleets rarely exceed, we will report that as the main finding. In that case the contribution narrows to a certification tool that tells an operator when exogenous travel times are safe.

Why not just iterate: solve, simulate, update travel times, re-solve? This is cheap and widely used. However, a fixed-point loop on discrete routes tends to herd: every vehicle moves to the corridor that looked fast last round, and the loop can oscillate without converging. It also provides no bound. We will log oscillation, final cost, and the number of rounds. If damped iteration matches the joint model's simulated cost within noise, the joint model's remaining value is its lower bound, and we will say so plainly.

Why not just optimize with the differentiable simulator directly? Differentiable Hybrid Traffic Simulation shows strong gradient-based results, but only for continuous controls on a synthetic 4x4 grid. Service assignment and route sequencing have no useful gradients. The simulator-in-the-loop neighborhood search baseline is the fair discrete stand-in for this alternative. Its known weakness against column generation, the 38.38% cost gap in the static setting, is what we expect to carry over.

Why not just add the relaxed traffic LP to the master without branching on regimes? This is the ablation. We expect it to produce optimistic plans that use phantom capacity through holding back. The test is whether its planned-versus-simulated gap is much larger than that of the regime-branched model at high fleet shares.

Proposed Experiments

No benchmark couples fleet service requests with real traffic. We will build one by overlaying Wen et al. electric vehicle scheduling instances (100 to 500 services, 2 to 8 depots) onto corridor graphs derived from the sensor topology of PEMS04 (307 sensors) and PEMS08 (170 sensors). Background boundary demand comes from held-out days, forecast by the trained spatiotemporal models. Ground truth for evaluation comes from the hybrid simulator replaying observed demand, so forecast error is included in every method's score.

The metrics are:

  • simulated fleet cost and lateness;
  • total background delay, reported separately so that we never trade the public's delay for fleet savings without disclosing it;
  • the planned-versus-simulated gap;
  • root bound and optimality gap;
  • runtime.

Three checks decide the project. The first is the fleet-share sweep against the forecast-driven baseline, which says whether endogenous congestion matters at realistic scales. The second is the regime-branching ablation, which says whether the hybrid-mode treatment is the ingredient that matters. The third is a tree-size study on the 100-service instances, which says whether regime branching stays tractable when warm-started from forecaster regimes or explodes. We will also check whether the cell duals learned in the jammed branches propagate upstream in the pattern predicted by kinematic-wave theory. That check ties the optimization result back to the physics that RA-BiGN exploits for prediction.