A Critical-Time-Point Approach to All-Departure-Time Lagrangian Shortest Paths

Venkata M.V. Gunturi, Shashi Shekhar, Kwangsoo Yang

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Given a spatiooral network, a source, a destination, and a desired departure time interval, the All-departure-time Lagrangian Shortest Paths (ALSP) problem determines a set which includes the shortest path for every departure time in the given interval. ALSP is important for critical societal applications such as eco-routing. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths across distinct departure-times. Current related work for reducing the redundant work, across consecutive departure-times sharing a common solution, exploits only partial information e.g., the earliest feasible arrival time of a path. In contrast, our approach uses all available information, e.g., the entire time series of arrival times for all departure-times. This allows elimination of all knowable redundant computation based on complete information available at hand. We operationalize this idea through the concept of critical-time-points (CTP), i.e., departure-times before which ranking among candidate paths cannot change. In our preliminary work, we proposed a CTP based forward search strategy. In this paper, we propose a CTP based temporal bi-directional search for the ALSP problem via a novel impromptu rendezvous termination condition. Theoretical and experimental analysis show that the proposed approach outperforms the related work approaches particularly when there are few critical-time-points.

Original languageEnglish (US)
Article number7095582
Pages (from-to)2591-2603
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number10
StatePublished - Oct 1 2015

Bibliographical note

Publisher Copyright:
© 1989-2012 IEEE.


  • Road networks and Geographic Information Systems
  • Spatial databases


Dive into the research topics of 'A Critical-Time-Point Approach to All-Departure-Time Lagrangian Shortest Paths'. Together they form a unique fingerprint.

Cite this