A new time-dependent shortest path algorithm for multimodal transportation network

Abstract

The shortest path problem is a classical combinatorial optimization problem with countless real-life applications. Numerous algorithms have been proposed to solve the SPP since the classical Dijkstra algorithm, as well as new approaches to improve the algorithms’ optimality. But according to the real-world transport conditions, researchers began to study variants of this problem which include the time-dependent SPP and the multimodal networks. In this paper, we introduce our new time-dependent shortest path algorithm for multimodal transportation network. The proposed algorithm is a goal-oriented single-source single-destination algorithm. It takes into account the concept of “closeness” to the target node as heuristic to drive the search towards its destination. The optimality of the algorithm is principally based on computing a virtual path which is basically an Euclidean distance from the source to the target aiming at a restriction of the search space.