A critical-time-point approach to all-start-time Lagrangian shortest paths: A summary of results

Venkata M V Gunturi, Ernesto Nunes, KwangSoo Yang, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

Given a spatio-temporal network, a source, a destination, and a start-time interval, the All-start-time Lagrangian Shortest Paths (ALSP) problem determines a path set which includes the shortest path for every start time in the given interval. ALSP is important for critical societal applications related to air travel, road travel, and other spatio-temporal networks. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths, meaning that a candidate path which is optimal for one start time may not be optimal for others. Determining a shortest path for each start-time leads to redundant computations across consecutive start times sharing a common solution. The proposed approach reduces this redundancy by determining the critical time points at which an optimal path may change. Theoretical analysis and experimental results show that this approach performs better than naive approaches particularly when there are few critical time points.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
Pages74-91
Number of pages18
DOIs
StatePublished - Sep 19 2011
Event12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011 - Minneapolis, MN, United States
Duration: Aug 24 2011Aug 26 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6849 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
CountryUnited States
CityMinneapolis, MN
Period8/24/118/26/11

Fingerprint Dive into the research topics of 'A critical-time-point approach to all-start-time Lagrangian shortest paths: A summary of results'. Together they form a unique fingerprint.

Cite this