A Time-Dependent Intermodal A* Algorithm: Methodology and Implementation on a Large-Scale Network

Abstract

This paper proposes a time-dependent intermodal A* (TDIMA*) algorithm. The algorithm works on a multimodal network with transit, walking, and vehicular network links, and finds paths for the three major modes (transit, walking, driving) and any feasible combination thereof (e.g., park-and-ride). Turn penalties on the vehicular network and progressive transfer penalties on the transit network are considered for improved realism. Moreover, upper bounds to prevent excessive waiting and walking are introduced, as well as an upper bound on driving for the park-and-ride (PNR) mode. The algorithm is validated on the large-scale Chicago Regional network using real-world trips against the Google Directions API and the Regional Transit Authority router.