Optimal Route Search with the Coverage of Users' Preferences

1 Introduction

It is important to consider preferences of a user when a route plan is required for their trip to a city. The user's preferences can be expressed by a set of keywords, e.g., shopping mall, restaurant, museum, and such locations can also be weighted differently. For example, one may enjoy shopping and local restaurants more and it is less painful for them to drop out of a museum visit than a visit to the museum in the trip, in which case shopping mall, restaurant, museum may be weighted, for example, by 0.5, 0.4, and 0.1, respectively. To best satisfy the user's needs, an optimal route shall pass by a sequence of locations in the city map labeled by these keywords. At the same time, this route can be subject to some constrains like travel time, money and so on.

This type of travel route search problem has been substantially studied. As two examples, the weighted constraint shortest path problem (WCSPP) [Dumitrescu and Boland, 2003] and the shortest path problem with time windows (SPPTW) [Desrochers and Soumis, 1988] aim to find a route with the shortest travel distance under a certain threshold (such as the travel time). However, they do not consider user preferences and thus are not able to satisfy specific requirements of the user. Some studies take into account user preferences, such as the TPQ [Li et al., 2005] and the OSR [Sharifzadeh et al., 2008] query. These methods retrieve routes that pass by all the user-specified types of locations with short travel distances. However, a user may not be satisfied with the proposed routes due to some constraints, e.g., they may not have enough holiday time to follow the proposed route. The more recent work [Cao et al., 2012] finds an optimal route that passes by user-specified types of locations and satisfies a certain budget constraint. It assumes that if a location is labeled by a keyword that expresses a user's preference, the location can fully satisfy the user's need; however, this may not always be true.

As identified in previous research, a location can have multiple functionalities and can be labeled by multiple keywords (such as "restaurant" or "mall") by different users. Fig. 1 shows a road network where each location is labeled by some keywords, each of which is associated with the degree to which the location satisfies the user's need expressed by this keyword (such as mall). The associated [0, 1] weighting reflects the popularity of the location as a given keyword, and the degree to which it satisfies user preferences.

In this paper, we allow a user to weight their various preferences, and we assume that each location is only able to satisfy their preferences to a certain degree. Our objective is to find a route passing by several locations that can optimally satisfy the user's weighted preferences. However, how to measure the degree to which a route covers the keywords indicating the user's preferences is non-trivial. Simply accumulating the keyword degree associated with the locations in a route cannot well reflect the satisfiability of the route. In Fig 1, when a user has a budget score of 8 and weights mall, movie, coffee by 0.5, 0.4, and 0.1 respectively, the route 〈vs, v1, v3, v5, vt〉 is found through an accumulative function of the keyword degrees since it has a budget score 8 and a maximum accumulated weighted degree score (0.5∗(0.6+0.6+0.8)+0.4∗0+0.1∗0.1 = 1.01). However, the route is rather monotonic and concentrates mainly on mall.

In our work, we resort to the coverage function [El-Arini et al., 2009] that calculates the joint satisfiability of one route over a set of keywords. We reformulate this problem as the optimal route search for keyword coverage (ORS-KC), which considers both user preferences and a constraint during the route search, and aims to find a solution that maximizes the keyword coverage function with some budget constraint. Given the example in Figure 1, we would return the route 〈vs, v2, v4, v6, vt〉, which can well satisfy all the user's requirements.

As the coverage function we use is submodular, solving the optimization problem with the constraint is extremely hard particularly for a graph. We prove the ORS-KC problem to be NP-hard by a reduction from the budgeted maximum coverage problem [Khuller et al., 1999]. To avoid the exhaustive search of all routes in a graph, we adapt the A* algorithm [Pearl, 1984] for solving the submodular function maximization problem in a graph. By exploiting the submodular property, we design one admissible heuristic function in the search so that the solution optimality is preserved.

