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

Hanif D. Sherali (), Antoine G. Hobeika () and Sasikul Kangwalklai ()
Additional contact information
Hanif D. Sherali: Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Antoine G. Hobeika: Department of Civil and Environmental Engineering (0105), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061
Sasikul Kangwalklai: Accenture, One Market, Spear Street Tower, Suite 3700, San Francisco, California 94105

Transportation Science, 2003, vol. 37, issue 3, 278-293

Abstract: 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 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.

Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.37.3.278.16042 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:37:y:2003:i:3:p:278-293

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().