Time-dependent shortest path with discounted waits - Institut de Recherche Mathématiques de Rennes Accéder directement au contenu
Article Dans Une Revue Networks Année : 2019

Time-dependent shortest path with discounted waits

Résumé

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.
Fichier principal
Vignette du fichier
main_rev.pdf (386.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01836007 , version 1 (11-07-2018)
hal-01836007 , version 2 (17-10-2018)
hal-01836007 , version 3 (15-04-2019)

Identifiants

Citer

Jérémy Omer, Michael Poss. Time-dependent shortest path with discounted waits. Networks, 2019, 74 (3), pp.287-301. ⟨10.1002/net.21885⟩. ⟨hal-01836007v3⟩
286 Consultations
591 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More