Abstract: Traffic is a significant source of global carbon emissions. In this paper, we study how carbon pricing can be used to guide traffic towards equilibria that respect given emission budgets. In particular, we consider a general multi-commodity flow model with flow-dependent externalities. These externalities may represent carbon emissions, entering a priced area, or the traversal of paths regulated by tradable credit schemes. We provide a complete characterization of all flows that can be attained as Wardrop equilibria when assigning a single price to each externality. More precisely, we show that every externality budget achievable by any feasible flow in the network can also be achieved as a Wardrop equilibrium by setting appropriate prices. For extremal and Pareto-minimal budgets, we show that there are prices such that all equilibria respect the budgets. Although the proofs of existence of these particular prices rely on fixed-point arguments and are non-constructive, we show that in the case where the equilibrium minimizes a convex potential, the prices can be obtained as Lagrange multipliers of a suitable convex program. In the case of a single externality, we prove that the total externality caused by the traffic flow is decreasing in the price. For increasing, continuous, and piecewise affine travel time functions with a single externality, we give an output-polynomial algorithm that computes all equilibria implementable by pricing the externality. Even though there are networks where the output size is exponential in the input size, we show that the minimal price obeying a given budget can be computed in polynomial time. This allows the efficient computation of the market price of tradable credit schemes. Overall, our results show that carbon pricing is a viable and (under mild assumptions) tractable approach to achieve all feasible emission goals in traffic networks.

Abstract: Stochastic effects significantly influence the dynamics of traffic flows. Many dynamic traffic assignment (DTA) models attempt to capture these effects by prescribing a specific ratio that determines how flow splits across different routes based on the routes’ costs. In this paper, we propose a new framework for DTA that incorporates the interplay between the routing decisions of each single traffic participant, the stochastic nature of predicting the future state of the network, and the physical flow dynamics. Our framework consists of an edge loading operator modeling the physical flow propagation and a routing operator modeling the routing behavior of traffic participants. The routing operator is assumed to be set-valued and capable to model complex (deterministic) equilibrium conditions as well as stochastic equilibrium conditions assuming that measurements for predicting traffic are noisy. As our main results, we derive several quite general equilibrium existence and uniqueness results which not only subsume known results from the literature but also lead to new results. Specifically, for the new stochastic prediction equilibrium, we show existence and uniqueness under natural assumptions on the probability distribution over the predictions.

Abstract: Modelling passenger assignments in public transport networks is a fundamental task for city planners, especially when deliberating network infrastructure decisions. A key aspect of a realistic model for passenger assignments is to integrate selfish routing behaviour of passengers on the one hand, and the limited vehicle capacities on the other hand. We formulate a side-constrained user equilibrium model in a schedule-based time-expanded transit network, where passengers are modelled via a continuum of non-atomic agents that want to travel with a fixed start time from a user-specific origin to a destination. An agent’s route may comprise several rides along given lines, each using vehicles with hard loading capacities. We give a characterization of (side-constrained) user equilibria via a quasi-variational inequality and prove their existence by generalizing a well-known existence result of Bernstein and Smith (Transp. Sci., 1994). We further derive a polynomial time algorithm for single-commodity instances and an exact finite time algorithm for the multi-commodity case. Based on our quasi-variational characterization, we finally devise a fast heuristic computing user equilibria, which is tested on real-world instances based on data gained from the Hamburg S-Bahn system and the Swiss long-distance train network. It turns out that w.r.t. the total travel time, the computed user-equilibria are quite efficient compared to a system optimum, which neglects equilibrium constraints and only minimizes total travel time.

Abstract: We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We describe a general mathematical model which, in particular, includes the settings leading to IDE and DE. On the theoretical side we show existence of equilibrium solutions under some additional assumptions while on the practical side we implement a machine-learned predictor and compare it to other static predictors.

Abstract: We propose a process algebra for link layer protocols, featuring a unique mechanism for modelling frame collisions. We also formalise suitable liveness properties for link layer protocols specified in this framework. To show applicability we model and analyse two versions of the Carrier-Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol. Our analysis confirms the hidden station problem for the version without virtual carrier sensing. However, we show that the version with virtual carrier sensing not only overcomes this problem, but also the exposed station problem with probability 1. Yet the protocol cannot guarantee packet delivery, not even with probability 1.