Efficient computation of shortest paths in time-dependent multiodal networks

We consider shortest paths on time-dependent multimodal transportation networks in which restrictions or preferences on the use of certain modes of transportation may arise. We model restrictions and preferences by means of regular languages. Methods for solving the corresponding problem (called the regular language constrained shortest path problem) already exist. We propose a new algorithm, called State Dependent ALT (SDALT), which runs considerably faster in many scenarios. Speed-up magnitude depends on the type of constraints. We present different versions of SDALT, including unidirectional and bidirectional search. We also provide extensive experimental results on realistic multimodal transportation networks.