Given a query point in a spatial network, the reachability query retrieves all points of interest that are reachable from the query point in a specific amount of time respecting network constraints. Reachability queries have a number of interesting applications, and for road networks efficient solutions have been proposed. Road networks are time-independent, i.e., the cost for traversing an edge is constant over time. Efficient algorithms for road networks heavily rely on precomputing shortest paths. In public transport networks, however, the edge costs depend on schedules, which renders most solutions for road networks inefficient. In particular, shortest paths between node pairs cannot be easily precomputed because they change over time. The goal of this work is to develop efficient solutions for reachability queries in public transport networks. The core idea is to partition the network into cells and compute time upper and lower bounds to traverse a cell. At query time, the reachable region is expanded cell by cell (instead of expanding edge by edge). All points of interest that are reachable using upper bound expansion are part of the result; all points that are not reachable in a lower bound expansion can safely be discarded; all other nodes are candidates and must be verified. This paper presents the expansion algorithm and and discusses interesting research directions regarding good network partitions, effective bounds, and efficient candidate verification.
Analyzing the reachability of geographic locations has many interesting application, for example, allocating hospitals and schools in urban planning, positioning franchise stores in geomarketing, or exploring the surroundings in mobile applications. In spatial networks, the reachability of a location does not only depend on the Euclidean distance, but also the restrictions and the structure of the network must be taken into account. For example, cars can only move on roads and must obey traffic rules, buses have schedules and can only be boarded at bus stops. Networks that allow different transport modes (e.g., pedestrian, car, and public transport) are called multi-modal networks.
Queries over spatial networks are essential for spatial and
spatio-temporal databases [
A reachability query retrieves all points of interest (POI) in the network that reach (resp. are reachable from) a given query point within a given time frame (the cost budget ) at a specific point in time. For example, in the query “return all students that can reach their school at 8am within 10 minutes either on foot or via public transport”, the student homes are the POIs, the query point is the school, the cost budget is 10 minutes, and the time point is 8am.
There are two basic approaches to solve reachability queries: (a) compute the subset of the network that reaches the query point and intersect with the POI set, (b) compute the shortest path between each POI and the query point, and retain those POIs that are close enough. The first approach is beneficial for network areas with many result points; unfortunately, the algorithm must also expand network areas that do not contain any result. The efficiency of the second approach depends on the overall number of POIs and may require a large number of shortest path computations even for small result sizes.
For road networks, a number of solutions have been
proposed, for example, Range Network Expansion (RNE), Range
Euclidean Restriction (RER) [
The problem of reachability queries is closely related to
the computation of shortest path queries. The fastest
algorithms for the shortest path problem heavily rely on
precomputation. If the shortest path between all pairs of nodes is
precomputed, the shortest path computation is reduced to a
single lookup; this approach, however, is not feasible for large
networks. Algorithms like Contraction Hierarchy (CH) [
As stated by Bast et al. [
The goal of this work is to find an efficient solution for reachability queries in public transport networks using precomputation. Time and space for the precomputation should scale to continent size networks; the resulting index should support incremental updates in response to local network changes (e.g., new bus lines or changing schedules).
Our solution is based on graph partitioning. We split the transportation network into cells and precompute upper and lower bounds to traverse each cell. The precomputed bounds are used to efficiently expand the reachable region cell by cell (instead of edge by edge). Points of interest that are within a region found by an upper bound expansion are reachable, while points that are outside the lower bound region are not reachable. All points of interest that are within the lower bound but outside the upper bound region are candidates and must be verified.
In spatial networks, reachability queries are closely related
to the shortest path (SP) problem, which has received much
attention from the research community in recent years. Most
of the current SP algorithms are based on Dijkstra’s
algorithm [
By using extensive precomputation, the online time for
SP queries can be substantially reduced. Highway Hierarchy
(HH) [
Another algorithm for SP computation mainly based
on graph partitioning is Precomputed Cluster Distance
(PCD) [
Customized Route Planning (CPR) [
Most of the above algorithms have been evaluated in road
and public transport networks, and the result is discussed
in [
To model a public transportation network as a graph,
two approaches have been widely used: the time-expanded
and the time-dependent approach. In time-expanded
models, each arrival and departure event in each station (e.g.,
bus stop or train stop) is represented by a vertex, and an
edge is used to represent the link between two events. The cost
to traverse each edge is the time difference between the
source and target event. In time-dependent models, each station
is represented by a single vertex and an edge is used between
two stations if there is a connection between them. A cost
function that depends on the departure time at the source
vertex is associated with each edge. The disadvantage of the
first approach is the large size of the resulting graph. But,
since each event is represented by a vertex, most of the SP
algorithms designed for road networks can be applied in the
resulting graph of this approach. See [
Range Euclidean Restriction (RER) and Range Network
Expansion (RNE) [
Bauer et al. [
We model the spatial networks as a directed graph G = (V, E) with vertices V and edges E. Vertices are embedded in the plane, i.e., they have coordinates. A cost function c(e, t) assigns each edge e ∈ E a positive cost: the time to traverse the edge e = (x, y) at time t (starting time at vertex x). The distance dt(u, v) between two nodes u, v ∈ V is the minimum cost required to travel from u to v at time t (dt(u, v) = ∞ if v is not reachable from u). A point p is in G if it is located on an edge or a vertex of G. The cost to traverse a partial edge is a linear fraction of the total cost.
Definition 1 (Reachability Query). Given a spatial network G = (V, E), a cost budget Δt, a set of points of interest P in G, a query point q in G, and the query time t. A reachability query computes all points of interest, R ⊆ P , that are reachable from q at start time t with cost Δt:
R = {p ∈ P | dt(q, p) ≤ Δt} The reverse reachability query computes all points of interest from which q is reachable at arrival time t with cost Δt.
The main objective of this work is to develop an algorithm for reachability queries in public transport networks. Current solutions for reachability queries are either restricted to road networks (i.e., time-independent edge cost) or do not scale to large networks.
In this section we sketch a technique for reachability queries based on network partitions and local precomputations within each partition.
We focus on public transport networks, which pose the main challenge to precomputation techniques. In a public transportation network graph, nodes are stations, e.g., bus stops or train stations. The time-dependent cost function that is associated to each edge represents the connection between two stations and depends on schedules and waiting times.
To simplify the discussion, the following presentation of our algorithm assumes undirected graphs. Later in this section we discuss possible extensions to directed graphs, which are a realistic model for a public transportation network. 4.1
4.1.1
We partition the graph into n cells. A cell C is a connected subgraph that consists of nodes VC ⊆ V and edges EC ⊆ E, where EC is the set of all edges that connect a pair of nodes in VC . The cells are disjoint (i.e., for any pair Ci 6= Cj: VC,i ∩ VC,j = ∅) and cover the nodes of the graph (i.e., n ∪i=1VC,i = V ). Edges that connect nodes from different cells are border edges, the end points of border edges are border nodes. The set of border nodes of cell Ci is denoted with Bi. 4.1.2
We add new nodes and edges to the graph. (1) In each cell Ci we connect all pairs of border nodes (b, b0), b, b0 ∈ Bi. (2) We add a virtual node i to each cell Ci and connect the virtual node to all border nodes. The virtual nodes are not part of the original graph. The cost between a border node b ∈ Bi and the virtual node i is the cost between b and the node in cell Ci that is most distant from b.
We compute time upper bounds and lower bounds between specific pairs of nodes. The upper bound is the shortest path between two nodes at the time of the slowest connection, i.e., the maximum shortest path over all points in time. The lower bound is the shortest path at the time of the fastest connection. We precompute upper and lower bounds for the following edges: • border nodes: edges between all pair of border nodes within each cell; • virtual node: edge between each border node b ∈ Bi of a cell Ci and the virtual node i of the cell; • all border edges.
The index size (i.e., number of precomputed bounds) is n index size = 2|Bi,j | + X |Bi|(Bi + 1), i=1 where Bi,j is the set off all border edges in G, and Bi is the set of border nodes of cell Ci. Note that Bi,j is a (hopefully small) subset of the nodes E in the original graph G. The summation adds up all upper and lower bounds that are computed within each cell. The summands only depend on the number border nodes in each cell, and the sum linearly increases with the number of cells. Thus, we expect the precomputation to scale to very large graphs.
The index can be incrementally updated in response to schedule changes, edge insertion, and edge removal. Only the updated edges and the cells that contain the updated edges are affected. The upper and lower bounds of all other cells and border edges remain unaffected by the update. 4.2
The core idea of our reachability algorithm is to expand cell by cell rather than expanding edge by edge. The expansion with upper bounds (slowest connection) defines a region Ru ⊆ V that can always be reached within the given cost budget, independent of the starting time. All POIs in the upper bound region are part of the result set. The lower bound expansion (fastest connection) defines the region Rl ⊆ V that is reachable under the assumption that each edge is traversed using the fastest connection, independent of the traversal time. All POIs outside the lower bound region Rl can safely be rejected since they are not part of the query result. The POIs between upper and lower bound region, Rl \ Ru (Ru ⊆ Rl), are candidates which we must to verify. Compared to an approach that computes SP for all POIs, in our approach SP computations are limited to candidates. As will be discussed below, in some cases it might not be necessary to compute SP between a candidate and the query point in order to verify the candidate.
Next we discuss the expansion with upper and lower bounds. For the expansion algorithm we only need to consider border nodes, border edges, and the virtual nodes, i.e., all edges for which we have precomputed bounds. The expansion area is increased by units of cells, not nodes or edges. 4.2.1
Assume a query point q that is located in cell Cq = (Vq, Eq) with border nodes Bq ⊆ Vq and virtual node q. The expansion must first deal with cell Cq and then proceeds to neighboring cells until the budget is exhausted.
Initialization. We first expand cell Cq. The result is a (possibly empty) set of border nodes B of neighboring cells, i.e., B 6⊆ Vq; each border node bi ∈ B has a time budget Δti. The expansion proceeds as follows: 1. Expand cell Cq: If all nodes in Cq are reachable from q with the cost budget Δt, then the upper bound region is initialized with the nodes of Cq, Ru = Vq; otherwise Ru = ∅. Cq is reachable from q if Δt ≥ 2 ub(bq, q) for any node bq ∈ Bq, where ub(x, y) is the upper bound between nodes x, y. The intuition is that we reach bq from any node in Cq (i.e., also from q) at cost at most ub(bq, q); from bq we reach any other node in Cq with the same cost upper bound. 2. Expand to neighboring cells. Compute B, the set of all nodes that are reachable from a border node of Cq via a border edge and have a non-negative cost budget. The cost budget of node bi ∈ B that is reachable via border node bq ∈ Bq is Δti = Δt − ub(bq, q) − ub(bq, bi).
Expansion Step. Given a set of border nodes B outside Ru and a time budget Δti for each bi ∈ B, the expansion proceeds as follows. For each node bi ∈ B: 1. Expand current cell: Let Ci be the cell that contains border node bi. If all nodes in Ci are reachable with the remaining cost budget at bi, the cell is added to the upper bound region, i.e., if Δti ≥ ub(bi, i) then Ru = Ru ∪ Vi. Otherwise only add border node bi: Ru = Ru ∪ {bi}. 2. Expand to neighboring cells. Follow the edges between bi and all other border nodes in Bi. The budget at node bj ∈ Bi \ {bi} is Δtj = Δti − ub(bi, bj). For all border nodes bj ∈ Bi: (a) if tj ≥ 0, Ru = Ru ∪ {bj}; (b) for all nodes d reachable from bj via a border edge: compute the cost budget td = tj − ub(bj, d) of node d; if td ≥ 0, B = B ∪ {d}. 3. Remove bi from B.
The expansion step is repeated until the set of border nodes to be expanded is empty, B = ∅. 4.2.2
The expansion with lower bounds is similar to the expansion with upper bounds. The main differences are: 1. The expansion uses lower bounds instead of upper bounds to compute the budgets of the nodes in B. 2. A cell Ci is added to the lower bound region Rl if (a) Ci contains the query node q (and Δt > 0), or (b) Ci contains a node of bi ∈ B with budget Δti > 0.
We need to expand all cells that are reachable via lower bounds with a non-zero budget. Even if we know that some nodes in the cell are unreachable (i.e., the lower bound to the virtual node exceeds the budget), we must make sure that the subset of nodes that is reachable is in the candidate set. 4.3
In the remaining section, we discuss extensions of the basic reachability algorithm. In particular, we discuss the extension to directed graphs, postulate criteria for a good partitioning of the graph into cells, introduce the concept of time-dependent bounds, and point to opportunities for candidate verification. 4.3.1
Public transportation networks will typically be modeled as directed graphs. In a directed graph, the bounds between a pair of nodes may depend on the direction. We extend our precomputation algorithm to compute two upper and lower bounds for each relevant node pair (one for each direction). For example, we distinguish the upper bound from a border node bi to the virtual node i from the upper bound in the reverse direction. Overall, the size of the precomputation will increase by a factor of two. The expansion algorithm must be adapted to the directed bounds, e.g., when expanding cell Cq, the condition will be Δt ≥ ub( q, bq) + ub(bq, q) (instead of Δt ≥ 2 ub(bq, q), cf. Section 4.2.1).
In an undirected graph, all nodes in a cell are pairwise reachable. This may, in general, not hold for directed graphs, i.e., the bounds between a pair of nodes may be infinite. While still correct, the expansion algorithm would be less effective for the affected cells. Since we model public transport networks, this situation is very unlikely. If for some node there is a path only in one direction, we could reach that station but never leave it (or vice versa). 4.3.2
So far we assumed that the partitioning of the graph into cells is given. Our algorithm is correct for any partitioning, but obviously the partitioning strategy will have an impact on the efficiency of the approach.
We identify a set of properties that an effective partitioning should satisfy: • the number of border nodes per cell should be small; • the overall number of border edges should be small; • the difference between the upper and lower bounds of a cell should be small; • all nodes in a cell should be pairwise reachable; • different cells should be of similar size (i.e., homogeneous in terms of upper bound traversal time). For the cell size, there is a balance to strike: Large cells improve the expansion speed since the processing time of a cell is independent of its size. Small cells allow finer grained expansion and lead to smaller candidate sets.
We expect that an algorithm for computing the optimal partitioning will have infeasible runtime. Thus we will target heuristics or approximations of the optimal algorithm. 4.3.3
In Section 4.1, we define the upper (lower) bound as the shortest path between two nodes at the time of the slowest (fastest) connection over all points in time. These bounds may be very loose for public transportation schedules, where the frequency of the connections will typically vary depending on the time of the day. For example, during rush hours the buses travel with the highest frequency, while there are no buses over night. This leads to lower bounds of minutes and an upper bounds of hours. For reachability queries during the day, the upper bound is too loose, leading to a very small upper bound region. Likewise, the lower bound is too small for departures in the evening, leading to large candidate sets.
Our solution are time-dependent bounds. We split the schedule into intervals and compute a different bound for each interval. During the expansion, we check the earliest (t1) and latest (t2) arrival time at a specific border node b. The upper bound is the maximum upper bound in the interval [t1, t2]; the lower bound is the minimum lower bound in the interval [t1, t2]. The interval of the arrival time is computed while expanding with the upper and lower bounds. Let b be a border node with time budget Δtl during the lower bound expansion and time budget Δtu during the upper bound expansion. With the query time t (i.e., the start time at the query node q) the earliest arrival time at node b is t1 = t + Δt − Δtli; the latest arrival time t2 = t + Δt − Δtiu.
We have different options to split the schedule into intervals: We either use intervals of fixed length (e.g., 6 hours) or intervals of variable length. Variable length intervals will lead to tighter bounds since we can choose the intervals such that the bounds best approximate the true schedule. For example, we can create intervals that cover the rush hours, the day schedule, and the night schedule. Individual intervals can be chosen for each pair of nodes. The intervals may even be different between upper and lower bound for a given pair of nodes. The limiting factor is the precomputation size, which increases with each additional interval.
Table 1 shows an example of time-dependent bounds between a border node b and the virtual node . The 24-hours schedule is split into 4 intervals. The table shows the minimum and maximum travel time from b to any node in b’s cell during the different time intervals. For example, between 6:01 and 12:00 the upper and lower bounds are 10min and 5min, respectively, while the bounds are 240min resp. 30min during the night. When we arrive at node b in the time interval [11:17, 13:03], the upper bound is 15min and the lower bound is 5min. 4.3.4
The straightforward approach to verify a candidate node is by computing the shortest path between the query point and the candidate. Since we have precomputed lower bounds, we do not need to resort to Dijkstra’s algorithm, but can use the efficient A∗ algorithm and do a directed search.
In some cases we can reject or accept candidates without computing the shortest path. For example, the border nodes of the upper bound region that are in partially reachable cells can be used. These nodes have a remaining time budget. All candidates that are reachable from the border node within the given time budget (considering the shortest path between the border node and the candidate) are part of the result. Similarly, the border nodes of the lower bound region that do not reach all nodes in their cell can be used to reject candidates in that cell. 5.
We propose a technique to compute reachability queries in public transportation networks by partitioning the graph into cells and use a novel expansion technique based on upper and lower bounds. The expansion algorithm generates a set of reachable points, a set of unreachable points that can be rejected without verification, and a set of candidates that must be verified. To get tighter bounds (closer upper and lower bounds), time-dependent upper and lower bounds are considered. This reflects the frequency patterns in public transportation schedules, which differ depending on the time of the day and the date (e.g., night buses, weekend schedules, holiday schedules). Better bounds lead to smaller candidate sets.
Different from the Dijkstra-like expansion techniques used in related work, we use precomputation and expect to dramatically reduce the number of shortest path computations for reachability queries. This will lead to better online query performance. The precomputation scales linearly with the network size, and local changes (e.g., schedule changes, new transport routes) require only a local update of the precomputed index.
As future work, we plan to develop an effective partitioning algorithm that satisfies the properties outlined in this paper. We will evaluate the proposed technique on real public transportation networks and empirically compare the performance to relevant competitors from related work. Further, we plan to generalize our solution for public transport networks to multimodal networks, which also include road and pedestrian edges. 6.