Electric vehicles get energy back when they brake or roll downhill. On a road graph this shows up as negative edge costs. Batteries also have a ceiling: a car that is already full at the top of a hill gains nothing on the way down. Routing research has worked out how to find single energy-optimal paths under these conditions. A road operator faces a harder problem. It wants to set a few tolls so that thousands of drivers, each choosing routes selfishly, collectively waste less energy, sit in less congestion, and run out of charge less often. That is a bilevel problem: the operator moves first, and the drivers' route equilibrium responds. Bilevel methods have so far been applied only to networks whose costs are positive and add up along a path.
This note proposes a fix in two parts. First, we track each vehicle's state of charge as part of its position on the graph. On this enlarged graph, the effects of recuperation and the battery ceiling become ordinary state transitions with positive travel-time costs. Second, we model drivers as making slightly noisy route choices. Under that model the drivers' equilibrium is the unique minimizer of a smooth, strongly convex problem. That is exactly the setting where single-loop bilevel methods have guarantees. These methods update the tolls and the drivers' response together, one small step each, instead of re-solving the equilibrium after every toll change. The outcome would be the first toll-design method that treats regenerative braking and battery limits exactly, with a convergence argument and a cost per iteration close to one sweep of a routing algorithm.
Core Claim
The difficulties that recuperation creates are negative cycles, path costs that change depending on how you group segments, and the absence of backward shortest-path trees. All three come from compressing the battery into a single number carried along a path. They are not inherent to the physics. Make the charge level part of the node, and charge capping becomes a deterministic transition. Every edge cost becomes nonnegative travel time plus toll. The energy outcome becomes a cost paid at the destination for recharging. Running out of charge becomes an absorbing "stranded" state. Add entropy-regularized route choice, meaning drivers pick routes with probabilities that fall off smoothly as cost rises, and the lower level becomes a stochastic user equilibrium with a unique, Lipschitz-continuous response to tolls.
On this structure, a single-loop method has three moving parts: one warm-started soft Bellman sweep, one forward pass that pushes vehicle flow through the network, and one adjoint update per toll step. We claim it reaches the toll quality of a full nested solver at a small fraction of the wall-clock cost. We further claim the battery ceiling materially changes which second-best tolls are optimal on hilly networks, so methods that ignore it set measurably worse prices.
Research Program
Physics, from the routing literature. We reuse the physical modeling from routing work. Optimal energetic paths for electric cars formalizes the capped depletion operator and proves two things: it is non-associative, and optimal trees exist from a single origin but not, in general, into a single destination. Optimal Route Planning for Electric Vehicles in Large Networks and Efficient Energy-Optimal Routing for Electric Vehicles use elevation as a node potential, which makes single queries fast. Real-Time Energy-Optimal Path Planning for Electric Vehicles supplies a quadratic consumption model calibrated against a powertrain simulator ($R^2$ of 0.99). That paper also shows elevation-only models leave 44% of Calgary routes infeasible.
All of these papers solve one vehicle's query on a fixed graph. None has an operator, an equilibrium, or a gradient with respect to prices. We take their energy model as given.
The charge-augmented graph. We discretize charge into $K$ levels $s_1 < \dots < s_K = B$, where $B$ is battery capacity. The enlarged graph has states $(v, k)$, meaning road node $v$ at charge level $k$. An edge $(u,v)$ with energy use $w(u,v)$, which may be negative, sends state $(u,k)$ to charge $\min(B, s_k - w(u,v))$. Because that value rarely lands exactly on a grid level, we split it between the two neighboring levels using linear interpolation weights. If the resulting charge would fall below zero, the transition goes to the stranded state instead.
Drivers with value of time $\lambda$ choose among outgoing transitions using a soft Bellman recursion with temperature $\theta > 0$:
$$V(u,k) = -\theta \log \sum_{(v,k')} P_{uv}(k' \mid k)\, \exp\!\Big(-\tfrac{1}{\theta}\big[\lambda\, t_{uv}(f_{uv}) + x_{uv} + V(v,k')\big]\Big).$$
The symbols are as follows. $V$ is the expected cost-to-go to the driver's destination. $P_{uv}(k' \mid k)$ is the interpolated charge transition. $t_{uv}(f_{uv})$ is the travel time on edge $(u,v)$ given its total physical flow $f_{uv}$, summed over all charge levels. $x_{uv}$ is the toll, which is zero on links the operator cannot toll. At the destination, $V$ equals the energy price times the charge needed to refill. At the stranded state, $V$ equals a large penalty.
Every step costs at least the minimum edge time. The recursion therefore behaves like a stochastic shortest-path problem with proper policies, and negative cycles cannot drive costs to minus infinity. The battery ceiling is encoded exactly in $P$.
This also addresses Optimal energetic paths for electric cars directly. Backward value functions into a destination do exist on the enlarged graph. The price is a factor of $K$ in the number of states, and we measure that cost explicitly.
The bilevel problem. The drivers' equilibrium flow $y^*(x)$ minimizes an entropy-regularized assignment objective. That objective is strongly convex in the state-edge flows, which is the standard property of logit stochastic user equilibrium. The operator then solves
$$\min_{x \in \mathcal{X}} \; F(x, y^*(x)) = \text{total time} + \rho_E \cdot \text{grid energy drawn} + \rho_S \cdot \text{stranded flow},$$
where $\mathcal{X}$ restricts tolls to a small set of tollable links. The weights $\rho_E$ and $\rho_S$ may differ from what drivers privately weigh.
Where the battery ceiling enters pricing. Tolls cannot depend on a car's private charge level. The best uniform toll therefore depends on how charge is distributed across the driver population. This is the effect a cap-blind model cannot see. A downhill link carrying mostly full-battery cars recovers little energy. The same link carrying mostly depleted cars recovers a lot.
The single-loop algorithm. The design follows the dynamic-tracking idea in Lin et al. and two-timescale stochastic approximation as analyzed in Hong et al.. Each iteration does four things:
- It applies one soft Bellman sweep to the warm-started value functions of the sampled destinations.
- It pushes demand from a sampled batch of origin–destination pairs and initial charge levels forward through the resulting choice probabilities. This updates the flow tracker by one averaging step.
- It updates an auxiliary adjoint variable that tracks the solution of the implicit-function linear system. This is the tracking device of FdeHBO, implemented with Hessian-vector products from automatic differentiation of the sweep.
- It takes one projected step on the tolls.
A variant replaces the separate step sizes with the double-momentum estimator of SUSTAIN. Its guarantee needs a strongly convex lower level. Our construction is built to provide exactly that, so the guarantee becomes usable for the first time on a recuperation network.
Theory. The theoretical work is to establish two properties. The first is that the equilibrium's sensitivity to tolls is Lipschitz, with constants that depend on $\theta$, $K$, and the minimum edge time. The second is that the error from doing only one sweep per iteration is controlled by the contraction rate of the soft Bellman operator.
One known weakness we will handle explicitly. If energy use itself depends on congestion, the interpolated transitions have kinks at grid boundaries. The main study keeps energy use dependent on free-flow speed and slope only. Congestion-dependent energy is treated as an extension, smoothed with quadratic interpolation.
Baselines
No tolls. The naive reference point is the untolled stochastic user equilibrium on the same charge-enlarged graph. Every gain is reported relative to it.
Marginal-cost pricing. Each tollable link is charged the congestion externality its users impose, evaluated at the current equilibrium and iterated to a fixed point. When every link is tollable, this classic rule is close to optimal. It is therefore the most dangerous simple competitor. It runs on identical networks and demand, with the same equilibrium solver. Beating it means a lower upper-level objective at equal toll budget, when only a small fraction of links can be tolled.
Online dual toll update. The rule of Online Learning for Traffic Routing under Unknown Preferences raises a link's toll when its flow exceeds capacity and lowers it otherwise. That paper proves $O(\sqrt{T})$ regret and $O(\sqrt{T})$ capacity violation. On Sioux Falls it reports total travel times "nearly identical to the theoretical minimum," but with no numeric value; no reported result found on Lacuna for its performance on energy or stranding objectives. We run it with capacities chosen by a small grid search under the same compute budget as our method. Beating it means lower energy and stranding at matched travel time.
Nested double-loop solver. This is the strongest exact competitor. At each toll step it solves the equilibrium to tight tolerance, then computes the exact implicit hypergradient. For the smallest toll sets, we also run a derivative-free Bayesian optimizer over the tolls with the same exact inner solver. For calibration of inner-solver cost, the routing literature reports single energy-optimal queries at 0.18 seconds with contraction hierarchies on a 5.5-million-node Southern Germany graph (Eisner et al.) and 0.6 seconds for Energy-A* on 90–100 km Bavarian trips (Sachenbacher et al.). These are single-query figures; no reported result found on Lacuna for equilibrium-level or bilevel runtimes with recuperation. Beating this baseline means reaching within 1% of its final objective in substantially less wall-clock time.
SFLCB on a cap-blind model. This is the strongest existing single-loop method on transportation network design. SFLCB solves the problem as a penalized augmented-Lagrangian gradient descent–ascent over continuous flows. That paper evaluates it on 3- and 9-node network design with positive polynomial latencies; no reported result found on Lacuna for a numeric objective value there. We give SFLCB a cap-blind model: energy enters as an additive cost made nonnegative by elevation potentials, and the battery ceiling is ignored. Its tolls are then scored in the cap-aware model. Beating it means a lower cap-aware objective, especially in stranding.
Ablations. Four ablations isolate the key ingredients. Setting $B=\infty$ removes the battery ceiling. Varying $K$ tests discretization. Running several sweeps per iteration tests the single-loop approximation. Freezing the adjoint at zero, which drops the implicit term, tests whether the hypergradient correction matters.
Why not just…?
Why not just use marginal-cost tolls? With every link tollable and drivers' private costs well specified, they may indeed be enough. In that regime we expect no gain, and we will report that. The bilevel machinery earns its keep in two cases. One is second-best tolling, where only a few links can be priced and the externality of untolled links must be shifted onto tolled ones. The other is an operator objective that weighs stranding or grid draw more than drivers do. The experiment sweeps the fraction of tollable links from small to full and locates where the two methods meet.
Why not just solve the equilibrium exactly each time and use a derivative-free search over tolls? With three to five tolls this is a real threat. Bayesian optimization with an exact inner solver may match us in wall-clock time. We sweep the toll dimension and report the crossover. We expect gradient-free search to degrade as tolls grow into the dozens. Nested solvers pay the full equilibrium cost on every step, while the single-loop method pays about one sweep.
Why not just reweight with elevation potentials, ignore the battery ceiling, and apply an existing positive-cost bilevel method? This is the strongest conceptual objection. Potentials do remove negative edges for single queries, as shown in Real-Time Energy-Optimal Path Planning for Electric Vehicles. But Optimal energetic paths for electric cars shows the battery ceiling makes path costs non-additive, which potentials cannot repair. The 44% infeasibility gap is a warning about what simplified energy models miss.
Whether the cap actually changes optimal tolls is an empirical question, and it is our first decisive check. If cap-blind SFLCB tolls score within noise of ours under cap-aware evaluation, the battery-ceiling story fails, and the proposal reduces to a speed result on ordinary networks.
Why not just clip negative energy to zero? Clipping treats a regenerating descent like a flat road. Online Learning of Energy Consumption for Navigation of Electric Vehicles uses a clipped Gaussian model to keep Dijkstra usable. Its large gap on Luxembourg (regret of 7176.85 for log-Gaussian Thompson sampling versus 409337.40 for greedy) compares exploration strategies, not clipping, so we do not cite it as evidence against clipping. Clipping instead enters our ablations as a cheaper cap-blind model.
Proposed Experiments
Networks. The first testbed is the 3- and 9-node design networks from SFLCB, with synthetic elevations added. Here exact bilevel solutions can be computed by enumeration. The second is Sioux Falls, as used by Jalota et al., with the same $5–$100/hr value-of-time spread. Its topology is schematic and flat, so we overlay controlled synthetic elevation fields of increasing relief. This lets us vary the strength of the battery-ceiling effect deliberately.
At realistic scale, we use subregions of the DIMACS San Francisco Bay and Colorado graphs with NASA SRTM elevations, following Resource Constrained Pathfinding with A* and Negative Weights. Demand is aggregated to a few dozen zones, because $K$ charge levels multiply the state count. Initial charge is drawn from several population distributions, from mostly full to mostly low. Final tolls are additionally evaluated in the Luxembourg traffic microsimulation used by Åkerblom et al.. This checks that gains survive vehicle-level dynamics our equilibrium model omits.
Metrics. We report the upper-level objective and its three components (time, energy, stranding). Stranding is re-measured by exact continuous-charge simulation of sampled vehicles, to expose discretization error. We also report hypergradient error against the nested solver, and wall-clock time to reach within 1% of the nested solver's objective.
Decisive checks. There are three.
- Do cap-aware tolls beat cap-blind tolls under cap-aware evaluation, with the gap growing with terrain relief and with the share of high-charge vehicles? If not, the battery ceiling does not matter for pricing.
- Does the single-loop method match the nested solver's final objective at a fraction of its cost as network size grows? If not, nesting is good enough.
- Do toll quality and stranding estimates stabilize by moderate $K$ (say 16–32 levels)? If not, the enlarged graph is too expensive and a continuous smoothed cap is needed.
A negative result on the first check would still be informative. It would tell the transportation community that standard positive-cost bilevel tools are adequate for pricing electric fleets.
References
- Optimal Energetic Paths for Electric Cars
- Optimal Route Planning for Electric Vehicles in Large Networks
- Efficient Energy-Optimal Routing for Electric Vehicles
- Real-Time Energy-Optimal Path Planning for Electric Vehicles
- On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
- A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
- Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization
- A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
- Online Learning for Traffic Routing under Unknown Preferences
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
- Online Learning of Energy Consumption for Navigation of Electric Vehicles
- Resource Constrained Pathfinding with A* and Negative Weights