Geography Reference
In-Depth Information
for start time 8:30 am can be obtained by waiting for 40 mins. The last column of
the table shows the result of the second step. To date, we have applied this approach
only to the travel time preference function.
6.11.2
Critical Time Points
A naive approach for solving the non-FIFO ALSP problem would involve deter-
mining the shortest path for each start time in the interval using techniques (George
et al.
2007b
; Ding et al.
2008
; Demiryurek et al.
2011
;OrdaandRom
1990
; Chabini
1998
; Delling
2008
; Delling and Wagner
2007
; Demiryurek et al.
2010
] developed
for single-start time shortest paths. This leads to redundant re-computation of the
shortest path across consecutive start times sharing a common solution. Some
efficiencies can be gained using a time series generalization of a label-correcting
algorithm (George et al.
2007b
). However, this approach still entails large number
of redundant computations (Gunturi et al.
2011
). Here, we propose the use of
critical time points to reduce this redundancy. For instance, consider again the
problem of determining the shortest path between University of Minnesota and MSP
international airport over a time interval of 7:30 am through 10:30 am. Figure
6.8
b
shows the preferred paths at some time instants during this time interval, and
Fig.
6.8
c shows the travel-times for the candidate paths for all start-times during
this interval. The dotted lines across bars are drawn for ease of understanding only.
As can be seen, the Hiawatha route is faster for times in the interval [7:30 am
8:30 am], whereas the 35 W route is faster for times in the interval [9:30 am
10:30 am]. This shows that the shortest path changed at some instant inside the
interval [8:31 9:30]. For sake of simplicity we assume that the shortest path changed
at 9:30 am. We define this time instant as a
critical time point
. Critical time
points can be determined by computing the earliest intersection points between
the functions representing the total travel time of paths. For example, the earliest
intersection point of the Hiawatha route was at 9:30 am (with 35 W route function).
Therefore, it would be redundant to recompute shortest paths for all times in interval
[7:31 am 9:29 am] and [9:31 am 10:30 am] since the optimal path for times within
each interval did not change. This approach is particularly useful in cases when there
are a fewer number of critical time points.
Thus, critical time points inspire a divide and conquer based approach to handle
network non-stationarity. In this approach we divide the time interval over which
the network exhibits non-stationarity into smaller intervals which are guaranteed to
show stationary behavior. These intervals are determined by computing the critical
time points, that is, the time points at which the cost functions representing the total
cost of the path as a function of time intersect. Now, within these intervals, the
shortest path can be easily computed using a single run of a dynamic programming
(DP) based approach (George et al.
2007b
). In our previous example of determining
the shortest paths between the university and the airport over an interval of
[7:30 am 10:30 am], the critical time point was 9:30 am. This created two discrete
Search WWH ::
Custom Search