In summary, the contribution of this paper is twofold: firstly, we formulate the problem of the optimal route search for keyword coverage (ORS-KC), and prove that this problem is NP-hard; secondly, we propose the A* based search algorithms for solving this problem, and present experiments conducted on two real-world datasets, which demonstrate the efficiency and accuracy of the proposed algorithms.

2 RelatedWork

Route search and planning is an important problem and has been studied substantially due to its wide range of applications. One of the most classic and well known problem is the shortest path problem, which does not take into account the user preferences and the budget constraint.

Searching for the shortest path under a budget constraint, such as WCSPP [Dumitrescu and Boland, 2003] and SPPTW [Desrochers and Soumis, 1988], is proved to be NPhard and approximation algorithms are proposed. Similarly, route recommendation (e.g., [Chekuri and Pal, 2005]) finds general popular routes without satisfying users' specific requirements.

Recently, consideration of the user preferences appears in the route search or planning. For example, Li et al. [Li et al., 2005] propose the TPQ query, which finds the shortest path between a source and a target location passing by all user-specified types of locations. The work [Sharifzadeh et al., 2008] proposes the OSR query, which finds a shortest route from a specified starting point passing by a sequence of user-specified types of locations. Similar proposals also exist [Chen et al., 2008; Levin et al., 2010; Li et al., 2013]. However, these studies do not take into account a budget constraint.

The work takes into account both the user preferences and the budget constraint in route search [Cao et al., 2012]. However, it treats each keyword equally and assumes that a location can fully satisfy the user's preferences expressed by the keywords labeled with it. In addition, they formulate the objective function as one accumulative function while we use a submodular function, which makes the problem more challenging.

The submodular coverage function we adopt in our work has been used widely in many problems, such as document recommendation [El-Arini et al., 2009], placement of sensor networks [Krause et al., 2011], point-of-interest recommendation [Chen et al., 2015] and so on.

The problem of route search in a graph optimizing a submodular function with a budget constraint has been studied in the work [Chekuri and Pal, 2005], where an recursive greedy algorithm with a performance guarantee is proposed. The algorithm is useful theoretically, but is not applicable to realworld problems such as city route planning. As shown in the study [Singh et al., 2007], its runtime is acceptable only on a graph containing up to 22 nodes, which is not applicable in a road network with at least thousands of locations.

3 ProblemFormulation

In this section, we present the keyword coverage function and formally define the problem of optimal route search for keyword coverage (ORS-KC). We also prove its complexity.

3.1 Keyword Coverage of a Route

We define a road network as a graph.

Definition 1. Road Network Graph. A directed graph G = (V, E) consists of a set of nodes V and a set of edges E ⊆ V × V. Each node v ∈ V represents a location and is associated with a set of keywords denoted by Kvi = {κi1 , · · · , κiq }, each edge 〈vi, vj〉 ∈ E represents a directed route between two locations vi and vj in V and is associated with a cost b(vi, vj) (representing travel time, distance etc).

We only consider directed graphs in this paper; but we note that it is straightforward to extend it to undirected graphs.

Definition 2. Route. Given a road network graph G = (V, E), a route R = 〈v1, · · · , vm〉 is a path from v1 to vm in G, i.e., ∀1≤i≤m · vi ∈ V and ∀1≤i<m · 〈vi, vi+1〉 ∈ E.

We consider two attributes for a route, namely the budget value and the keyword coverage value. The budget value of a route is a sum-up of the costs of the edges along the route, as shown in Eq. 1 below,

Given a budget constraint, our goal is to find a route that can best satisfy the user's weighted preferences, where the satisfiability of a route is measured by a keyword coverage function [El-Arini et al., 2009]. A route is a traversal of locations each of which is associated with multiple keywords, and the keyword coverage function reflects the degree to which a set of query keywords are covered by the route.

Let K = {κ1, · · · , κq} be a set of query keywords and λκq (>0) be the weight of keyword κq. The coverage function we use to compute the keyword coverage for a route R = 〈v1, · · · , vm〉 is shown in Eq. 2,

where covκq (R) measures the degree to which the keyword κq is covered by at least one location in R as computed below:

