Time-dependent shortest paths with discounted waits

Time-dependent shortest paths with discounted waits

Authors: Omer, Jérémy; Poss, Michael

Networks - 2019 Volume 74, Pages 287-301

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 -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.

https://doi.org/10.1002/net.21885

Cite as:

@article{Omer_2019,
	doi = {10.1002/net.21885},
	url = {https://doi.org/10.1002%2Fnet.21885},
	year = 2019,
	month = {apr},
	publisher = {Wiley},
	volume = {74},
	number = {3},
	pages = {287--301},
	author = {J{'{e}}r{'{e}}my Omer and Michael Poss},
	title = {Time-dependent shortest paths with discounted waits},
	journal = {Networks}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close