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

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

Abstract

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.

Citation

Gunturi, V. M., Shekhar, S., & Yang, K. (2015). A Critical-Time-Point Approach to All-Departure-Time Lagrangian Shortest Paths. IEEE Transactions on Knowledge and Data Engineering, 27(10), 2591-2603. https://doi.org/10.1109/TKDE.2015.2426701

• Journal Article Type: Article
• Online Publication Date: Apr 27, 2015
• Publication Date: Oct 1, 2015
• Deposit Date: Sep 27, 2023
• Journal: IEEE Transactions on Knowledge and Data Engineering
• Print ISSN: 1041-4347
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 27
• Issue: 10
• Pages: 2591-2603
• DOI: https://doi.org/10.1109/TKDE.2015.2426701
• Keywords: Spatial databases; Road networks and Geographic Information Systems
• Public URL: https://hull-repository.worktribe.com/output/4401702