Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights

Ravindra K. Ahuja (), James B. Orlin (), Stefano Pallottino () and Maria Grazia Scutellà ()
Additional contact information
Ravindra K. Ahuja: Department of Industrial and Systems Engineering, University of Florida, Gainsville, Florida
James B. Orlin: Sloan School of Management, MIT, Cambridge, Massachusetts
Stefano Pallottino: Dipartimento di Informatica, Università di Pisa, Pisa, Italy
Maria Grazia Scutellà: Dipartimento di Informatica, Università di Pisa, Pisa, Italy

Transportation Science, 2002, vol. 36, issue 3, 326-336

Abstract: This paper investigates minimum time and minimum cost path problems in street networks regulated by periodic traffic lights. We show that the minimum time path problem is polynomially solvable. On the other hand, minimum cost path problems are generally NP-hard. Special, realistic cases which are polynomially solvable are discussed.

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.36.3.326.7827 (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:36:y:2002:i:3:p:326-336

Access Statistics for this article

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