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

R. K. Ahuja, J. B. Orlin, S. Pallottino, and M. G. Scutella. Transportation Science Volume 36, 326-336, 2002.

This paper investigates minimum time and minimum cost path problems in street networks regulated by periodic traffic lights.W e 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.