Time‐dependent shortest paths with discounted waits. Issue 3 (14th April 2019)

• Record Type: Journal Article
• Authors: Omer, Jérémy; Poss, Michael
• Is Part Of: Networks. Volume 74:Issue 3(2019)
• Page Start: 287
• Page End: 301
• Publication Date: 2019-04-14
• Subjects: approximation -- NP‐completeness -- dynamic programming -- time‐dependent networks -- shortest paths -- waiting; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21885
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving time. Although optimal solutions may contain cycles and pseudo‐polynomially many arcs, we provide a representation of the solutions that is polynomial in the absolute value of the inverse of the slopes as well as in the dimensions of the graph. We further prove that the problem is NP ‐Hard when the slopes are integer. We introduce a restriction of the problem where waits must be integer and propose pseudo‐polynomial algorithms for the latter. We also provide a pseudo‐FPTAS, polynomial in the ratio between the bound on the total waiting time and the minimum travel time. Finally, we discuss harder variants of the problem and show their inapproximability.