This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Sherali, H. D. Articles by Kangwalklai, S. Search for Related Content

Time-Dependent, Label-Constrained Shortest Path Problems with Applications

Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Department of Civil and Environmental Engineering (0105), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Accenture, One Market, Spear Street Tower, Suite 3700, San Francisco, California 94105
hanifs{at}vt.edu
hobeika{at}vt.edu
sasikul.kangwalklai{at}accenture.com

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 theRoute Planner Moduleof Transportation Analysis Simulation System (TRANSIMS), which is developed by theLos Alamos National Laboratoryand is part of a multitrackTravel Model Improvement Programsponsored by the U.S. 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.

History: Received: April 2001; revised: February 2001; accepted: February 2001.