A spatio-temporally opportunistic approach to best-start-time lagrangian shortest path

Sarnath Ramnath, Zhe Jiang, Hsuan Heng Wu, Venkata M.V. Gunturi, Shashi Shekhar

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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 languageEnglish (US)
Article numberA15
Pages (from-to)274-291
Number of pages18
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - 2015
Event14th International on Symposium on Spatial and Temporal Databases, SSTD 2015 - Hong Kong, China
Duration: Aug 26 2015Aug 28 2015

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2015.


Dive into the research topics of 'A spatio-temporally opportunistic approach to best-start-time lagrangian shortest path'. Together they form a unique fingerprint.

Cite this