Dynamic Shortest-Path Algorithm for Continuous Arc Travel Times: Implication for Traffic Incident Management

To achieve the desired computational speed, existing algorithms for time-dependent (or dynamic) shortest-path problems call for the unrealistic aggregation of travel time as multiples of a given time increment. While the time increment can be varied between, say, peak and off-peak periods, it still has its obvious limitation on granularity. An improved solution algorithm is proposed for the all-to-one or one-to-all time-dependent versions of the problem. The algorithms are solidly founded on Bellman’s principle of optimality and apply to continuous or real-value arc travel times (rather than the current practice of discrete-time specifications). The new algorithms are practical in computational speed, and they capture a more realistic metric for route choice. In this case, a relatively coarse time increment can be used throughout the analysis, yet it is compatible with any continuous or real-value arc travel times. To support these claims, computational results that consider various network sizes, densities, and numbers of time increments are provided. For future extensions, a non-first-in-first-out fastest-path and minimum-cost-path algorithm is proposed. A generalized cost (or disutility arc function) is defined to combine the two, on the basis of which route choices are made. For route-choice decisions, it is stipulated that adoption of such a disutility specification mandates a continuous valuation of arc time and cost. Instead of an all-to-one implementation, a one-to-all implementation is suggested under these circumstances. The latter approach, when complemented by the speed of algorithmic execution, facilitates real-world applications. It allows the driver to value incident delay and risks in route choice on a real-time basis.

• Record URL:
  • https://doi.org/10.3141/2089-07
• Summary URL:
  • http://scholar.google.com/scholar_lookup?title=Dynamic+Shortest-Path+Algorithm+for+Continuous+Arc+Travel+Times%3a+Implication+for+Traffic+Incident+Management&author=J.+Hu&author=Y.+Chan&publication_year=2008
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/isbn/9780309126014
• Authors:
  • Hu, Jian
  • Chan, Yupo
• Publication Date: 2008

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 51-57
• Monograph Title: Network Analysis for Policy and Logistics
• Serial:
  • Transportation Research Record: Journal of the Transportation Research Board
  • Issue Number: 2089
  • Publisher: Transportation Research Board
  • ISSN: 0361-1981

Subject/Index Terms

• TRT Terms: Incident management; Route choice; Shortest path algorithms; Time dependence; Traffic delays; Traffic incidents; Travel time
• Uncontrolled Terms: Computational efficiency
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning; I73: Traffic Control;

Filing Info

• Accession Number: 01099138
• Record Type: Publication
• ISBN: 9780309126014
• Files: TRIS, TRB, ATRI
• Created Date: May 21 2008 7:05AM