The asymmetric traffic assignment problem on large scale networks

The traffic assignment problem is a network equilibrium problem with applications in various fields. Given a directed and weighted graph and a trip rate matrix, the problem consists of determining a flow assignment on the network that satisfies the demand from each origin to each destination under a properly defined equilibrium concept. The most widely used equilibrium concept is the user equilibrium, which corresponds to the situation in which users try to minimize their personal travel times. One of the most common applications of the problem is to transportation planning. In this context, link weights are defined as functions of link flows to model the congestion phenomenon of urban transportation networks. If link weights depend on the interactions between different link flows the problem is known as asymmetric traffic assignment. Traffic assignment models are used to predict the behavior of travelers in a transportation network. The goal of this thesis is to implement and compare three different path-based algorithms for the asymmetric traffic assignment problem. Path-based algorithms consider path flows as variables. The methods we have implemented and investigated are: the gradient projection algorithm of Jayakrishnan, a heuristic method proposed by Sancho and the double projection algorithm of Panicucci, Pappalardo and Passacantando. The gradient projection algorithm was published by Jayakrishnan in 1994 for the diagonal traffic assignment problem and we extend it to the asymmetric version. The heuristic method was proposed by Sancho in 2014 and it includes a projection scheme based on the mean path cost difference between used paths. The double projection algorithm proposed by Panicucci, Pappalardo and Passacantando in 2007 is the only one among the three methods that is proven to converge on asymmetric problem instances. We compare the three algorithms on different medium to large-scale networks, representing actual transportation networks, to evaluate their performance and to verify their applicability for solving real-world problem instances. Our results show that path-based algorithms are viable for solving the asymmetric traffic assignment problem. In particular, the gradient projection algorithm and the double projection algorithm exhibit the best performance on the considered networks.