User Equilibrium Delays in the Traffic Equilibrium Problem

Alexander Rudyk, Bachelor Thesis, Summer 2007

Supervisor: Vania Dos Santos Eleuterio

Keywords: Traffic Assignment Problem, User Equilibrium, Social Optimum, Delays, Multicommodity Flow, Linear Programming, Complementary Slackness Conditions

Abstract

This bachelor thesis addresses the modeling of the delays faced by private drivers in traffic networks when they are free to choose their way: a traffic network is considered at user equilibrium (UE) when all traffic patterns stabilize and no driver has an incentive to change its current route, Wardrop’s First Principle, 1952. In contrary a traffic network is at social optimum (SO) when a central organization routes assign routes to drivers in order to collectively optimize the utilization of the network, Wardrop’s Second Principle, 1952.
The work is focused on the traffic assignment model recently developed by Nesterov and De Palma, 1998. The SO is modeled by a minimum linear cost multicommodity flow problem, where the total travel time is minimized under flow capacity constraints. The UE is derived as a consequence of the complementary slackness conditions of linear programming. UE and SO have the same distribution of the traffic flows and only differ in the delays occurring on congested roads, namely, the dual variables corresponding to the capacity constraints. Existence and uniqueness of the delays, i.e., the dual variables, are the two main topics investigated in this bachelor thesis.
It was shown that delays are unbounded if and only if there is a road in the traffic network such that any decrease of its flow capacity would turn the multicommodity flow problem into an infeasible one. Two algorithms were developed for bounding the UE delays and tested. Bounded and not unique delays were common in high loaded scenarios. The same algorithms were also used for investigating Braess paradox type of problems.