Humboldt-Universität zu Berlin - Wirtschaftswissenschaftliche Fakultät

Understanding and Improving Traffic with Unknown Demands


Traffic and logistic networks are among the most vital infrastructures of modern civilization providing access to economic activities, work, health care, and social and cultural life. However, the huge benefits of private and commercial traffic are accompanied by severe burdens in terms of congestion, exhaust gas pollution and land consumption. With the continuing effects of globalization and urbanization and in the light of the increased risk of global warming, the mitigation of the negative effects of traffic will persist to be a pressing issue in the future.
In the past years, we witnessed the emergence of several new car-related technologies that have the potential to fundamentally change the way traffic networks are managed and used: navigation devices with real-time information allow each traffic participant to make an informed decision concerning the route choice; electrical and hybrid vehicles allow mobility with reduced carbon-dioxide footprint; car-to-car and car-to-infrastructure communications pave the way to a more coordinated traffic, ultimately culminating in the use of autonomous vehicles.
The ubiquity of navigation devices and car communication today produces a wealth of data concerning the traffic demand, its elasticity, and the travel times, making these pieces of information available to the system designer. Yet, all these advancements are not able to remove a root cause of inefficient network usage — the selfish behavior of the driver (be it a human or a robot).
The behavior of systems of autonomous agents that follow their own interests instead of increasing the overall network performance are typically analyzed with the mathematical theory of non-cooperative games, and several notions of traffic equilibria have been proposed and discussed in the literature (Wardrop 1952; Rosenthal 1973, Koch and Skutella 2011). All of these models have in common that they typically assume a fixed travel demand that is then distributed in the network according to the equilibrium concept in question. The restriction to a single demand matrix may be useful when modeling a particular traffic scenario (e.g. a rush hour situation). However, when designing the overall network or when installing road-pricing schemes that are active for a long time period it is much more sensible to analyze the overall performance of the system, i.e., to study the average travel with respect to the empirical distribution of travel demands over a given time span. This is the main question addressed in this project.
Traffic models in the transportation literature are based on so-called OD-matrices, i.e., quadratic matrices that contain a row and column for each node in the network such that the entry at position $(i,j)$ of the matrix corresponds to the amount of traffic aiming to travel from node $i$ to node $j$. A static traffic equilibrium is then a splittable or unsplittable flow satisfying an equilibrium condition and flow conservation constraints for all OD-pairs. Similarly, dynamic equilibrium models, physical models, and simulations are based on OD-matrices, possibly varying in time. 
The travel demands given by the OD-matrices are subject to a high level of uncertainty. They are either generated by home interviews of potential traffic participants or estimated by traffic counts both of which give only rough estimates. Despite these uncertainties in the data, the predominant part of the literature assumes a single and deterministic OD-matrix. The goal of this project is to study the average behavior of equilibria for a given distribution of OD-matrices. The distribution may by gained, e.g., by empirical distributions of travel demands observed by navigation service providers.
We will start to examine the average efficiency of equilibria in terms of the price of anarchy and then continue to use these insights in order to design networks that have good equilibria for the empirical demands.

The average price of anarchy


Figure 1: Pigou network.

pigou poa

Figure 2: Price of anarchy in the Pigou network as a function of the flow demand.
The ratio of the total travel time of a system optimal solution and the total travel time of an equilibrium is known as the price of anarchy of a system and is a central measure for the efficiency loss due to selfish behavior indicating how well the incentives of the users are aligned with the incentives of the system designer. It has been observed that the price of anarchy of models of real-world traffic networks is considerably lower than the theoretical upper bounds from the literature. For polynomials of degree 4 (used in traffic models by the US Bureau of Standards), the theoretical upper bound on the price of anarchy is 2.151 while for real-world networks modeled with these latency functions the value is typically between 1.01 and 1.10. A possible explanation for this considerable gap between theory and practice is that for the theoretical worst-case instances, the price of anarchy is very sensitive to the demand and, in fact, only obtained for a single demand, see Figures 1 and 2. To obtain a more realistic picture of the price of anarchy of real-world traffic networks, we will study the average price of anarchy for reasonable demand distributions.

Tolls for uncertain demands

A popular way to improve the performance of traffic equilibria is road pricing. A classic result in the transportation literature is that for fixed traffic demands, the system optimum can be induced as a traffic equilibrium with tolls by charging for each edge the marginal cost of the optimal flow. However, when the traffic demand is not known, such a scheme can only be implemented with flow-dependent tolls which are problematic since they require more technical setup and can only work give the desired effects when the traffic participants can anticipate the flow-dependent tolls. They also seem to be mathematically very challenging as the current state of the art is only able to treat networks of two parallel edges. Marginal cost pricing can even lead to worse outcomes than the traffic without tolls in the case of uncertainty. The goal of this work package is to develop flow-independent road pricing schemes that work well in the presence of demands uncertainty and give a provable performance guarantee with respect to the expected total travel time.