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

We shall investigate minimum time and minimum cost path problems in street networks regulated by traffic lights. We shall show that the minimum time path problem is polynomially solvable. On the other hand, in general minimum cost path problems are NP-hard. Particular but realistic cases which are polynomially solvable will be discussed.