Non-additive shortest path in the context of traffic assignment

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.