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 FIFO networks. In this paper, (ⅰ) we show that the minimum-cost walk problem is an NP-hard problem; (ⅱ) we develop a pseu-dopolynomial-time algorithm to solve the minimum-cost walk problem (for integer travel times); and (ⅲ) we develop a polynomial-time algorithm for the minimum-time walk problem arising in road networks with traffic lights.