Geography Reference
In-Depth Information
[Airlines,
http://www.delta.com
]
between Minneapolis and Austin, TX. Here, the
travel time at 8:30 is 6 h 31 min, whereas waiting 40 min for the 9:10 flight would
yield a quicker route 2 h and 51 mins. This violation of first-in-first-out (FIFO) is
called non-FIFO behavior. Surface transportation networks such as road networks
also exhibit such behavior. For example, UPS (Joel Lovell
2007
; Deutsch
2007
)
minimizes the number of left turns in their delivery routes during heavy traffic
conditions. This leads to faster delivery and fuel savings. Second, the ranking of
alternate paths between any particular source and destination pair in the network is
not stationary. In other words, the optimal path between a source and destination for
one start time may not be optimal for other start times. In our previous example of
shortest route between the university and airport, different routes were optimal at
different times. The principle of stationarity states that, if two reward sequences
R
1
,
R
2
,
R
3
, ::: and
S
1
,
S
2
,
S
3
,.... begin with the same reward then the sequences
should be preference ordered the same way as the sequences
R
2
,
R
3
,.... and
S
2
,
S
3
,....
(Bertsekas
1987
; Russel and Norwig
1995
]. This means that, in shortest route
computation, if two journeys
e
1,
e
2,
e
3, ::: and
f
1,
f
2,
f
3, ::: start at the same node,
then the preference order of the journeys should not change for another start
time. This lack of stationarity in TD roadmaps eliminates the possibility of using
dynamic programming based techniques. Lastly, due to the potentially large and
ever growing sizes of SBD such as TD roadmaps, efficient computational methods
need to developed which can scale to large datasets.
Relatively little work has been done in the area of route collections with
minimization of travel time as the preference function (Chabini and Lan
2002
;
Kanoulas et al.
2006
; Dehne et al.
2009
) due to the FIFO assumptions. Other
related work includes skyline based techniques (Kriegel et al.
2010
) which assume
independence among dimensions and do not incorporate a Lagrangian frame of
reference. The challenges of ALSP can be addressed using the idea of earliest
arrival-time transformation and critical time points.
6.11.1
Earliest Arrival-Time Transformation (EAT)
The first challenge for solving ALSP is the non-FIFO behavior of the network.
Our work attempts to address this by converting travel information associated with
an edge into earliest arrival time (at destination) information (George et al.
2008
;
Orda and Rom
1990
). This is a two step process. First, the travel time information
is converted into arrival time information. Second, the arrival time information
is converted into earliest arrival time information. The second step captures the
possibility of arriving at an end node earlier by waiting (non-FIFO behavior).
For example, consider again Table
6.6
which shows the flight schedule between
Minneapolis and Austin, TX. Here, the result of the first step, shown in fourth
column, was obtained by adding the start time with the travel time (flight time). Now,
we would scan the arrival time information (in the fourth column) to capture any
benefits associated with waiting. For example, we can observe that a quicker path
Search WWH ::
Custom Search