Dynamic shortest paths minimizing travel times and costs

In this paper, we study dynamic shortest path problems that determine a shortest path from a specified source node to every other node in the network where arc travel times change dynamically. We consider two problems: the minimum-time walk problem and the minimum-cost walk problem. The minimum-time walk problem is to find a walk with the minimum travel time. The minimum-cost walk problem is to find a walk with the minimum weighted sum of the travel time and the excess travel time (over the minimum possible travel time). The minimum-time walk problem is known to be polynomially solvable for a class of networks called first in first out networks. In this paper, (i) we show that the minimum-cost walk problem is an NP-hard problem; (ii) we develop a pseudopolynomial-time algorithm to solve the minimum-cost walk problem (for integer travel times); and (iii) we develop a polynomial-time algorithm for the minimum-time walk problem arising in road networks with traffic lights.