CS Paper Radar

Topology-Aware Congestion Pricing: Demand Robust Routing using the Forman-Ricci Curvature

Sheryl Paul, Samuel Williams, Kexin Wang, Ruolin Li, Jyotirmoy V. Deshmukh

eess.SY ·submitted 2026-09-14 03:35 UTC · v1
theory

Abstract

Congestion pricing is widely used to improve transportation network efficiency where individual decentralized route choices can lead to system-level inefficiencies. Pigouvian tolls achieve the system optimum but depend on demand and can lose effectiveness under demand shifts, particularly on structurally critical bottleneck edges. We propose a topology-aware regularization of the Beckmann potential governing the (Wardrop) equilibrium by augmenting precomputed Pigouvian tolls with an offline structural penalty derived from Forman--Ricci curvature (FRC), which captures bottleneck structures. We prove that the resulting equilibrium is well-defined, that stronger regularization reduces flow on penalized edges, and that efficiency loss depends on how closely the structural penalty approximates optimal Pigouvian tolls. Experiments on eight real-world networks under targeted and uniform demand perturbations show reduced bottleneck flow with near-optimal efficiency. FRC achieves reductions comparable to edge betweenness at substantially lower computational cost, making it a practical, robust complement to classical congestion pricing.

Closest papers

Nearest neighbours by meaning across the whole index.

Single-level reformulations for network pricing under Wardrop equilibrium with separable affine costs

cs.GT math.OC ·2026-10-19 ·Miguel F. Anjos, José Neto
benchmarktheory similarity 0.59
Abstract

We consider the problem of setting tolls on a subset of the arcs of a congested network so as to maximize the revenue of a network authority, anticipating that users route according to a Wardrop equilibrium. This problem is naturally cast as a bilevel program in which the leader sets tolls while the followers respond by choosing an equilibrium routing. We focus on the important special case of separable affine arc cost functions. Under this assumption, Wardrop equilibria admit Beckmann's convex characterization, from which we derive three new single-level reformulations of the bilevel problem, exploiting both Beckmann's formulation and its dual: an arc-based formulation, which we solve exactly, and two path-based formulations, solved by column-and-constraint generation. Beyond the reformulations, we further derive from Beckmann's potential an upper bound on the optimal revenue that can be used to certify optimality gaps across all formulations. An extensive computational study on instances derived from the Sioux Falls and Eastern Massachusetts networks compares our formulations with the recent mixed-integer nonlinear formulation of Beck, Labbé and Schmidt. The arc-based formulation solves substantially more instances to proven optimality (within a time limit of 1800 s) than this formulation and, unlike it, returns a feasible solution on every instance. It remains effective on the largest, 74-node network, on which the formulation of Beck et al. solves none. The magnitude of the upper bounds on the tolls proves to be a major driver of tractability: the genuinely hard core of the benchmark emerges once the regulatory cap on tolls is removed. The two path-based formulations, used as heuristics, return a solution within one percent of the optimum on every instance whose optimal value is known, often in seconds where exact formulations reach the time limit.

0.24

Real-Time Design of Public Transport Lines: Reconciling Adaptivity and Efficiency

eess.SY ·2026-08-18 ·Duo Wang, Andrea Araldo, Mounim El-Yacoubi
similarity 0.58
Abstract

Demand-responsive transport (DRT) is typically routed by solving Dynamic Vehicle Routing Problems (DVRPs), where individual vehicle trajectories are adjusted on incoming requests. This limits demand consolidation and thus efficiency. On the other hand, Conventional Public Transport (CPT) bus systems are based on a network of lines and users find their routes on it, which provides high demand consolidation. However, such a network is built offline and cannot adapt to the demand. We propose a public transport management strategy that reconciles efficiency and adaptivity by dynamically designing a structured network of lines via a receding-horizon optimization approach. Using real-world trip requests, we show that we nearly double the fraction of served requests compared to DVRP-based routing, and we serve more requests than CPT with lower user trip times.

0.31

Tolls for Dynamic Equilibrium Flows

cs.GT ·2026-08-12 ·Lukas Graf, Tobias Harks, Julian Schwarz
similarity 0.58
Abstract

We consider dynamic network flows and study the following question: Which dynamic edge flows can be implemented as tolled dynamic equilibrium flows? We study this question for the heterogeneous-user model, where the flow particles are partitioned into populations characterized by their own source,destination-pairs and a cost function associating with any walk and departure time some costs. As our two main results, we first provide a duality-based characterization of implementability of dynamic edge flows for the multi-source, multi-destination case. Secondly, we derive both, a combinatorial and duality-based characterization of implementability of dynamic edge flows for the multi-source, single-destination case. Both results are derived under a fairly general network loading model. For the proof, we make several technical contributions: We formulate a novel infinite dimensional optimization problem, where the goal is to minimize the aggregated costs of the particles with respect to the fixed network loading induced by the given edge flow. This requires the recently introduced concept of autonomous network loadings for which we show several new structural insights. In particular, we give an alternative (tighter) characterization of the existence of autonomous network loadings for our setting by deriving a generalization of a result of M.A. Zareckiĭ on the Lusin $N^{-1}$ property of absolutely continuous monotone functions which may also be of independent interest. These insights allow us to prove the stated characterizations under the assumption of strong duality. Finally, for the case of a single-destination, we are able to provide a non-trivial proof that this assumption is always fulfilled for finitely supported edge flows with costs representing weighted travel times.

