Non-Additive Shortest Paths in the Context of Traffic Assignment

The most commonly used traffic assignment (TA) model is known as user equilibrium, which assumes that all travellers minimise their travel time or generalised cost. In this paper we study a TA problem in which generalised cost is composed of two attributes, for instance travel time and toll combined through a non-linear relation. One of the solution methods for this problem is path equilibration (PE). This method decomposes the original problem into sub-problems that are solved sequentially by origin-destination pair performing multiple calculations that identify paths which are minimal w.r.t. the generalised cost function. Because of the non-linear nature of generalised cost, the shortest path sub-problem is non-additive and conventional shortest path algorithms cannot be applied. The non-additive shortest path (NSP) sub-problem is the bottleneck operation of PE. We propose and analyse different ways to speed-up NSP computation by exploiting the properties of TA. Unlike in standard one-off NSP computations, we propose to exploit knowledge of existing paths from previous TA iterations, and use the generalised cost function to narrow the search space. We investigate two flow update strategies and propose a new one based on randomising shortest path calculations. Our computational experiments compare the presented strategies for solving NSP in TA, and show that much larger TA problem instances can be solved to higher precision than previously done in the literature. We carefully analyse and discuss performance of the different speed-up approaches