A Critical-time-point Approach to All-departure-time Lagrangian Shortest Paths

A Critical-time-point Approach to All-departure-time Lagrangian Shortest Paths

Abstract— Given a spatio-temporal network, a source, a destination, and a desired departure time interval, the All-departure time Lagrangian Shortest Paths < Final Year Projects 2016 > 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.