DYNAMIC SHORTEST PATHS MINIMIZING TRAVEL TIMES AND COSTS

Ravindra Ahuja, James Orlin, Stefano Pallottino and Maria Scutella

No 4390-02, Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management

Abstract: In this paper, we study dynamic shortest path problems that determine a shortest path from a specified source node to every other node in the network where arc travel times change dynamically. We consider two problems: the minimum time walk problem and the minimum cost walk problem. The minimum time walk problem is to find a walk with the minimum travel time. The minimum cost walk problem is to find a walk with the minimum weighted sum of the travel time and the excess travel time (over the minimum possible travel time). The minimum time walk problem is known to be polynomially solvable for a class of networks called FIFO networks. In this paper: (i) we show that the minimum cost walk problem is an NP-hard problem; (ii) we develop a pseudopolynomial-time algorithm to solve the minimum cost walk problem (for integer travel times); and (iii) we develop a polynomial-time algorithm for the minimum time walk problem arising in road networks with traffic light

Keywords: Dynamic shortest path; arc travel; FIFO networks (search for similar items in EconPapers)
Date: 2003-01-27
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://hdl.handle.net/1721.1/1798 (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:mit:sloanp:1798

Ordering information: This working paper can be ordered from
MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA

Access Statistics for this paper

More papers in Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA. Contact information at EDIRC.
Bibliographic data for series maintained by None ( this e-mail address is bad, please contact ).