In this paper we present a novel approach to solve the TimeDependent Nearest Server problem, i.e., the problem of finding a service provider that, given a requesting user, can reach the user's geographical location as early as possible while taking into account trac conditions. We also present a reduction of the above problem to the fastest-path problem to prove the correctness and bound the time complexity of our approach. In the experimental evaluation we compare our approach with respect to the state-of-art, and show its e↵ectiveness in terms of accuracy and performance.
Large amounts of vehicles in big urban agglomerations usually create serious mobility issues, such as congestion. Indeed, trac conditions can change considerably over time, ranging from rush hours to regular hours, thus having relevant impacts on travel times. Consequently, taking into account trac conditions is essential to improve the quality of location-based services, for example by providing better route plans.
In this context, we model a road-network as a time-dependent road-network
– i.e., the costs associated with the edges of the network can vary over time –
and attempt to solve a variation of the problem of computing nearest neighbor
queries over time-dependent networks, i.e., the Time-Dependent Nearest Server
(TDNS) problem[
Figure 1 provides an example of the applicability of TDNS queries: let us suppose there is a user issuing an emergency call and a system has to find out which ambulance, among those available, can reach the user’s location in the shortest amount of time. In this context, we model the network by means of a time-dependent network, where streets get associated with edges. Ambulances moving over the network may require to update frequently their positions. Also, to take into account trac conditions each edge is associated with a timedependent cost function that determines the travel time needed to cross the edge at the time instant an object starts traversing it (e.g., rush hours typically imply higher costs).
In this paper, we propose a new method to solve TDNS queries.
Di↵erently than the algorithm proposed in [
The rest of the paper is structured as follows: Section 2 provides the definitions and the problem statement. Section 3 reviews the related works. Section 4 illustrates the approach we propose to compute TDNS queries. Finally, Section 5 presents the experimental evaluation, while Section 6 draws the final conclusions. 2
A time-dependent graph (TDG) G = (V, E, C) is a directed graph where V = {v1, . . . vn} represents a set of vertices, E = {(vi, vj ) | vi, vj 2 V, i 6= j} represents a set of edges, and C = {c(vi,vj)(·) | (vi, vj ) 2 E}, with c(vi,vj) : [0, T ] ! R+, represents a set of cost functions. Each cost function attributes a positive weight to the associated edge, depending on the time instant t 2 [0, T ] provided to the function (T is a domain-dependent time length).
Since G is directed, bidirectional segments may have associated di↵erent edge
costs, i.e., c(u,v)(t) 6= c(v,u)(t). Furthermore, we assume that C represents a set
of piecewise linear functions that satisfy the FIFO property, i.e., if an object
A starts crossing an edge before an object B, then A has to finish crossing
the edge before B. We remind that the problem of finding the fastest path in
time-dependent networks that satisfy the FIFO property has a polynomial time
solution, while it is NP-hard in non-FIFO networks [
Given a TDG G = (V, E, C), a path P = hvp1 · · · , vpn 1 , vpn i in G and a departure time t 2 [0, T ], we define the travel time (TT) of P to be the time-dependent cost to traverse P ; this cost is defined as the sum T T (P, t) = where t1 = t and ti+1 = (ti + c(vpi ,vpi+1 )(ti)) mod T . The rationale behind the use of modulo is to deal with time cycles (e.g., a day implies T = 24 hours). We also define the time-dependent fastest path (TDFP) from a vertex v to a vertex u at time t to be the path with the minimum travel time; we denote it by T DF P (v, u, t).
A Point of Interest (POI) represents an object within the underlying network that can be characterized by its geographic coordinates (latitude and longitude). In most of the works present in the literature a POI represents just a static entity, such as a hospital, a restaurant, and so on. In our case, however, POIs represent moving objects acting as service providers. For simplicity, from here on we use the term point of interest (POI) to refer to a service provider. At this point we can provide the problem statement.
Definition 1 (Problem statement). Given a time-dependent graph G = (V, E, C), a query point q, a time-instant t, and a set P of moving objects (POIs) in G, the Time-Dependent Nearest Server (TDNS) problem requires to retrieve the object p 2 P such that, 8 p0 2 P , p0 6= p, we have that T T (T DF P (p, q, t), t) T T (T DF P (p0, q, t), t).
The first algorithm that considers a time-dependent variant of the shortest path
problem was proposed in [
Other related works solve the problem of finding the k nearest neighbors in
time-dependent networks, where the goal is to find the first k POIs that can be
reached from the query point in the shortest amount of time (time-dependent
k-NN query). The problem was first introduced in [
Another solution [
Others works propose solutions that deal with variations of the problem
of computing k-NN queries over time-dependent networks. In [
Finally, in [
Finally, we mention that this solution requires each POI to be associated with a node in the original graph, which in turn represents a potential bottleneck during the processing.
The goal of this section is to introduce our proposal, i.e., the competitive network expansion (CNE), and the key ideas that brought to its conception. The Competitive Network Expansion algorithm considers the original graph to compute the cost of the paths from a set of service providers (POIs) to a query point q – as such, our algorithm is guaranteed to always return exact costs. A na¨ıve solution would calculate the fastest paths between all the POIs and q, and pick up the fastest one. Instead, we base our iterative search on the idea of computing the paths from all the POIs in a competitive way, where at each step the POI having the highest chance to be q’s nearest neighbor acquires the most preference. 4.1
Given a set of POIs P , we apply a search algorithm to select the nearest POI among the candidates. Our search step is based on a reduction of the TDNS problem to the fastest path problem. Before delving into the inner workings of the search step, we need to show how the reduction is carried on. The idea behind the reduction is that, by including a virtual node vn in G connected to all the POIs in P , and by adding in E zero-cost edges that connect vn to all the POIs in P , we have that the fastest path between vn and q passes through q’s nearest POI.
Theorem 1. Let G = (V, E, C) be a TDG and P C = {pc1, · · · pc }, P C ✓ P , be a set of POIs; let us obtain from G a transformed graph G0 = (V 0, E0, C0) by including a virtual node, vn, and a set of virtual edges, that is, V 0 = V [ { vn}, E0 = E [ { (vn, pc1), · · · , (vn, pc )}, and C0 = C [ { c(vn,pc1) = 0, · · · , c(vn,pc ) = 0}. If the time-dependent fastest path from vn to q pass through pc 2 P C, and pc is the first POI in P C that appears in the path, then pc is the TDNS of q. Proof. Let pc be the first POI in the time-dependent fastest path from vn to q. If pc is the first POI, then pc is the second vertex in this path, because vn has edges only with POIs in P C. Furthermore, the cost of the fastest path from vn to q at time t is TDFP(vn, q, t) = c(vn,pc)(t) + TDFP(pc, q, t) = TDFP(pc, q, t), since c(vn,pc)(t) = 0. Let us suppose that pc is not the TDNS of q: then, there must be another POI pc0 2 P C that is the TDNS of q, since TDFP(pc0, q, t) < TDFP(pc, q, t) = TDFP(vn, q, t); however this is impossible, since this would imply that there exists a faster path than the fastest one.tu
At this point we can describe the search step of CNE. Our approach uses a
variant of the A⇤ algorithm [
Vmax and Vmax is the maximum velocity allowed on the network. The pseudo-code of CNE is provided in Algorithm 1.
First, with respect to the original A⇤ algorithm we change the way the queue is initialized (InitQueue, line 2); more precisely, in G0 we have that the costs associated with the edges between vn and the POIs in P C are zero. As such, we can ignore the additional edges added in G0 and start the search directly from the POI candidates, since the reduction happens in linear time on size of P C (by virtue of Theorem 1). Consequently, between lines 2 and 8 of InitQueue (Algorithm 2) each candidate p gets included in a priority queue, visited, which is sorted according to Lp, i.e., the distance from the virtual node, vn, to p, plus h(p). Subsequently, CNE goes on until visited gets empty (line 3) or the query point is reached (lines 6-7). As in the case of original A⇤ -search, at each iteration one node is dequeued and marked accordingly (lines 4-5), while the neighbors that were not marked as VISITED get enqueued (line 14). If a neighbor was already visited, and its new travel time is better than the current one, then its state get updated (lines 17-18). 4.2
According to Theorem 1, CNE is an exact algorithm. However, expanding all the POIs in the network is unnecessary, since this would make the solution na¨ıve. As such, we suggest to perform a candidate generation phase before executing Algorithm 1; the goal of this phase is to produce a set of candidate POIs according to the (Euclidean) distance between the POIs and the query point.
During the candidate generation phase, we compute k-NN queries between the query point and the POIs – to this end we observe that, the lower the number of candidates, the smaller the chance that the correct result will be returned by CNE; Section 5 studies the impact that this factor has on the quality of results. We also maintain an R-Tree that is used to index the vertices of the graph. Since search algorithms typically suppose that POIs are associated with the vertices of the graph, the goal of this data structure is to facilitate the related map-matching.
Overall, the candidate generation step helps to decrease the execution time of CNE and the time to map-match POIs. 5
The goal of this section is two-fold: first, we assess the accuracy of CNE and to
do so we use the output returned by the Naive algorithm as our ground truth
– we remind that the Naive approach computes the fastest paths between the
POIs and the query point and picks up the fastest among these. Subsequently,
we compare CNE with Breadth-First Search (BFS) in reverse graphs [
For the purposes of this work, all the approaches were implemented on top
of the Graphast framework [
Comparison of Accuracy SCENARIO A SCENARIO B SCENARIO C 99 98 98 99 98 99 100 98 99 99 99 100 100 100 100 100.00
Accuracy of CNE X Number of Candidates 100.00 100.00
We use the road network related to the city of Fortaleza, obtained by collecting the data available from the Open Street Map Project2. The graph representing the network contains around 100.000 nodes, while travel time functions are synthetically generated. In the experiments, we consider three distinct scenarios involving real-world POIs, where we vary their density and distribution; more specifically, we consider taxis positions (A) at 7am with 360 POIs, (B) at 12am with 216 POIs, and (C) at 5pm, with 398 POIS. The set of POI locations was provided by Taxi Simples, a company that tracks and monitors cabs activities3; POI positions span one day (July 23, 2016). 5.2
In the first batch of experiments we want to evaluate the impact that the number of candidates has on CNE’s accuracy; in general we expect that, the less the candidates provided, the less the resulting accuracy. To this end we compare the results returned by CNE with the ones returned by the Naive approach. Figure 3 presents the accuracy achieved by CNE when using 10, 20, 30, 40, and 50 candidates.
From the Figure 3, we see that the minimum accuracy achieved by CNE is 97.65% (scenario B, 10 candidates). With 50 candidates, all POIs returned were the correct nearest service provider. We also report that once the number of candidates gets above 50, CNE was always able to achieve total correctness (100%).
In the second batch of experiments we evaluate the execution time of CNE, Naive and BFS. We consider, again, the three scenarios introduced before, and measure the CPU time needed to update the POI locations and run the search. 2 http://wiki.openstreetmap.org/wiki/Main_Page 3 http://www.taxisimples.com.br/ 22,000 16,500 ) s m ( e im11,000 T U P C 5,500 0 In this context, we also enforce CNE to produce 50 candidates. Each test is repeated 100 times. Figure 4 presents the results. From this figure, we see that CNE always outperforms the competitors; the average CPU times achieved by Naive when considering the scenarios A, B, and C were, respectively, 10.504 ms, 20.429 ms and 20.477 ms, almost two orders of magnitude greater than the times achieved by CNE.
If we compare CNE with BFS, we see that the speedups yielded by our approach are equal, respectively for the scenarios A, B, and C, to 2.4⇥ , 3.9⇥ and 4.2⇥ . Finally, we observe that the execution time of CNE remains always below 800 ms and that it exhibits an almost constant trend: as such, we argue that the number of POIs in the network has a minimal impact on CNE’s performance.
In the third, final batch of experiments we evaluate how the performance of CNE is a↵ected when the POI density (i.e., the rate of POIs per node) increases. We generate 10 sets of synthetic POIs in the network, in the [0, 1%; 1%] density range, and compare the CPU time of CNE and BFS. We also enforce CNE to produce 50 candidates at the end of the candidate generation phase. Figure 5 shows the average time and standard deviation obtained with 100 executions.
From the Figure 5, we see that the CPU time of CNE remains constant – thus indicating that the candidate generation phase makes CNE scalable with respect to the POI density – while the CPU time of BFS increases linearly. 6
In this paper we propose a new approach to solve nearest service provider queries
in time-dependent road networks (TDNS). Among the contributions, we provide
a reduction of the TDNS problem to the fastest path problem, and prove its
correctness. Thanks to this, it is possible to solve our query by applying minor
modifications to the A⇤ -search algorithm [
Another contribution consists in showing that the application of a candidate generation phase allows to quickly update POI locations with negligible e↵ects on the correctness of the final results. Indeed, in the experimental evaluation we show that our solution achieves at least 97% of accuracy with real-world datasets, even when using a very low amount of candidates.
Finally, in the experimental evaluation we show that our approach performs
better than the state-of-the-art currently available in the literature [
As a future direction of research, we plan to improve the way candidate POIs are chosen; we also plan to solve the problem of computing a continuous version of the TDNS query, where we continuously monitor the service providers to identify the best one in real-time. Finally, we plan to investigate how we can compute TDNS queries over dynamic networks, where travel-time functions can be updated over time.