Article ID: | iaor2004328 |
Country: | United States |
Volume: | 36 |
Issue: | 3 |
Start Page Number: | 326 |
End Page Number: | 336 |
Publication Date: | Aug 2002 |
Journal: | Trans Science |
Authors: | Pallottino Stefano, Scutell Maria Grazia, Orlin James B., Ahuja Ravindra K. |
Keywords: | numerical analysis |
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.