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:
  • 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

Subject/Index Terms

Filing Info

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