where covκq (vi) is the degree to which the location vi covers the keyword κq.

For example, given the aforementioned case in Fig. 1, the keyword coverage of the route can be calculated as: KC(〈vs, v2, v4, v6, vt〉) = 0.5∗[1-(1-0.7)]+0.4∗[1-(10.5)∗(1-0.2)]+0.1∗ [1-(1-0.1)∗(1-0.1)∗(1-0.5)] = 0.6495.

Note that the keyword coverage function KC(R) is submodular so that the property is satisfied, e.g., KC(R1 ⋃ vi)- KC(R1) ≥ KC(R2 ⋃ vi) -KC(R2), for all R1 ⊆ R2 ⊆ R and vi ̸∈ R1, where R is a finite set of routes and R1(R2) ⋃ vi composes a new route.

In this paper, we use the popularity of the location vi labeled by the keyword κq to measure covκq (vi), which is implied by the number of check-ins that the location receives at vi labeled by κq. To equally prioritize locations with a high volume of check-ins, we make covκq (vi) proportional to the average users' check-ins at vi labeled by κq, and is computed in Eq. 4,

where ncvκq i is the number of check-ins that are made at vi and labeled by keyword κq, ∑vi 1 is the number of locations visited, and ∑vi ncvκq i counts all check-ins labeled by κq. covκq (vi) is 1 if ncvvq i exceeds the average number of checkins labeled by κq.

3.2 Keyword Coverage Optimal Route Search

Intuitively, the optimal route search for keyword coverage (ORS-KC) problem consists in finding an optimal route from a source node to a target in a graph, such that the keyword coverage is optimized and the budget score satisfies a given constraint. Formally, we define the ORS-KC problem as follows: given G = (V, E), and a query Q = 〈vs, vt,K,Υ,∆〉, where vs is the source location, vt is the target location, K is a set of keywords, Υ contains the keyword weights λκq , and ∆ specifies a budget constraint, we aim to find the route R starting from vs and ending at vt such that

Proposition 1. Solving the optimal route search for keyword coverage (in Eq. 5) is an NP-hard problem.

Proof. We develop the proof by reducing the problem from a unit cost version of the budgeted maximum coverage (UBMC) problem [Khuller et al., 1999]. Given a collection of sets S = {S1, S2, · · · , Sm} with a unit cost C, a domain of elements X = {x1, x2, · · · , xn} with associated weights {w1,w2, · · · ,wn}, and a budget ∆, the aim of UBMC is to find a collection of sets S′ ⊆ S whose total budget is smaller than L and the elements covered by S′ have the largest total weight.

Given an instance of the UBMC problem ϕ, we can construct an ORS-KC problem instance ω as follows: we build a graph containing m + 2 nodes, where two nodes are the source node and the target node and the other nodes correspond to the sets in S, and each pair of nodes is connected by an edge with a unit cost C. For each element xj, we create a query keyword κj, and the weight of κj is set to the weight wj of xj. On a node vi corresponding to a set Si, for each element xj ∈ Si we associate κj with vi, and the value covκj (vi) is set to 1. The budget value ∆ is set to (L+C). Given this mapping, if S′ is the optimal result of ϕ, any route passing by the nodes corresponding to the sets in S′ is the optimal route of ω, and vice versa. As the UBMC problem has been proved to be NP-hard, the ORS-KC problem is NP-hard as well. ■

In analogy to the submodular orienteering problem [Chekuri and Pal, 2005], the ORS-KC problem is hard to solve in an optimal way. One potential approximation with theoretical quality bound is 1 ⌈1+log(k)⌋ , where k is the number of nodes in the optimal route. As demonstrated in the work [Singh et al., 2007], the approximate technique costs more than 104 seconds in a small graph with 22 nodes and a budget of 450 meters, so it is not scalable and cannot be used to solve the problem in real road graphs which typically have thousands of nodes and much larger budgets. The problem is difficult because the route must satisfy the budget constraint and must have an optimized keyword coverage score, which is computed by a submodular function.

