Premium
A polynomial algorithm for minimizing travel time in consistent time‐dependent networks with waits
Author(s) -
Omer Jérémy,
Poss Michael
Publication year - 2021
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21994
Subject(s) - time complexity , travel time , piecewise , path (computing) , piecewise linear function , graph , shortest path problem , algorithm , computer science , mathematics , running time , response time , polynomial , mathematical optimization , combinatorics , mathematical analysis , geometry , transport engineering , engineering , programming language , computer graphics (images)
We consider a time‐dependent shortest path problem with possible waiting at some nodes of the graph and a global bound W on the total waiting time. The goal is to minimize the time traveled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when the travel time functions are piecewise linear and continuous. The algorithm relies on a recurrence relation characterized by a bound ω on the total waiting time, where 0 ≤ ω ≤ W . We show that only a small number of values ω 1 , ω 2 , …, ω K need to be considered, where K depends on the total number of breakpoints of all travel time functions.