TIME-DEPENDENT, LABEL-CONSTRAINED SHORTEST PATH PROBLEMS WITH APPLICATIONS

This paper considers the class of time-dependent, label-constrained shortest path problems for a given transportation network. The problem involves finding a time-dependent shortest path from an origin node to a destination node that also conforms with a string of labels delineating admissible travel mode sequences. This problem arises in the route planner module of Transportation Analysis and Simulation System, which was designed to provide transportation planners with a comprehensive detailed view of travel forecasts, traffic patterns, congestion effects and pollution due to vehicle emissions. This paper proposes a dynamic programming-based solution method for this problem by adapting efficient existing portioned shortest path algorithmic schemes to handle time dependency along with the label constraints. Several heuristics are also developed to curtail the search based on various route restrictions, indicators of progress and projected travel times to complete the trip. The exact and heuristic methods are implemented on a real test network derived from the Portland, Oregon, transportation system. Computational results using four heuristic methods--a curtailment scheme, an exponential decay variant of this scheme and a restricted delineation of the network using a suitable union of ellipsoids--were competitive, yielding solutions within 6.1%-7.0% of optimality and decreasing computational effort by 13.5%-33.6%, as compared with applying the exact method.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Sherali, H D
  • Hobeika, A G
  • Kangwalklai, S
• Publication Date: 2003-8

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 278-293
• Serial:
  • Transportation Science
  • Volume: 37
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Algorithms; Dynamic programming; Heuristic methods; Networks; Origin and destination; Route guidance; Routes and routing; Shortest path algorithms; Time dependence; Traffic simulation; Transportation modes; Travel time
• Geographic Terms: Portland (Oregon)
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00961808
• Record Type: Publication
• Files: TRIS, ATRI
• Created Date: Aug 10 2003 12:00AM