We propose the Roadscape-based Route Recommender System (R3), which provides diversified roadscape-based routes. Given starting and destination points, R3 provides four types of roadscapebased routes: rural-, mountainous-, waterside-, and urban-prior routes. To reduce the computational cost, we propose a coarse-toifne route search approach that consists of a roadscape-based clustering method, a roadscape cluster graph, a coarse-grained route search, and a fine-grained route search. We evaluated the performance of R3 using network data for a real road. The experimental results show that using coarse-grained route search can significantly reduce route search time.
• Information systems → Social recommendation;
Cars are driven not only for transportation but also for the pleasure of it. Some people want to drive along the seaside or on rural roads while enjoying their favorite landscape. We call such roadside landscapes “roadscapes.” In such situations, it is not always the best solution to provide the shortest or the fastest route. An alternative solution is to provide routes with favored roadscapes even if they involve a detour.
Given starting and destination points, a route recommender system provides routes from the starting point to the destination point. The majority of traditional route recommender systems provide the shortest routes [3, 7], the fastest routes [4, 5, 9, 11, 12], or popular routes [1, 6, 8, 10]. As mentioned above, the shortest and the fastest routes do not always satisfy the user’s demands. Systems that recommend popular routes provide routes many people are interested in. Wei et al. [8] extract popular routes by mining road links many people are interested in from their trajectories. Such route recommender systems consider the attractiveness of routes based on the wisdom of crowds, without considering the content features of routes.
In this paper, we focus on the roadscape as a route feature and propose the Roadscape-based Route Recommender System (R3), which provides diversified routes on the basis of roadscapes. Given starting and destination points, R3 provides four types of roadscapebased routes: rural-, mountainous-, waterside-, and urban-prior routes. For example, a user who likes waterside views can select waterside-prior routes from the four types of routes provided. To develop such a route recommender system, we have proposed a method for estimating roadscapes of given road links. In particular, we defined rural, mountainous, waterside, and urban elements as the roadscape elements, which are basic elements that compose a roadscape, through preliminary experiments. We defined a roadscape vector each of whose elements corresponds to a roadscape element and proposed a method for estimating such roadscape vectors for given road links. We presuppose that R3 is to be used on road network data with roadscape vectors.
Traditional route searching algorithms, such as the Dijkstra algorithm [2], are given the costs of road links and find a route that minimizes the sum of their costs. The simplest approach is to apply the traditional method and reduce the costs of the road links having the targeted roadscape elements. However, there is a high computational cost in applying such a method to a very large road network.
To reduce the computational cost, we propose a coarse-to-fine route search approach. We focus on the concept that similar roadscapes do not exist as fragments but in clusters. For example, there are some areas composed of similar roadscape elements, such as rural areas, mountainous areas, waterside areas, and urban areas. Based on this characteristic, we expect that we can reduce the computational cost by clustering similar roadscape areas in advance.
In this approach, we firstly extract areas—roadscape clusters— composed of similar roadscape elements by using a roadscapebased clustering method. Secondly, we create a roadscape cluster graph whose nodes correspond to the roadscape clusters and whose links correspond to the links between roadscape clusters. In the route searching process, given the roadscape cluster graph and starting and destination points, we roughly find four types of roadscape-based routes, which are the roadscape cluster sets passed through, one for each roadscape element; we call this the coarse-grained route search. Then, we find specific routes that connect the roadscape clusters in each type of route; we call this the ifne-grained route search.
The contributions of this paper are as follows:
We propose the Roadscape-based Route Recommender System (R3), which provides diversified roadscape-based routes, namely, rural-, mountainous-, waterside-, and urban-prior routes.
To reduce the computational cost, we propose a coarse-toifne route search approach that consists of a roadscape-based clustering method, a roadscape cluster graph, a coarse-grained route search, and a fine-grained route search.
We evaluate the performance of R3 using network data for a real road. The results show that using coarse-grained route search can significantly reduce route search time. 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 2 V represents an intersection or an endpoint of a road. A road link ek = ¹vi ; vj º 2 E is a directed link from the starting node vi to the ending node vj . A road link ek is assigned a cost wk according to the length of the link.
basic elements that compose a roadscape. We define four roadscape elements: rural, mountainous, waterside, and urban elements. These elements were selected by preliminary experimentation.1 Definition 3: Roadscape vector. A roadscape vector is deifned 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 as s¹ei º = ¹sir ; sim ; siw ; siu º. Each element of the vector denotes the probability of how strongly ei includes the corresponding roadscape element. Therefore, the sum of the values over all elements is 1.
Definition 4: Roadscape cluster. A roadscape cluster Cj 2 C is represented by a set of road links having similar roadscape vectors. A roadscape vector s¹Cj º of roadscape cluster Cj is represented by the mean vector of the roadscape vectors of the road links included in cluster Cj . Therefore, we define s¹Cj º as follows: s¹Cj º = 1
∑
jCj j i 2Cj
s¹ei º:
(
Definition 5: Roadscape cluster graph. A roadscape cluster graph is a directed weighted graph G = ¹V; Eº, where V is a set of roadscape clusters Ci and E V V is a set of links between roadscape clusters. A link lk = ¹Ci ; Cj º 2 E is a directed link from the starting node Ci to the ending node Cj . The road link lk is assigned a cost vector ωk = ¹ωkr ; ωm ; ωw ; ωku º based on the roadscape vector Cj of endk k ing roadscape cluster Cj . Each element of ωk denotes a cost for the corresponding roadscape; these are used for roadscapebased route searching. For example, ωkr is the cost referenced when searching for rural-prior routes.
The intra-cluster similarity is the mean similarity between
all pairs of road links included in the cluster. We denote the
intra-cluster similarity of roadscape cluster Cj as intra_sim¹Cj º.
The value of intra_sim¹Cj º is calculated as follows:
intra_sim¹Cj º =
cos¹s¹ei º; s¹ek ºº:
(
∑ ∑
njCj j i 2Cj k 2Cj
Here, ei and ek are road links included in cluster Cj , and n
denotes the total number of links in the road network. The
1The preliminary experimentation to select the roadscape elements was done via
crowdsourcing. These four elements are specific to Japanese road network data.
Details are outside the scope of this paper.
value of cos¹s¹ei º; s¹ek ºº is calculated as follows:
cos¹s¹ei º; s¹ek ºº = s¹ei º s¹ek º :
js¹ei ºjjs¹ek ºj
(
Our proposed Roadscape-based Route Recommender System (R3) provides four types of roadscape-based routes: rural-, mountainous, waterside-, and urban-prior routes. Figure 1 shows a result provided by R3. When a user inputs starting and destination points on the map, the four types of roadscape-based routes are provided in diferent colors.
It is assumed that R3 will be used with a road network with
roadscape vectors. The steps of R3 are as follows:
(
Here, step (
Generating Roadscape Cluster Graph 3.2.1 Roadscape-based Clustering. Given a road network, we form roadscape clusters based on proximities of pairs of road links and similarities between their roadscape vectors. Adjacent road links belong to the same cluster if their similarity is greater than or equal to a given threshold value. Figure 2 shows the result of applying roadscape-based clustering to the road network of Awaji
Island, Japan. Here, area A corresponds to a rural area, area B corresponds to a mountainous area, area C corresponds to a waterside area, and area D corresponds to an urban area.
Algorithm 1 shows the pseudocode for roadscape-based clustering. We explain the clustering process as performed by Algorithm 1 as follows: Algorithm 1 Roadscape-based clustering.
Require: Target link ei , Cluster ID k 1: function roadscapeClustering(ei , k ) 2: Cluster ID of ei ( k 3: linkList ( getLink¹ei º: Get links adjacent to ei : 4: for each ej in linkList 5: if Cluster ID of ej = 0 then 6: if cos¹s ¹ei º; s ¹ej ºº >= α then 7: roadscapeClustering¹ej; k º 8: end if 9: end if 10: end for 11: return 0 12: end function
We randomly select a road link from the road network. Let ei be the target link, and let ej be one of the links adjacent to ei . Here, if two links are connected to a common node, the links are considered adjacent. Furthermore, let s¹ei º and s¹ej º be roadscape vectors of the respective links.
The roadscape-based clustering algorithm is called as
roadscapeClustering¹ei ; kº. First, add k as the cluster ID of ei .
Second, get all links adjacent to ei , and set them into linkList.
For each link ej 2 linkList, perform the following process. If a
cluster ID has not been assigned to ej , cos¹s¹ei º; s¹ej ºº (Equation
(
We define the roadscape cluster obtained by the above process
as Ck 2 C, where k corresponds to the cluster ID. In addition,
roadscape vector s¹Ck º of cluster Ck is calculated by Equation (
3.2.2 Generating Roadscape Cluster Graph. After extracting the roadscape clusters, we create the adjacency matrix for all roadscape clusters. The adjacency matrix for the roadscape clusters is represented as the jC j jC j matrix A = »ai j ¼j C j j C j . If ai j = 1, clusters Ci and Cj have at least one common node; otherwise, they do not have a common node.
We then create the roadscape cluster graph based on the adjacency matrix. Figure 3 gives an example of the roadscape cluster graph created for Awaji Island’s road network. Here, a node in the roadscape cluster graph corresponds to a roadscape cluster, and a link corresponds to the adjacency relationship between clusters.
3.2.3 Assigning Costs to Roadscape Cluster Graph. In order to execute the coarse-grained route search described in the next section, we assign costs to the links of the roadscape cluster graph in advance. A link cost is calculated based on the roadscape vector of the roadscape cluster corresponding to the link’s destination. If the targeted roadscape element of the next roadscape cluster destination is emphasized, let its link cost be lower; on the other hand, 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 cost be lower; otherwise, let its link cost be higher. By assigning costs in such a way, the route to the roadscape cluster where the rural element is emphasized is more likely to be chosen in the route search.
A cost vector ωk of link lk = ¹Ci ; Cj º is calculated as follows:
ωk = dk ¹1
s¹Cj º2º:
(
As the first search, we execute the coarse-grained route search
method. This method roughly finds four types of roadscape-based
routes in the roadscape cluster graph. The process is as follows:
(
Mean route search time[s] 200 300 Without coarse-grained route search
α=0.95 ** irr-sgaeedn rch αα==00..9805 ****
α=0.80 ** itcaohW trsaeeou α=0.75 α=0.70 α=0.65 ** **
**
(
(
Thus, we obtain four types of coarse-grained routes as the roadscape cluster sets that are passed through for each roadscape element. 3.4
As the second search, we execute the fine-grained route search
method for each coarse-grained route. This method finds detailed
routes that connect roadscape clusters. The process for each
targeted element is as follows:
(
(
In this section, we evaluate the performance of the proposed R3 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 Awaji Island. For this area, roadscape vectors for all road links are available on the web.3
R3 introduces a coarse-grained route search as preprocessing to reduce the route search time instead of performing a route search on all road links. In this section, we compare the route search times using coarse-grained route search with those not using it.
First, we prepare the following five pairs of starting and destination points. 2https://www.openstreetmap.org/ 3https://zenodo.org/record/1405255#.W4Yyb-j7T-g (a) ¹34:257575; 134:722549º ! ¹34:574902; 134:959632º (b) ¹34:317774; 134:676412º ! ¹34:348304; 134:896255º (c) ¹34:499798; 134:938260º ! ¹34:293801; 134:788816º (d) ¹34:545838; 134:923368º ! ¹34:440009; 134:912038º (e) ¹34:208185; 134:814500º ! ¹34:430861; 134:830634º For each pair, we execute the route search algorithm that emphasizes each roadscape element and measure the route search time. We regard this execution as one trial. We execute this trial ten times for each pair and calculate the mean of the route search times across trials.
We implemented the route search algorithm using Java and managed the road network data using PostgreSQL 9.5. We conducted experiments on a computer equipped with an Intel Core i5-6200U CPU (2.8 GHz), 8 GB memory, 256 GB SSD, and Linux Mint 18.2.
Figure 4 shows the mean route search times for methods with and without coarse-grained route search. For the method with coarsegrained route search, the figure includes the route search time for each value of α . indicates that a significant diference ( p < 0:01) could be confirmed when comparing with the method without coarse-grained route search by the paired t -test (one-sided test). We can see from Figure 4 that the route search time can be shortened by using coarse-grained route search. The figure also shows that the higher the value of α was, the shorter the route search time was. In particular, when α = 0:95, the search time with coarsegrained route search was 6:24 s, whereas it was 456 s when coarsegrained route search was not used. Consequently, we can say that the use of coarse-grained route search can significantly reduce route search time. 5
In this paper, we have proposed a Roadscape-based Route Recommender System (R3) that provides diversified roadscape-based routes. Given starting and destination points, R3 provides four types of roadscape-based routes: rural-, mountainous-, waterside-, and urban-prior routes. To reduce computational costs, we proposed a coarse-to-fine route search approach that consists of a roadscapebased clustering method, a roadscape cluster graph, a coarse-grained route search, and a fine-grained route search.
We evaluated the performance of R3 using real road network data with roadscape vectors in the area of Awaji Island. The results show that using coarse-grained route search can significantly reduce route search time. In the future, we will conduct user tests to evaluate our system from the users’ perspective.
This work was supported by JSPS KAKENHI Grant Numbers JP15K12151 and JP16HO593.