0.04

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.56
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

TANGCO: Learning Topology-Aware Capacity Allocation for Overload-driven Cascading Failures

cs.LG cs.SI ·2026-08-13 ·Orkun Irsoy, Leman Akoglu, Osman Yagan
similarity 0.56
Abstract

Networked systems, from power grids to traffic networks and cloud clusters, carry loads across nodes with limited capacity. A node whose load exceeds its capacity fails and sheds its load onto its neighbors, which can trigger a system-wide cascade. We study how to allocate a fixed capacity budget across nodes to resist these cascades under local load redistribution. The problem is difficult because no optimal allocation is known, and the fail-or-survive objective is non-differentiable and piecewise constant, so exact and gradient-based optimization methods do not directly apply. We introduce TANGCO (Topology-Aware Neural Graph-Guided Capacity Optimization), which uses a graph neural network policy trained through the cascade simulator with policy-gradient learning and a heuristic anchor. We evaluate TANGCO on five synthetic graph families and five real networks spanning power, road, air, and Internet topologies. The learned policy improves on the best of four hand-designed heuristics in all 450 synthetic instances and in 40 of 45 real-network conditions, with robustness gains ranging from 1.6% to 246%. The learned policies transfer to unseen graphs within a family and partially across related topologies, and TANGCO$^{pre}$, pre-trained on synthetic graphs, matches per-network training on unseen real networks. Training scales near-linearly with graph size, and TANGCO$^{pre}$ allocates on a new network with no per-target training, matching the deployment cost of a hand-designed heuristic. Free-vector variants without the GNN, stay close to the heuristics, so the graph representation carries the gain beyond numerical search. Finally, analysis of the learned allocations identifies when local risk is sufficient, leads to an improved closed-form heuristic, and reveals the regimes where a topology-aware learned policy remains necessary.

0.04

Token Economy Design for Fair and Efficient Highway Congestion Management with Express Lanes

eess.SY cs.GT ·2026-10-01 ·Leonardo Pedroso, Juan Pablo Bertucci, W. P. M. H. Heemels, Mauro Salazar
similarity 0.55
Abstract · Accepted to the 2026 IFAC Workshop on Cyber-Physical Human Systems

We study the design of a token economy for highway lane allocation that aims to improve fairness without sacrificing traffic efficiency. Motivated by the San Mateo 101 Express Lanes Project, we consider a setting in which high-occupancy vehicles have unrestricted access to an express lane, while the remaining users can alternate between regular and express lanes by earning and spending nonmonetary tokens. We model the resulting interaction as a finite-population dynamic congestion game with heterogeneous time preferences and limited-information evolutionary policy revisions. Building on a mean-field approximation, we derive token prices that enforce the system-optimal lane split while inducing fairness over time through turn-taking. The scheme is evaluated in a microscopic traffic simulation with real-world demand data. The results show that the proposed prices yield nearly the same average travel time as a baseline scenario in which no lane is reserved as an express lane, while substantially reducing urgency-weighted perceived travel time. These findings highlight token economies as a promising alternative to monetary congestion pricing for fairer management of scarce road capacity.

0.40

A Performative Control Approach to Day-to-Day Traffic Signal Retiming

eess.SY ·2026-10-13 ·Shuchang Jiang, Xinwu Qian, Santiago Segarra, Zhongyuan Zhao
similarity 0.55
Abstract · 8 pages, 6 figures, 2 tables

Conventional fixed-time traffic signal optimization and recent day-to-day signal retiming generally model route adaptation under prescribed route-choice behavior and origin-destination (OD) demand, while neglecting the fact that travelers' behavior can be performative to the signal control policy. A signal timing policy learned from historical traffic observations must therefore account for how its own deployment changes the distribution on which it will be evaluated in the future. We formulate this problem as performative signal control under observed traveler responses and characterize performative stability of the coupled policy-demand system. We propose incremental day-to-day retiming using the local policy gradient at the current operating point, estimated offline through simulation-based zeroth-order optimization without an explicit day-to-day demand-response model. This gradual approach provides a feasible path for policy and demand to co-evolve toward stability. Experiments on a downtown Denver network show that our approach improves congestion, throughput, and stability, generalizes across different demand levels, and remains effective when the offline simulator contains mismatched travel demand and routing behaviors.

0.21

Design Rules for Low-Latency Multipath Congestion Control

cs.NI ·2026-11-16 ·Danny De Vleeschauwer, Chia-Yu Chang, Koen De Schepper, Simone Bolettieri
similarity 0.55
Abstract

We first study optimal congestion control from a theoretical perspective. Concretely, we consider a system that optimizes the sum of the utilities of all the users, in which the users are allowed to send their traffic over different paths over the network and derive design rules that optimal (low-latency) multipath congestion control needs to follow. Because, as it turns out that optimal congestion control requires coordination between the network nodes, and hence, is hard to implement, we investigate how to approximate its performance with algorithms in which (i) the network nodes make independent decisions and (ii) coordination is only allowed between the subflows that belong to the same user. Therefore, these design rules need to be slightly relaxed. We compare the performance of these realistic algorithms with the optimal algorithm. We also investigate to what extent the algorithms that are currently defined and are being defined in the Internet Engineering Task Force (IETF), in particular, (i) Prague congestion control (i.e., congestion control based on Accurate Explicit Congestion Notification (AccECN) marks) and (ii) a variant of a loss-based multipath congestion control algorithm, adhere to these rules.

0.25