Efficient algorithms for the 2-Way Multi Modal Shortest Path Problem

7International audienceWe consider the 2-Way Multi Modal Shortest Path Problem (2WMMSPP). Its goal is tofi nd two multi modal paths with total minimal cost, an outgoing path and a return path. The main di fficulty lies in the fact that if a private car or bicycle is used during the outgoing path, it has to be picked up during the return path. The shortest return path is typically not equal to the shortest outgoing path as tra ffic conditions and timetables of public transportation vary throughout the day. In this paper we propose an e fficient algorithm based on bi-directional search and provide experimental results on a realistic multi modal transportation network