Spatio-temporal Networks: Modeling, Storing, and Querying Temporally-Detailed Roadmaps - Space-Time Integration in Geography and GIScience - page 87

Tabl e 6. 5 Predicate operators in time-aggregated graphs
exists_at_time_t

exists_after_time_t

Node exists(node u,at_time_t) exists(node u,after_time_t)

Edge exists(node u,node v,at_time_t) exists(node u,node v,after_time_t)

Route exists(node u,node v,a_route r,at_time_t) exists(node u,node v,a_route

r,after_time_t)

Flow exists(node u,node v,a_flow r,at_time_t) exists(node u,node v,a_flow r,after_time_t)

a b

N1 N1 N1

N1 N1 N1 N1

1,1,

N2

N1

(a,s)

N2 N2 N2 N2 N2 N2 N2

(a,s) (a,s)

2,2,2 2,2,3

N3 N3 N3 N3 N3

N3 N3

(a,s)

N3

N4

1, ,4

N4 N4 N4 N4 N4

N4 N4

t=5 t=6 t=7

t=1 t=2 t=3 t=4

Time Expanded Graph Time−aggregated Graph

Fig. 6.7 Time-aggregated graph vs. time expanded graph

6.11 Case-Study: STN Queries

SBD magnifies the already partial and ambiguous nature of a traditional routing
query. This is because a typical routing query specified by a start location and a
destination may result in multiple answers. The apparent ambiguity in the shortest
path query is clearly visible in the multiple candidate routes returned for a single
start and destination pair in common web-based routing services like [Google Maps,
http://maps.google.com , Mapquest, http://www.mapquest.com/ , Maps, http://www.
bing.com/maps/ ] . For example, consider Fig. 6.8 a, which shows two candidate
shortest travel time routes from the University of Minnesota to MSP International
Airport. This ambiguity increases tremendously with the availability of SDB
datasets, resulting in increased computational costs due to re-computation that may
be necessary for thousands of possible start times. Let us consider this issue in the
context of TD roadmaps via the all start-time Lagrangian shortest paths (ALSP)
problem.
Given a TD roadmap, a source, a destination, and a start-time interval, an ALSP
problem determines a route collection which includes the shortest path for every
start time in the interval. The ALSP output includes both the shortest paths and
the corresponding set of time instants when the paths are optimal. For example, for