Minimum time and minimum cost path problems in street networks with traffic lights

Minimum time and minimum cost path problems in street networks with traffic lights
R.K. Ahuja, J.B. Orlin, S. Pallottino, and M. Scutella, Transportation Science 36, 326-336, 2002

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.