Non-Additive Shortest Paths in the Context of Traffic Assignment

O Perederieieva, A Raith, Marie Schmidt

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)325-338
Number of pages14
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 7 Feb 2018

Research programs



Dive into the research topics of 'Non-Additive Shortest Paths in the Context of Traffic Assignment'. Together they form a unique fingerprint.

Cite this