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

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.

https://doi.org/10.1287/trsc.36.3.326.7827

Cite as:

@article{Ahuja_2002,
	doi = {10.1287/trsc.36.3.326.7827},
	url = {https://doi.org/10.1287%2Ftrsc.36.3.326.7827},
	year = 2002,
	month = {aug},
	publisher = {Institute for Operations Research and the Management Sciences ({INFORMS})},
	volume = {36},
	number = {3},
	pages = {326--336},
	author = {Ravindra K. Ahuja and James B. Orlin and Stefano Pallottino and Maria Grazia Scutell{`{a}}},
	title = {Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights},
	journal = {Transportation Science}
}