Tolls for Dynamic Equilibrium Flows

Coordination versus Selfishness: The Impact on Traffic Efficiency

A general framework for nonlocal traffic flow models on networks

We present a general computational framework for macroscopic nonlocal traffic flow models on networks with multiple commodities. The model combines scalar conservation laws on edges with nonlocal velocity functions and couples them via buffer-based junction dynamics. Routing is defined in general as a prescription for distributing drivers across outgoing road segments. As an example, we implement dynamic k-shortest-path routing, where travel times along roads and waiting times at intersections are used to compute shortest paths to the commodities'destinations at each time step, and drivers are distributed accordingly. In another example, we optimize routing over a considered time horizon to minimize the total travel time. This framework naturally creates a feedback loop between traffic evolution and route choice. Numerical examples, ranging from small test cases to large grid-like networks, demonstrate the robustness of the approach and allow for a comparison of different routing strategies.

Perturbed utility Markovian traffic equilibrium: theory and computation

Large-scale traffic assignment requires equilibrium models that are both behaviorally plausible and computationally tractable. This paper develops a perturbed utility Markovian equilibrium (PUME) framework that preserves the scalability of link-based Markovian traffic equilibrium models and extends their applicability to settings with boundary choice probabilities, undiscounted network loading, and general link interactions. As the behavioral basis of PUME, we first develop the perturbed utility Markovian choice model (PUMCM) in which the Bellman optimality operator is defined through a convex surplus function whose gradient directly yields the optimal policy. The model generalizes existing additive random utility (ARUM) Markovian choice models and admits both interior and boundary choice probabilities. Accordingly, unattractive links can receive zero flow without imposing ex ante choice-set restrictions as in existing ARUM models. We establish conditions under which the corresponding Markov decision problem is well posed and yields a proper demand mapping. We then formulate the equilibrium as a variational inequality (VI) problem on the dual cost space and establish its existence and uniqueness. Particularly, the VI formulation of PUME accommodates non-separable and asymmetric cost structures and thus offers a more flexible modeling framework than existing Markovian traffic equilibrium (MTE) models. For computation, we develop a modified policy iteration method for network loading and a safeguarded accelerated meta-algorithm for computing equilibrium. Both algorithms are proven to be globally convergent and have demonstrated satisfactory numerical performances. Experiments on benchmark and synthetic networks further show that the proposed framework is highly scalable and robust towards a wide variety of demand-supply settings.

Dynamic Congestion Pricing in Distribution Networks via a Convex-Analytic Bilevel Reformulation

Dynamic congestion pricing is an important tool for managing congestion and coordinating distributed energy resources in active distribution networks. However, scalable mechanisms that preserve participant autonomy remain computationally challenging because the operator-resource interaction is naturally bilevel. This paper develops a convex-analytic framework in which a distribution system operator computes dynamic congestion-price adders, while decentralized energy hubs schedule flexible demand, storage, local generation, renewable curtailment, and grid import/export. Unlike conventional single-level reformulations that replace lower-level problems by Karush-Kuhn-Tucker (KKT) conditions, complementarity constraints, and big-M linearizations, the proposed model represents follower feasibility and optimality through a Fenchel-Young equality involving the convex conjugate of an extended follower objective. The remaining bilinear price-response term is handled through a penalized difference-of-convex reformulation and sequential convex approximation. The method solves continuous convex subproblems and avoids the constraint-wise complementarity and branch-and-bound scaling of mixed-integer KKT reformulations; its main computational drivers are price-response dimension and conjugate evaluation rather than binary encodings of follower inequalities. On augmented IEEE 13- and 34-node feeders, it reduces congestion by 96.89% and 96.45%, respectively, approaches centralized full-information dispatch, certifies price-response consistency to numerical precision, and yields lower residual congestion than time-limited KKT incumbents within the computational budget.

Delay-Optimal Congestion-Aware Routing and Computation Offloading in Arbitrary Networks

Emerging edge computing paradigms enable heterogeneous devices to collaborate on complex computation applications. However, for arbitrary heterogeneous edge networks, delay-optimal forwarding and computation offloading for long-term average performance remains an open problem. In this paper, we jointly optimize data/result routing and computation placement in arbitrary networks with heterogeneous node capabilities and congestion-dependent nonlinear transmission and processing costs. Despite the non-convexity of the formulated problem, by analyzing the KKT conditions, we provide a set of sufficient optimality conditions that solve the problem globally. To provide insight into such global optimality, we show that the proposed non-convex problem is geodesically convex under mild assumptions. We also show that the proposed sufficient optimality condition leads to a lower hemicontinuous solution set, providing stability against user-input perturbations. We then extend the framework to incorporate utility-based congestion control and fairness. We develop a fully distributed algorithm that converges to the global optimum. Numerical results demonstrate significant improvements over multiple baseline algorithms.

Mitigating Regional Traffic Congestion via School Start Time Scheduling: A Bilevel Alternating Optimization Approach

This paper addresses morning commute congestion caused by concentrated school-related trips in urban networks. We propose a bi-level optimization framework for regulating school start times in a multi-region urban network characterized by Macroscopic Fundamental Diagrams (MFDs), explicitly coupling system-level regulation with multi-class user-equilibrium-based departure-time choices. The Upper-Level problem jointly minimizes total time spent and deviations from current school schedules, while the Lower-Level problem models commuter behavior through a deterministic dynamic multi-class user equilibrium formulation incorporating alpha-beta-gamma preferences for travel time, earliness, and lateness costs. To address the computational challenges arising from the bilevel structure, non-convex traffic dynamics, and endogenous demand responses, an iterative algorithm alternating between the Upper- and Lower-Level problems is developed. The Upper-Level problem is approximated through a formulation solvable with standard mathematical programming solvers, while an iterative algorithm provides an approximate solution to the Lower-Level equilibrium problem. Numerical results demonstrate substantial congestion reductions and characterize the trade-off between school start-time flexibility and traffic efficiency. Sensitivity analyses further examine the effects of MFD uncertainty and scheduling preferences.