Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights
Published Online:1 Aug 2002https://doi.org/10.1287/trsc.36.3.326.7827
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.
