The Traffic Equilibrium Problem

Starting with the mass-production of automobiles in the beginning of last century, transport analysts and economists first and, later, mathematicians and computer scientists have considered ways of coping with road congestion. From a driver (user) point of view, the highest economical impact of congestion translates into delays. Wardrop [War52] pointed out in his Second Principle that con-gestion can only occur if users choose their routes individually to optimize their own utility functions, which is usually the case in transportation networks. Thus the main focus of research has been on ways of understanding and possibly relieving congestion in this setting in which drivers are free to choose their way. From a game-theoretic point of view, a transportation network is considered at equilibrium when all traffic patterns stabilize (and, thus, so do the delays) and no driver has any incentive to change its current route (Wardrop’s First Principle, [War52]). In this case, we will say the system is at a user equilibrium state (UE). The other side of the spectrum is when there is a central decision maker that assigns routes to drivers. In this case, the goal is to collectively optimize the utilization of the network; when this goal is achieved we will say that the system is at a social optimum state (SO). The existence and uniqueness of either states is a very non-trivial question, but they can be guaranteed in certain cases for some mathematical models