Updating Paths in Time-Varying Networks Given Arc Weight Changes

Elise Miller-Hooks () and Baiyu Yang ()
Additional contact information
Elise Miller-Hooks: Department of Civil and Environmental Engineering, 1173 Glenn Martin Hall, University of Maryland, College Park, Maryland 20742
Baiyu Yang: Operations Research and Decision Support, American Airlines, 4333 Amon Carter Boulevard, MD 5358, Fort Worth, Texas 76155

Transportation Science, 2005, vol. 39, issue 4, 451-464

Abstract: Many transportation applications, including applications in intelligent transportation systems, require the solution of a series of shortest path problems in which only the travel time along a set of arcs of the network change from one problem instance to the next. One could use an existing path algorithm to solve each problem instance independently as it arises. However, significant savings in computation time can often be achieved through the use of a reoptimization algorithm that would begin from the prior solution in determining the updated optimal solution for the given arc travel-time changes. Such quick solution is critical for providing routing instructions to travelers in real time as travel-time information is retrieved from the traffic network. Numerous works have presented reoptimization techniques for use in updating shortest path trees in deterministic and static networks; however, it appears that no reoptimization technique exists in the literature for updating paths where future travel times in time-varying networks change. In this paper, such procedures are proposed. The proposed techniques can provide updated solutions given simultaneous and arbitrary changes (increasing and decreasing in value) in any number of network arcs. Further, this technique can be extended for use in stochastic networks.

Keywords: dynamic networks; stochastic networks; shortest paths; optimal routing; reoptimization; intelligent transportation systems (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1040.0112 (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:39:y:2005:i:4:p:451-464

Access Statistics for this article

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