4 A* Search Algorithm

We propose an adaptation of the A* algorithm for solving the ORS-KC problem. We first introduce the pre-processing method and then present the algorithm. Meanwhile we develop a pruning techniques to improve the search efficiency.

4.1 Pre-processing

We introduce the pre-processing method that is commonly used to accelerate the search algorithm in a road network. We use the Floyd-Warshall algorithm [Floyd, 1962], which is a well-known algorithm for finding all pairs of the shortest paths, to compute the smallest budget for each pair of locations. After this pre-processing, we get all the smallest budgets of pairs. For every pair of nodes (vi, vj), we denote the least budget from vi to vj as BSsm(vi, vj).

4.2 Algorithm

A brute-force approach for solving ORS-KC is to conduct an exhaustive search. It first enumerates all candidate paths from a source node and uses a queue to store the partial paths. Subsequently, in each step, it extends one partial path in the queue and generates a new set of candidate partial paths. The paths that have budget scores smaller than ∆ are added to the queue. Finally it returns the best route after comparing all the candidate routes from the source location to the target location. Thus the brute-force technique guarantees an optimal solution to the ORS-KC problem.

However, the exhaustive search is computationally prohibitive. To avoid enumerating all partial paths, we propose a novel variant of the A* algorithm. The basic idea of applying the A* algorithm is to search the candidate partial paths with best estimated keyword coverage firstly, and prune the partial paths with small estimated keyword coverage. It is non-trivial to estimate the keyword coverage of partial paths because the objective function is submodular and the budget also needs to be considered.

The Framework of A* Algorithm

As all the partial paths start from a source node, we can build a search tree and conduct a breadth-first search. As well known, the A* algorithm uses a knowledge-plus-heuristic cost function to determine the order in which the search visits nodes in the tree. When we reach a node vn in the search tree, we define the knowledge-plus-heuristic cost function at node vn by:

where gn (Rs→n) is the exact keyword coverage of the path Rs→n and can be computed using KC(Rs→n) in Eq. 2, and hn (Rn→t|Rs→n) estimates the marginal keyword coverage of the successive route conditioned on Rs→n in the search tree. Note that hn (·) does not depend on the gn (·) in the conventional A* algorithm, and thus designing f n (Rs→t) in our problem is more challenging.

From the source node vs to the node vi, there exist many paths. To store each path and its information on the node vi, we define the route label in format of Lki = 〈Rk i ,BS(Rk i ),KC(Rk i ), f i (Rs→t)〉, where Rk i represent the kth path from vs to vi. We use a max-priority queue Q to organize these labels, which are enqueued into Q in decreasing order of f i (Rs→t).

In Alg. 1, the algorithm starts by creating an empty R that is used to store the current best route (line 1). The current best keyword coverage score is stored in KCmax and the route label containing vs is enqueued into Q (lines 3-4). It dequeues the candidate route label from Q one by one until either Q is empty or all the route labels in Q have an estimated keyword coverage smaller than KCmax (lines 5-7). In each while-loop, the algorithm first obtains a partial route from the dequeued route label that is to be extended (line 8). For each outgoing neighbor vj of vi, it creates a new route (line 10) and ignores the new route whose budget score is larger than the budget ∆ (line 11). The algorithm updates R and KCmax when the keyword coverage of a new route is larger than the current KCmax; otherwise, a candidate partial route is found and its keyword coverage is estimated. For the candidate route, the algorithm then creates a new route label and enqueues it into Q when the estimated keyword coverage is larger than the current KCmax (lines 12-21). Finally, if KCmax is never updated, there exists no feasible route for the given query; otherwise, the optimal route R is returned (lines 22-23).

Algorithm 1: A* Algorithm for ORS-KC

