Roadscape-based Route Recommender System using Coarse-to-fine Route Search Koji Kawamata Kenta Oku Ryukoku University Ryukoku University Otsu, Shiga, Japan Otsu, Shiga, Japan t18m057@mail.ryukoku.ac.jp okukenta@rins.ryukoku.ac.jp ABSTRACT method for estimating roadscapes of given road links. In particu- We propose the Roadscape-based Route Recommender System (R3), lar, we defined rural, mountainous, waterside, and urban elements which provides diversified roadscape-based routes. Given start- as the roadscape elements, which are basic elements that compose ing and destination points, R3 provides four types of roadscape- a roadscape, through preliminary experiments. We defined a road- based routes: rural-, mountainous-, waterside-, and urban-prior scape vector each of whose elements corresponds to a roadscape routes. To reduce the computational cost, we propose a coarse-to- element and proposed a method for estimating such roadscape vec- fine route search approach that consists of a roadscape-based clus- tors for given road links. We presuppose that R3 is to be used on tering method, a roadscape cluster graph, a coarse-grained route road network data with roadscape vectors. search, and a fine-grained route search. We evaluated the perfor- Traditional route searching algorithms, such as the Dijkstra al- mance of R3 using network data for a real road. The experimental gorithm [2], are given the costs of road links and find a route that results show that using coarse-grained route search can signifi- minimizes the sum of their costs. The simplest approach is to ap- cantly reduce route search time. ply the traditional method and reduce the costs of the road links having the targeted roadscape elements. However, there is a high CCS CONCEPTS computational cost in applying such a method to a very large road network. • Information systems → Social recommendation; To reduce the computational cost, we propose a coarse-to-fine KEYWORDS route search approach. We focus on the concept that similar road- scapes do not exist as fragments but in clusters. For example, there route recommender system, route search, roadscape are some areas composed of similar roadscape elements, such as rural areas, mountainous areas, waterside areas, and urban areas. 1 INTRODUCTION Based on this characteristic, we expect that we can reduce the com- Cars are driven not only for transportation but also for the plea- putational cost by clustering similar roadscape areas in advance. sure of it. Some people want to drive along the seaside or on rural In this approach, we firstly extract areas—roadscape clusters— roads while enjoying their favorite landscape. We call such road- composed of similar roadscape elements by using a roadscape- side landscapes “roadscapes.” In such situations, it is not always based clustering method. Secondly, we create a roadscape clus- the best solution to provide the shortest or the fastest route. An ter graph whose nodes correspond to the roadscape clusters and alternative solution is to provide routes with favored roadscapes whose links correspond to the links between roadscape clusters. even if they involve a detour. In the route searching process, given the roadscape cluster graph Given starting and destination points, a route recommender sys- and starting and destination points, we roughly find four types tem provides routes from the starting point to the destination point. of roadscape-based routes, which are the roadscape cluster sets The majority of traditional route recommender systems provide passed through, one for each roadscape element; we call this the the shortest routes [3, 7], the fastest routes [4, 5, 9, 11, 12], or pop- coarse-grained route search. Then, we find specific routes that con- ular routes [1, 6, 8, 10]. As mentioned above, the shortest and the nect the roadscape clusters in each type of route; we call this the fastest routes do not always satisfy the user’s demands. Systems fine-grained route search. that recommend popular routes provide routes many people are The contributions of this paper are as follows: interested in. Wei et al. [8] extract popular routes by mining road links many people are interested in from their trajectories. Such • We propose the Roadscape-based Route Recommender Sys- route recommender systems consider the attractiveness of routes tem (R3), which provides diversified roadscape-based routes, based on the wisdom of crowds, without considering the content namely, rural-, mountainous-, waterside-, and urban-prior features of routes. routes. In this paper, we focus on the roadscape as a route feature and • To reduce the computational cost, we propose a coarse-to- propose the Roadscape-based Route Recommender System (R3), fine route search approach that consists of a roadscape-based which provides diversified routes on the basis of roadscapes. Given clustering method, a roadscape cluster graph, a coarse-grained starting and destination points, R3 provides four types of roadscape- route search, and a fine-grained route search. based routes: rural-, mountainous-, waterside-, and urban-prior • We evaluate the performance of R3 using network data for a routes. For example, a user who likes waterside views can select real road. The results show that using coarse-grained route waterside-prior routes from the four types of routes provided. To search can significantly reduce route search time. develop such a route recommender system, we have proposed a RecTour 2018, October 7th, 2018, Vancouver, Canada. 23 Copyright held by the author(s). 2 PRELIMINARIES Definition 1: Road network. A road network is a directed weighted graph G = (V , E), where V is a set of road nodes and E ⊆ V × V is a set of road links. A road node vi ∈ V represents an intersection or an endpoint of a road. A road link ek = (vi , v j ) ∈ E is a directed link from the starting node vi to the ending node v j . A road link ek is assigned a cost w k according to the length of the link. Definition 2: Roadscape element. Roadscape elements are basic elements that compose a roadscape. We define four roadscape elements: rural, mountainous, waterside, and ur- ban elements. These elements were selected by preliminary experimentation.1 Definition 3: Roadscape vector. A roadscape vector is de- fined as a four-dimensional probability vector each of whose elements corresponds to one of the respective roadscape elements. We define a roadscape vector of a road link ei Figure 1: Recommended roadscape-based routes. as s(ei ) = (sir , sim , siw , siu ). Each element of the vector de- notes the probability of how strongly ei includes the cor- responding roadscape element. Therefore, the sum of the value of cos(s(ei ), s(ek )) is calculated as follows: values over all elements is 1. Definition 4: Roadscape cluster. A roadscape cluster C j ∈ s(ei ) · s(ek ) cos(s(ei ), s(ek )) = . (3) C is represented by a set of road links having similar road- |s(ei )||s(ek )| scape vectors. A roadscape vector s(C j ) of roadscape cluster C j is represented by the mean vector of the roadscape vec- 3 ROADSCAPE-BASED ROUTE tors of the road links included in cluster C j . Therefore, we RECOMMENDER SYSTEM define s(C j ) as follows: 3.1 System Overview 1 ∑ s(C j ) = s(ei ). (1) Our proposed Roadscape-based Route Recommender System (R3) |C j | provides four types of roadscape-based routes: rural-, mountainous- i ∈C j , waterside-, and urban-prior routes. Figure 1 shows a result pro- Here, |C j | denotes the number of road links included in the vided by R3. When a user inputs starting and destination points on roadscape cluster C j . the map, the four types of roadscape-based routes are provided in Definition 5: Roadscape cluster graph. A roadscape cluster different colors. graph is a directed weighted graph G = (V, E), where V It is assumed that R3 will be used with a road network with is a set of roadscape clusters Ci and E ⊆ V × V is a set of roadscape vectors. The steps of R3 are as follows: links between roadscape clusters. A link lk = (Ci , C j ) ∈ E is a directed link from the starting node Ci to the ending (1) Generate roadscape cluster graph based on road network node C j . The road link lk is assigned a cost vector ωk = with roadscape vectors. (ωkr , ωkm , ωkw , ωku ) based on the roadscape vector C j of end- (2) Roughly find four types of roadscape-based routes in the ing roadscape cluster C j . Each element of ωk denotes a cost roadscape cluster graph based on the starting and destina- for the corresponding roadscape; these are used for roadscape- tion points that are input (coarse-grained route search). based route searching. For example, ωkr is the cost refer- (3) Find a detailed route that connects roadscape clusters in enced when searching for rural-prior routes. each type (fine-grained route search). Definition 6: Intra-cluster similarity of roadscape vector. (4) Recommend four types of routes in different colors on the The intra-cluster similarity is the mean similarity between map. all pairs of road links included in the cluster. We denote the Here, step (1) can be performed offline because this process does intra-cluster similarity of roadscape cluster C j as intra_sim(C j ). not depend on the inputs. In the next sections, we describe steps The value of intra_sim(C j ) is calculated as follows: (1)–(3) in detail. 1 ∑ ∑ intra_sim(C j ) = cos(s(ei ), s(ek )). (2) 3.2 Generating Roadscape Cluster Graph n|C j | i ∈C j k ∈C j 3.2.1 Roadscape-based Clustering. Given a road network, we Here, ei and ek are road links included in cluster C j , and n form roadscape clusters based on proximities of pairs of road links denotes the total number of links in the road network. The and similarities between their roadscape vectors. Adjacent road 1 The preliminary experimentation to select the roadscape elements was done via links belong to the same cluster if their similarity is greater than crowdsourcing. These four elements are specific to Japanese road network data. De- or equal to a given threshold value. Figure 2 shows the result of tails are outside the scope of this paper. applying roadscape-based clustering to the road network of Awaji RecTour 2018, October 7th, 2018, Vancouver, Canada. 24 Copyright held by the author(s). (C) node = roadscape cluster link (A) (D) (B) Figure 2: Result of applying roadscape-based clustering to Figure 3: Example of a roadscape cluster graph created for the road network of Awaji Island, Japan. Each color corre- Awaji Island’s road network. sponds to a given cluster. Island, Japan. Here, area A corresponds to a rural area, area B cor- 3.2.2 Generating Roadscape Cluster Graph. After extracting the responds to a mountainous area, area C corresponds to a waterside roadscape clusters, we create the adjacency matrix for all road- area, and area D corresponds to an urban area. scape clusters. The adjacency matrix for the roadscape clusters is Algorithm 1 shows the pseudocode for roadscape-based cluster- represented as the |C| × |C| matrix A = [ai j ] | C |× | C | . If ai j = 1, ing. We explain the clustering process as performed by Algorithm 1 clusters Ci and C j have at least one common node; otherwise, they as follows: do not have a common node. We then create the roadscape cluster graph based on the adja- Algorithm 1 Roadscape-based clustering. cency matrix. Figure 3 gives an example of the roadscape cluster Require: Target link e i , Cluster ID k graph created for Awaji Island’s road network. Here, a node in the 1: function roadscapeClustering(e i , k ) roadscape cluster graph corresponds to a roadscape cluster, and a 2: Cluster ID of e i ⇐ k link corresponds to the adjacency relationship between clusters. 3: linkList ⇐ getLink(e i ): Get links adjacent to e i . 4: for each e j in linkList 3.2.3 Assigning Costs to Roadscape Cluster Graph. In order to 5: if Cluster ID of e j = 0 then execute the coarse-grained route search described in the next sec- 6: if cos(s (e i ), s (e j )) >= α then tion, we assign costs to the links of the roadscape cluster graph in 7: roadscapeClustering(e j , k ) advance. A link cost is calculated based on the roadscape vector 8: end if of the roadscape cluster corresponding to the link’s destination. If 9: end if the targeted roadscape element of the next roadscape cluster desti- 10: end for nation is emphasized, let its link cost be lower; on the other hand, 11: return 0 12: end function if it is not emphasized, let its link cost be higher. For example, for a case in which a rural element is targeted, if the rural element of the next roadscape cluster destination is emphasized, let its link We randomly select a road link from the road network. Let ei cost be lower; otherwise, let its link cost be higher. By assigning be the target link, and let e j be one of the links adjacent to ei . costs in such a way, the route to the roadscape cluster where the Here, if two links are connected to a common node, the links are rural element is emphasized is more likely to be chosen in the route considered adjacent. Furthermore, let s(ei ) and s(e j ) be roadscape search. vectors of the respective links. A cost vector ωk of link lk = (Ci , C j ) is calculated as follows: The roadscape-based clustering algorithm is called as roadscapeClustering(ei , k). First, add k as the cluster ID of ei . ωk = dk (1 − s(C j )2 ). (4) Second, get all links adjacent to ei , and set them into linkList. For each link e j ∈ linkList, perform the following process. If a Here, dk is the length of link lk . cluster ID has not been assigned to e j , cos(s(ei ), s(e j )) (Equation (3)) is calculated. If cos(s(ei ), s(e j )) is greater than or equal to the 3.3 Coarse-grained Route Search threshold α, cluster ID k of ei is added as the cluster ID of e j . Fur- As the first search, we execute the coarse-grained route search thermore, roadscapeClustering(e j , k) is recursively called. The method. This method roughly finds four types of roadscape-based above process is repeated until the cluster ID has been added to all routes in the roadscape cluster graph. The process is as follows: of the links in the road network. We define the roadscape cluster obtained by the above process (1) Given starting and destination points, get roadscape clus- as Ck ∈ C, where k corresponds to the cluster ID. In addition, ters and starting and destination clusters, which include the roadscape vector s(Ck ) of cluster Ck is calculated by Equation (1). starting and destination points, respectively. RecTour 2018, October 7th, 2018, Vancouver, Canada. 25 Copyright held by the author(s). Mean route search time[s] (a) (34.257575, 134.722549) → (34.574902, 134.959632) 0 100 200 300 400 500 (b) (34.317774, 134.676412) → (34.348304, 134.896255) Without coarse-grained route search (c) (34.499798, 134.938260) → (34.293801, 134.788816) α=0.95 ** (d) (34.545838, 134.923368) → (34.440009, 134.912038) (e) (34.208185, 134.814500) → (34.430861, 134.830634) With coarse-grained α=0.90 ** α=0.85 ** route search α=0.80 ** For each pair, we execute the route search algorithm that empha- α=0.75 ** sizes each roadscape element and measure the route search time. α=0.70 ** We regard this execution as one trial. We execute this trial ten α=0.65 ** times for each pair and calculate the mean of the route search times across trials. We implemented the route search algorithm using Java and man- Figure 4: Comparison of route search times. aged the road network data using PostgreSQL 9.5. We conducted experiments on a computer equipped with an Intel Core i5-6200U (2) For the targeted roadscape element, find a route that mini- CPU (2.8 GHz), 8 GB memory, 256 GB SSD, and Linux Mint 18.2. mizes the sum of the link costs related to the targeted ele- Figure 4 shows the mean route search times for methods with ments using Dijkstra’s algorithm [2] on the roadscape clus- and without coarse-grained route search. For the method with coarse- ter graph. grained route search, the figure includes the route search time for (3) Repeat step (2) for each roadscape element. each value of α. ∗∗ indicates that a significant difference (p < 0.01) could be confirmed when comparing with the method with- Thus, we obtain four types of coarse-grained routes as the road- out coarse-grained route search by the paired t-test (one-sided test). scape cluster sets that are passed through for each roadscape ele- We can see from Figure 4 that the route search time can be short- ment. ened by using coarse-grained route search. The figure also shows 3.4 Fine-grained Route Search that the higher the value of α was, the shorter the route search time was. In particular, when α = 0.95, the search time with coarse- As the second search, we execute the fine-grained route search grained route search was 6.24 s, whereas it was 456 s when coarse- method for each coarse-grained route. This method finds detailed grained route search was not used. Consequently, we can say that routes that connect roadscape clusters. The process for each tar- the use of coarse-grained route search can significantly reduce route geted element is as follows: search time. (1) Find common road nodes of each adjacent cluster in the roadscape cluster sets captured by the coarse-grained route 5 CONCLUSIONS search. (2) Find the shortest route from the starting point to the first In this paper, we have proposed a Roadscape-based Route Rec- common road node that is adjacent to the next cluster. ommender System (R3) that provides diversified roadscape-based (3) While there are common road nodes, find the shortest route routes. Given starting and destination points, R3 provides four types from the common road node to the next common node. of roadscape-based routes: rural-, mountainous-, waterside-, and (4) Find the shortest route from the last common node to the urban-prior routes. To reduce computational costs, we proposed a destination point. coarse-to-fine route search approach that consists of a roadscape- (5) Generate a route that connects all the routes obtained. based clustering method, a roadscape cluster graph, a coarse-grained route search, and a fine-grained route search. Here, we again use Dijkstra’s algorithm [2] to find the shortest We evaluated the performance of R3 using real road network routes. Finally, we obtain four types of fine-grained routes. data with roadscape vectors in the area of Awaji Island. The results show that using coarse-grained route search can significantly re- 4 RESULTS duce route search time. In the future, we will conduct user tests to In this section, we evaluate the performance of the proposed R3 evaluate our system from the users’ perspective. method using network data for a real road in Awaji Island, Japan. The road network data are derived from OpenStreetMap,2 and they include 102,506 road nodes and 212,050 road links for the area of ACKNOWLEDGMENTS Awaji Island. For this area, roadscape vectors for all road links are This work was supported by JSPS KAKENHI Grant Numbers available on the web.3 JP15K12151 and JP16HO593. R3 introduces a coarse-grained route search as preprocessing to reduce the route search time instead of performing a route search REFERENCES on all road links. In this section, we compare the route search times [1] Zaiben Chen, Heng Tao Shen, and Xiaofang Zhou. 2011. Discovering Popular using coarse-grained route search with those not using it. Routes from Trajectories. In Proceedings of the 2011 IEEE 27th International Con- ference on Data, Vol. 4. 900–911. First, we prepare the following five pairs of starting and desti- [2] Edsger Wybe Dijkstra. 1959. A Note on Two Problems in Connexion with nation points. Graphs. Numer. Math. 1 (1959), 269–271. [3] Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: 2 https://www.openstreetmap.org/ A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM 3 https://zenodo.org/record/1405255#.W4Yyb-j7T-g symposium on Discrete algorithms. 156–165. RecTour 2018, October 7th, 2018, Vancouver, Canada. 26 Copyright held by the author(s). [4] Hector Gonzalez, Jiawei Han, and Xiaolei Li. 2007. Adaptive fastest path com- Pattern-Aware Trajectory Search. In Mobile Data Management. 362–377. putation on a road network: a traffic mining approach. In Proceedings of the 33rd [9] Ling-yin Wei, Wen-chih Peng, Chun-shuo Lin, and Chen-hen Jung. 2009. Explor- international conference on Very large data bases. 794–805. ing Spatio-Temporal Features. In Advances in Spatial and Temporal Databases, [5] Evangelos Kanoulas, Yang Du, Tian Xia, and Donghui Zhang. 2006. Finding Lecture Notes in Computer Science. 399–404. fastest paths on a road network with speed patterns. In Proceedings of the 22nd [10] Ling-Yin Wei, Yu Zheng, and Wen-Chih Peng. 2012. Constructing popular routes International Conference on Data Engineering, Vol. 2006. 10. from uncertain trajectories. In Proceedings of the 18th ACM SIGKDD international [6] Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M. Ni. 2013. Finding time period- conference on Knowledge discovery and data mining. 195–203. based most frequent path in big trajectory data. In Proceedings of the 2013 ACM [11] Jing Yuan, Yu Zheng, Chengyang Zhang, and Wenlei Xie. 2010. T-drive: driving SIGMOD International Conference on Management of Data. 713–724. directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL In- [7] Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. 2009. ternational Conference on Advances in Geographic Information Systems. 99–108. Fast shortest path distance estimation in large networks. In Proceedings of the [12] Jing Yuan, Yu Zheng, Liuhang Zhang, XIng Xie, and Guangzhong Sun. 2011. 18th ACM conference on Information and knowledge management. 867–876. Where to find my next passenger. In Proceedings of the 13th international confer- [8] Ling-yin Wei, Wen-chih Peng, Bo-chong Chen, and Ting-wei Lin. 2010. Eleventh ence on Ubiquitous computing. 109–118. International Conference on Mobile Data Management PATS : A Framework of RecTour 2018, October 7th, 2018, Vancouver, Canada. 27 Copyright held by the author(s).