The Best-start-time Lagrangian Shortest Path (BLSP) problem requires choosing the start time that yields the shortest path in a time-dependent graph. The inputs to the problem are a spatio-temporal network, an origin, o, a destination, d, and a discrete interval of possible start times. The solution is a path, P, and a start time, t, such that the total time taken to travel along P, starting at t, is no greater than the time taken to travel along any path from o to d, if we start in the given interval. The problem is important when the traveler is flexible about the start time, but would like to select a start time that minimizes the travel time. Its computational challenges arise from the large number of start time instants, and the manner in which the length of the shortest lagrangian path can vary from one start time instant to the next. Earlier work focused largely on finding the shortest path for a single start time. Researchers recently considered the BLSP problem, and proposed an approach based on finding the shortest lagrangian path for each start time, and then picking the best. Such an approach performs redundant evaluation of common sub-expressions, because time is explored in a sequential manner. We present an algorithm, BESTIMES, and propose an implementation that uses a Temporally Expanded priority queue. Our algorithm is built on the idea of “spatio-temporal opportunism”, which allows us to navigate both space and time simultaneously in a non-sequential manner and appropriately combine sub-paths. Theoretical analysis and experiments on real data show that there is a welldefined range of inputs over which this approach performs significantly better than previous approaches.
|Original language||English (US)|
|Number of pages||18|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|State||Published - 2015|
|Event||14th International on Symposium on Spatial and Temporal Databases, SSTD 2015 - Hong Kong, China|
Duration: Aug 26 2015 → Aug 28 2015
Bibliographical noteFunding Information:
We are grateful to the members of the Spatial Database Research Group at the University of Minnesota and Dr Betsy George for their valuable feedback, and Kim Koffolt for editing help. This material is based upon work supported by the National Science Foundation under Grant No. 1029711, IIS-1320580, 0940818 and IIS-1218168, the USDOD under Grant No. HM1582-08-1-0017 and HM0210-13-1-0005, and the University of Minnesota under the OVPR U-Spatial.
© Springer International Publishing Switzerland 2015.