Input: G = (V, E), Q = 〈vs, vt, K, Υ, ∆〉, BSsm(vi, vj) of all pairs of locations in G Output: An optimal route R 1 Initialize a max-priority queue Q← ∅; 2 R← ∅; KCmax ←-∞; 3 Create a route label: L0s ← 〈(vs), 0, 0, 0〉; 4 Q.enqueue(L0s); 5 while Q is not empty do 6 Lki ←Q.dequeue(); 7 If Lki .f n (Rs→t) ⩽ KCmax break; 8 Obtain Rk i fromLki ; 9 for each edge (vi, vj) do 10 Create a route Rlj ← Rk i ∪ vj; 11 If BS(Rlj ) > ∆ continue; 12 if vj is vt then 13 if KC(Rlj) > KCmax then 14 R ← Rlj ; 15 KCmax ← KC(Rlj ); 16 else 17 Compute f j (Rs→t) ; 18 if f j (Rs→t) >KCmax then 19 Create a route label Llj ← 20 〈Rlj , BS(Rlj ), KC(Rlj ), f j (Rs→t)〉; 21 Q.enqueue(Llj ); 22 If KCmax is -∞return "No feasible route exists"; 23 Else return R;

The key challenge of this algorithm is at line 17, i.e., how to compute the function in Eq. 6. Because the keyword coverage function is a submodular function, it implies that the future path-keyword coverage hn (·) depends on the past pathkeyword coverage gn (·), which is different from the conventional A* algorithm. We next proceed to present how to compute the function f n (·).

The Heuristic Function hn (·)

The most crucial part of designing an A* algorithm is to compute the admissible heuristic function for a node vn, i.e., in our problem it is hn (·). In conventional A* algorithms, it is the estimation of the cost value of the route from vn to the target node vt. However, because our keyword coverage function KC(·) is submodular, as shown in Eq. 6, the heuristic function hn (·) is the marginal keyword coverage of the successive route conditioned on Rs→n, instead of the keyword coverage of the route Rn→t. Therefore, rather than estimating KC(Rn→t), we are going to estimate KC(Rs→t) - KC(Rs→n).

Note that KC(Rn→t) = ∑κq∈K λκq (1 - ∏vi∈Rn→t [1 - covκq (vi)]), and thus we can conclude:

KC(Rn→t).

Hence, we can define hn (Rn→t|Rs→n) = (maxκq∈K ∏vi∈Rs→n [1 - covκq (vi)]) · KC(Rn→t), and this estimation offers the expected admissibility of the heuristic function, as it is an upper bound of KC(Rs→t) - KC(Rs→n). This guarantees the optimality of the solution.

Specifically, when reaching a node vn, we first get (maxκq∈K ∏vi∈Rs→n [1 - covκq (vi)]), which is already known, and then we compute KC(Rn→t). Computing KC(Rn→t) becomes a new ORS-KC problem with the reduced budget ∆′ = ∆-BSsm(vs, vn). Fortunately, it is not necessary to compute the exact KC(Rn→t), and instead we can estimate an upper bound (UB) for KC(Rn→t). Then, we compute hn (Rn→t|Rs→n) as (maxκq∈K ∏vi∈Rs→n [1 - covκq (vi)]) · UB, which still guarantees admissibility. We proceed to explain how to estimate the upper bound of KC(Rn→t).

We first get the locations set Ln including all nodes which can be visited from vn to vt with the budget ∆′ , denoted by Ln = {vi|BSsm(vn, vi) + BSsm(vi, vt) ≤ ∆′}. We compute the node's cost as a lower bound of the budget passing by this node, i.e., Cost(vi) = min{b(vk,vi)}+min{b(vi,vj)} 2 , where 〈vk, vi〉 is one in-edge of vi and 〈vi, vj〉 is one outedge of vi. We set Cost(vt) = 0.0 at the target node. Then, we utilize the greedy algorithm for the budgeted maximum coverage (BMC) problem [Khuller et al., 1999], to approximately find a set of nodes such that their total cost does not exceed the budget ∆′ , and their keyword coverage is maximized. Note that using this algorithm, the nodes found are not necessarily connected as a route, but this does not affect the fact that the result found provides an upper bound. This algorithm achieves an approximation factor of 1-1/√e. Thus, we can get KC(Lop ) ⩽ KC(Lmg ) 1-1/√e , where Lmg is the nodes set found by the greedy algorithm and Lop is the optimal nodes set. Proposition 2 provides an upper bound of KC(Rn→t).

