Time-dependent, label-constrained shortest path problems with applications

In this paper, we consider a variant of shortest path problems where, in addition to congestion related time-dependent link travel times on a given transportation network, we also have specific labels for each arc denoting particular modes of travel. The problem then involves finding a time-dependent shortest path from an origin node to a destination node that also conforms with some admissible string of labels. This problem arises in the Route Planner Module of Transportation Analysis Simulation System (TRANSIMS), which is developed by the Los Alamos National Laboratory and is part of a multitrack Travel Model Improvement Program sponsored by the US Department of Transportation (DOT) and the Environmental Protection Agency (EPA). We propose an effective algorithm for this problem by adapting efficient existing partitioned shortest path algorithmic schemes to handle time dependency along with the label constraints. We also develop several heuristics to curtail the search based on various route restrictions, indicators of progress, and projected travel times to complete the trip. The proposed methodology is applied to solve some real multimodal test problems related to the Portland, Oregon, transportation system. Computational results for both the exact method and the heuristic curtailing schemes are provided.