Algorithm for Intermodal Optimal Multidestination Tour with Dynamic Travel Times

This paper presents an efficient algorithm that finds the intermodal optimal tour (origin to origin) in a time-dependent transportation network while the algorithm implicitly solves the park-and-ride facility choice problem with the inherent park-and-ride constraints for a traveler with a sequence of destinations to visit. To solve the problem, a network expansion technique that captures the constraints of park-and-ride behavior in the model and that transforms the park-and-ride choice problem into a dynamic network flow problem is introduced. An efficient iterative labeling algorithm that finds the optimal intermodal tour to serve the sequence of activities is also introduced. Multisource shortest-path runs are used in the iterative labeling algorithm to find the optimal tour with several intermediate destinations in an efficient manner. The performance of the algorithm is compared with the performance of existing approaches, and improvement is indicated. The solution method proposed benefits from the advantages of Dijkstra's shortest-path algorithm, which is made possible by (a) a nontrivial transformation of the original problem into a dynamic network flow problem and (b) an innovative use of a multisource shortest path in the context of origin–destination choice. The solution algorithm integrates time-dependent auto and transit shortest-path algorithms to find the optimal tour. The algorithm is implemented, coded, and tested on a real network, and the results are promising.