Proof. We first prove that the optimal route Rop achieved by computing KC(Rn→t) is a feasible solution of the transformed BMC problem. For the optimal route Rop , the budget score BS(Rop ) is not larger than ∆′ , e.g., ∆′ ≥ BS(Rop ). As BS(Rop ) = ∑(vi,vj)∈Rop b(vi, vj) is larger than ∑vi∈Rop Cost(vi), we have ∑vi∈Rop Cost(vi) ≤ BS(Rop ) ≤ ∆′ , and thus Rop is a feasible solution. Since Lop is the optimal solution, we know that KC(Rop ) ≤ KC(Lop ) ⩽ KC(Lmg ) 1-1/√e . ■

In summary, we set hn (Rn→t|Rs→n) = (maxκq∈K ∏vi∈Rs→n [1 - covκq (vi)]) KC(Lmg ) 1-1/√e , which preserves the admissibility of the heuristic function. We finally compute the function f n (Rs→t) in Eq. 7,

Pruning Optimization

In Alg.1, we only prune the candidate partial routes with small keyword coverage (lines 18-21). We further improve the efficiency of the A* algorithm by pruning the candidate partial routes with large budget scores. Before creating a new route label for Rlj and enqueuing it into Q, we check whether the estimated budget score BS(Rlj ) +BSsm(vj , vt) is larger than the budget ∆. If BS(Rlj ) + BSsm(vj, vt) > ∆, we prune Rlj . Proposition 3 states that the pruning technique preserves all feasible solutions.

Proposition 3. No feasible route contains Rlj given BS(Rlj ) + BSsm(vj , vt) > ∆.

Proof. Assume that when BS(Rlj ) + BSsm(vj, vt) > ∆, there exists a feasible route Rls→j→t including Rlj , where Rls→j→t = Rlj + Rlj→t and BS(Rls→j→t ) ≤ ∆, so BS(Rls→j→t ) = BS(Rlj )+BS(Rlj→t ) ≤ ∆. Consequently, we get BS(Rlj→t ) < BSsm(vj, vt), which contradicts the assumption. ■

5 Experimental Study

We conducted a series of experiments to study the ORS-KC problem and demonstrate the algorithm performance.

5.1 Experimental Settings

Datasets. We use two real-world datasets. One has been collected from F oursquare which was made in Singapore (SG) between Aug. 2010 and Jul. 2011 [Yuan et al., 2013], and another one is from Gowalla which was made in Austin (AS) between Nov. 2009 and Oct. 2010 [Cho et al., 2011]. We have adopted the Foursquare APIs to fill in the missing values of keywords (categories of locations). The SG dataset has 189,306 check-ins made by 2,321 users at 5,412 locations, and the AS dataset contains 201,525 check-ins made by 4,630 users at 6,176 locations. Following the work [Cao et al., 2012], we build an edge between two locations which were visited continuously in 1 day by the same user, and set the budget value by the Euclidean distance for each edge.

Comparative Methods. We have implemented the A* algorithm with the above described pruning optimization. In addition, we adopt the standard Weighted A* method (WA*) [Ebendt and Drechsler, 2009] to further optimize performance. In WA*, the cost function for WA* is expressed as f n (·) = gn (·) + ωhn (·), which improves performance through a phenomenon known as precision-complexity exchange, speeding up search at the cost of a minimal departure from optimality 1 . For the comparison purpose, we have implemented the Brute-Force (BF) approach. Meanwhile we use the Pruning Optimization (as described in Section 4) to improve BF (denoted by BF+PO).

We generate 100 queries randomly in each experiment, implement methods in JAVA and conduct experiments on a Windows PC with a 4-core Intel i7-870 2.93GHz CPU and 16 GB memory.

5.2 Performance of Methods

Efficiency of Methods. We compare our A* algorithm with BF+OP method on the run time with variation of the budget limit ∆ (travel distance). Note that both methods are able to get the optimal solution, and BF+OP is the improved version of brute-force approach. Fig. 2 shows that the A* algorithm is usually 2-3 times faster than BF+OP method, and the run time of both methods grows with the increase of ∆ quickly, as ∆ is larger, more potential routes should be checked.

Effect of the Weighting Parameter ω. In the WA* algorithm, the weighting parameter ω sets a trade-off between precision and complexity. We denoted the route found by the WA* algorithm as Rsw , if ω = 1, the WA* algorithm gets the optimal route Rop , then we use the ratio KC(Rsw ) KC(Rop ) to measure the precision of the WA* algorithm. Fig. 3 shows the effect of ω with ∆ = 15 kilometers on solving the ORSKC problem. With the increase of ω, the precision improves while the efficiency drops (longer run time). In particular, the change of precision and run time is notable from ω = 0.3 to

1 As discussed in the work [Ebendt and Drechsler, 2009] weighted A* is a bounded suboptimality method. Another way to characterize the precision-complexity exchange is to consider the approach as epsilon-admissible.

ω = 0.4, which indicates that 0.4hn (·) = 0.4 ∗ KC(Lmg ) 1-1/√e is close to the upper bound of the marginal keyword coverage hn (Rn→t|Rs→n). As (1 - 1/√e) approximates 0.4, KC(Lmg ) is near the upper bound of hn (Rn→t|Rs→n) in most cases. We thus set the weighting coefficient to 0.2, which drastically reduces computation time while limiting solution quality deterioration to 5%.

Scalability of the A* algorithm. In order to study the scalability of the algorithms, we run the A* and WA* algorithms on a larger budget limit ∆ in two datasets. As the run time of A* algorithm is larger than 104 ms when ∆ ≥ 17 kilometers, we omit it. Fig. 4 shows that WA* scales better than A*. This is expected as a large budget enlarges A*'s search space.

Example. We use one real-world example in the SG dataset to show that ORS-KC can find optimal routes for satisfying user's various preferences. We set the source location at National Library of Singapore and the target location at Gallery Hotel, the budget constraint ∆ = 6 kilometer, and the keywords set is K = {κ1 = mall, κ2 = coffee, κ3 = park}, i.e., a user would like to enjoy shopping, drink some coffee and visit a park on the route. To keep the example clear, we only list some locations having the three keywords in the map. When we set the keyword weights be Υ = {λκ1 = 0.8, λκ2 = 0.1, λκ3 = 0.1}, our (W)A* algorithm returned the optimal route in Fig.5(a), which contains some popular malls on the prosperous Orchard Road. On the other hand, when Υ = {λκ1 = 0.1, λκ2 = 0.1, λκ3 = 0.8}, the route in Fig. 5(a) is not a good choice, because it only goes though a small park. Instead the (W)A* algorithm selects a new route that contains a popular park in Fig. 5(b).

6 Conclusion

Considering users' various preference on route search, we introduce the keyword coverage function and define the optimal route search for keyword coverage (ORS-KC) problem, which is to find an optimal route such that it can optimally satisfy the user's weighted preferences. In order to solve ORSKC, we define an admissible heuristic exploiting the submodular property, then use a variant of A* to compute solution routes. This is also challenging in a general submodular function optimization for a graph. Empirical results demonstrate performance of our methods as well as the quality of routes found in the ORS-KC problem. In the future work, we will seek other approximate algorithms for solving this new problem.

Acknowledgements

This work was done during Xuefeng Chen's visit to Teesside University, sponsored by Teesside University. Yanping Xiang would like to thank the support of projects (No. 2015TD0002 and No. 2014FZ0087) from the Sichuan province, China.