Various unknown circumstances may afect users' travel behaviors between two locations on the road network, hence it is complicated to provide satisfactory personalized route recommendations. In this paper, we believe that users' travel behaviors are reflected and can be learned from their historical GPS trajectories. The Behavior-based Route Recommendation (BR2) method is proposed to compute personalized routes based exclusively on users' travel preferences. The concepts of appearance and transition behaviors are used to describe users' travel behaviors. The behaviors are extracted from users' past travels and the missing behaviors, of unvisited locations, are estimated with the Optimized Random Walk with Restart technique. Then, the temporal dependency of travel behaviors is considered by constructing a time diference interval histogram. Last, a behavior graph is generated to allow the maximum probability route computation with the shortest path algorithm, resulting in the most likely route to be taken by a user. Experiments conducted on two real GPS trajectory data sets demonstrate the eficiency and efectiveness of the proposed method.
With advances in Global Positioning System (GPS) technology
and the popularity of mobile devices, massive amounts of
human movement data in GPS trajectories have been collected and
are available for research, which provides an alternative way to
explore travel route recommendation. Route recommendation
systems usually suggest routes based on the optimization of cost
functions of either distance or travelling time. However, it has
been observed that in the real world the shortest or quickest
routes are often not taken [
The proper representation of GPS readings allows the analysis of the relationship between users and their behaviors. Users’ travel behaviors reflected in historical GPS trajectories are the implicit feedback of their preferences, as they do not explicitly rate preferred routes. Since it is laborious to use surveys and questionnaires to acquire the explicit feedback about traveling preferences from individual users, users’ travel behaviors are captured based on implicit feedback obtained from their past travels.
The consideration of users’ preferences in route
recommendation can be problematic when suggesting routes to
untraveled locations. To alleviate this issue, some studies have been
conducted in personalized route recommendation based on
collaborative filtering (CF) methods, e.g. item-based CF and matrix
factorization (MF), to acquire more information through users
that share similar preferences [
Time is another essential factor for the efective comprehension of users’ travel behaviors, as users’ behaviors tend to be similar during specific intervals of the day. For instance, a user that has a behavior of taking a route between an origin and destination at noon might have a diferent behavior at midnight, but the same behavior is expected to be shown at times close to noon. To accurately represent temporal dependency and to efectively incorporate it in the recommendation process are challenges that need to be addressed.
In this study, we propose a personalized Behavior-based Route
Recommendation method, named BR2, to extract users’ travel
behaviors and compute the route with maximum probability,
which refers to the route that users are most likely to take based
on their previous travels. In BR2, the implicit information of users’
travel behaviors is extracted from their historical movements.
Compared with popular CF methods, the random walk with
restart (RWR) has been proven to provide better estimations
when considering users’ implicit feedback [
In the remainder of this paper, Section 2 outlines the related works regarding CF techniques and route recommendation. Section 3 presents the personalized route recommendation methodology and explains the proposed method step by step. Section 4 discusses the experiment results. Finally, Section 5 exposes the conclusion and further work of this research. 2 2.1
Recommendation systems are popular for providing predictions that interest people in various scenarios. One of the approaches of recommendation systems is given by CF, which considers information of preference from multiple users to predict missing ratings of users on items, and some of its popular methods are the item-based CF, MF, and RWR.
The item-based CF is one of the most simplistic methods which
considers the similarities between items to calculate values for
others without a user rating [
Among the latent factor models, MF is one of the most used
methods for recommendation problems [
Random walk is a process that describes the probabilities of
series of random movements in a dimension space. In
recommender systems, one of the techniques that considers personal
preferences is the RWR. While the usual approach of random
walk traverses a graph only based on its structure, leading to
an exclusive convergence, the RWR makes uses of a probability
of returning to the original node on each movement. Therefore,
the technique allows personalization by having lower ranking
values given to nodes farther from the origin node [
General route recommendation aims to provide a route between two points in a road network, an origin and a destination, based on a given cost function. Researches have been conducted to study human movement and provide route recommendations based on historical GPS trajectories.
Chen et al. [
These studies contribute to the area of route planning and travel recommendation, but neither of them is truly personalized, as they do not study users’ personal route preferences on the road network. 2.3
Diferently from general route recommendation, personalized route recommendation considers users’ preferences in the definition or calculation of a cost function. While some studies explore users’ preferences through explicit feedback, collecting information by directly querying users, others assume that preference factors cannot be modelled entirely and that users might not be fully aware of their own preferences. Our study is focused on the latter assumption.
Several researches explore personalized route
recommendation through the optimization of the cost function based on
multiple criteria either weighted directly by users or defined by their
driving preferences information [
Another approach is focused on providing personalized tourism
route recommendation based on social media data. Studies have
used users’ data to model route attributes [
Personalized route recommendation based on historical GPS
trajectories is another branch of research. McGinty and Smyth
[
Letchner et al. [
Cui et al. [
A diferent approach is proposed by Wang et al. [
This section discusses the proposed method of the Behaviorbased Route Recommendation (BR2). The following preliminaries are first defined for this research. 3.1
The preliminaries of this study are defined as follows.
G = (V , E) composed by a set of vertices V and edges E. A vertex v ∈ V represents the boundary of road segments and an edge e ∈ E represents a road segment, containing starting and ending vertices, denoted as e .start and e .end, respectively, where e .start ∈ V and e .end ∈ V .
Definition 2 - GPS reading. A GPS-reading is a 3-tuple p = (t, lat, lnд) in which t represents a timestamp, and lat and lnд are the latitude and longitude of the location of the GPS-reading.
Definition 3 - GPS trajectory. A GPS trajectory tr j = (p1, p2, p3, · · · , pk ) consists of a sequence of GPS-readings, such that pi .t − p(i−1).t > 0 and 1 < i ≤ k.
Definition 4 - Route. Given a road network G = (V , E), a route R starting from vertex vi and ending at vertex vj is a sequence of connected road segments R = (vi , e1, e2, e3, · · · , el , vj ), where vi , vj ∈ V and ei ∈ E; ei is the i-th road segment in R, ei , ej if i , j, e1.start = vi , and el .end = vj .
Two types of behaviors are proposed to extract the user’s movement behaviors on the road network. First, to provide a global overview of how frequently users are in specific locations at a certain time on the road network, the concept of appearance behavior is defined to represent the relation between location and time of users’ movement. The second, transition behavior, captures the sequential relation of appearance behaviors, not only giving a sense of location regularity but most importantly of direction. Both behaviors are formally described as follows.
Definition 5 - Appearance behavior. An appearance behavior is defined as tuple of the road segment and the time, denoted as b = (e, t ), where e is an edge of the road network and t is a time interval of a day, and it describes the location and time of a user’s movements. For a given user u and an associated appearance behavior b, the frequency that user u has behavior b is represented by f rq(u, b).
tb represents the relationship of two sequential appearance behaviors bi = (ei , t ) and bj = (ej , t ) at the same time interval t , such that ei .end = ej .start . It is denoted as an ordered tuple tb = (bi → bj ) or tb(i→j) in short. Similarly, the frequency that user u has transition behavior tb is given by f rq(u, tb).
Both appearance and transition behaviors contribute to capture the implicit travel preferences of each user. This implicit travel preference information is essential in solving the problem of the personalized route recommendation, as the recommendations need to truly reflect users’ priorities. 3.2
The framework of the proposed BR2 is illustrated in Figure 1. The ifrst step of BR 2 is data preprocessing. The GPS trajectories are split into trips with defined origins and destinations, the trips are matched to the road network by applying the map matching technique, and the outliers are removed from the trajectories. As a final step of the preprocessing component, the appearance and transition behaviors are generated from the historical users’ routes. Since users, in general, travel on few routes daily, covering a limited number of road segments in a study area, the missing travel behaviors for each user need to be estimated. In the second step, the RWR technique is used to estimate users’ appearance and transition behaviors on each untraveled road segment. With the missing behaviors frequencies estimated, the temporal dependency is evaluated in the data set by building a time interval diference histogram. The histogram indicates how the data is distributed and suggests the number of intervals that should be considered in the route recommendation process. Then, the probabilities are calculated from the travel behaviors for a defined origin and destination considering the Markov property. In addition, the Laplace smoothing method is applied to estimate the probability of users’ missing travel behaviors for the road segments that have never been visited previously by any user.
Finally, the last stage is the recommendation of the route with maximum travel behavior probability. To facilitate the route computation, a behavior graph is constructed to represent the travel behaviors and the relationship among them. Dijkstra’s algorithm is used in the behavior graph to find the route maximum travel behavior probability. 3.3
The preprocessing can be divided into three parts. First, since
a GPS trajectory usually tracks users for a long period of time
and contains multiple trips of the users, trajectory
segmentation is first applied to divide the raw trajectory into several
sub-trajectories [
GPS trajectory
Road network Map matching & segmentation
Historical routes
Travel behaviors
Travel behavior frequency estimation (RWR) Temporal dependency processing Behavior probability estimation
Behavior graph
generation
Route search
the road network to obtain users’ historical routes with the map
matching method proposed in [
3.4.1 Random Walk with Restart for Behavior Estimation. In this study, the appearance and transition behaviors are first extracted from the historical users’ trajectories and a user-behavior matrix U Bn×m is built. In user-behavior matrix, rows represent users U = (u1, u2, · · · , un ), columns represent both appearance and transition behaviors B = (b1, b2, · · · , br , tb1, tb2, · · · , tbq ), where m = r + q, and the element U Bi,j of user i and behavior j represents the frequency of the pair (ui , bj ) or (ui , tbj ). The user-behavior matrix can also be represented as a user-behavior graph, in which the nodes (users and behaviors) are connected through edges with weights as the corresponding frequency of the user-behavior pair, as illustrated in Figure 2a.
The RWR technique tackles the problem based on a graph and can approach it with an adjacency matrix representation. Considering the structure of the user-behavior graph shown in Figure 2a, the idea of RWR is to traverse the graph by either moving to a neighbor node or going back to an initial node based on a given restart probability value. Therefore, a behavior node is highly related to a user when it is visited multiple times. A behavior node associated with a higher score value represents the higher probability of being visited from a user node when the graph is traversed. The score values are represented as the weights of the edges in the graph. Overall, the RWR estimates the probability values of all edges in the user-behavior graph by incrementally updating the user-behavior probability values based on past behaviors of the user and the behaviors of the similar behaving user. Since users and behaviors are interpreted as nodes in an undirected graph, the adjacency matrix of the graph is generated with the combination of both users and behaviors, resulting in a large and sparse symmetric matrix, illustrated in Figure 2b. The adjacency matrix has (n + m) rows and columns, composed by four distinct parts: part 1 is a n × n matrix (users by users) composed by similarities between users, part 2 is the user-behavior matrix, part 3 is the transposed user-behavior matrix, and part 4 Users
Behaviors
Users
Behaviors s r e s U s ir o v a h e B 1 3 UBn×mT
UBn×m 2 4 u1 u2 u3 un w11 w1r w2(r+1) w3r wn(r+1) wnm b1 br tb1 tbq (a) Bipartite graph (b) Adjacency matrix is a m × m matrix (behaviors by behaviors) composed similarities between behaviors. This structure is commonly unoptimized due to the exceedingly higher number of behaviors compared to the number of users in a data set.
The adjacency matrix and restart probability c are provided as inputs to the RWR algorithm. The score matrix r , is calculated by:
0 r (t +1) = (1 − c) U Bn×m
T "
U Bn×m 0 # r (t ) + c I(n+m)×(n+m) where U Bn×m represents the row-normalized user-behavior ma
T trix, U Bnxm represents the transposed row-normalized userbehavior matrix, r (t ) is the score matrix of t -th iteration – initially set as an identity matrix – and I(n+m)×(n+m) is the identity matrix with (n + m) rows and columns. The score matrix is calculated iteratively until convergence, in which the diference between the new and previous scores is smaller than a defined threshold ε.
|r (t +1) − r (t ) | < ε After convergence, the RWR algorithm returns the score matrix, which contains the normalized probability values associated with the previously unknown behavior frequencies.
Considering the total number of users n and behaviors m, the adjacency matrix representation contains (n + m)2 elements. Consequently, the time complexity of the algorithm is defined by the total number of iterations for convergence k and the matrices multiplication in every iteration, resulting in a time complexity of O(k(n + m)3).
3.4.2 Optimized Random Walk with Restart for Behavior Estimation. The common RWR algorithm approach makes use of an adjacency matrix as input, processed for as many iterations as needed until the process converges. However, to fit the data into an adjacency matrix representation, both sets of users and behaviors need to be combined in rows and columns to form a symmetric matrix, as shown in Figure 2b.
This representation could be useful if similarity measures between users and between behaviors are available, describing the inner relations between themselves, as the data could be used to ifll parts 1 and 4 of the adjacency matrix presented in Figure 2b. Nevertheless, since we do not explore the similarities between users and between behaviors, the matrix representation is unquestionably unoptimized and leads to unnecessary processing overhead, as the total number of elements in the matrix is exceedingly higher than the actual data in the user-behavior matrix. For instance, for n users and m behaviors the total number of elements in the adjacency matrix is (n +m)2 while the actual data consists of the part 2 in Figure 2b, containing (n ∗ m) elements.
To better handle the estimation of missing behavior
frequencies we use the ORWR algorithm, which considers the
userbehavior bipartite graph represented by the user-behavior matrix
only [
Time is one of the important factors that influence users’ actions
throughout the day, as people are more prone to go to diferent
places during specific times [
An appropriate strategy to predict user’s behaviors by considering temporal information is to study the relation between behaviors at diferent time intervals. Behaviors associated to a given road segment are most likely to be shown on closer time intervals. Temporal dependency is implemented in this study by considering existing behaviors of the same road segment at similar time intervals in the calculation of travel behaviors’ probabilities.
To identify how behaviors at diferent time intervals impact the route recommendation process, a time diference histogram is generated by comparing behaviors of all users related to the same road segments in pairs. For example, if there are 24 time intervals in total, each time interval representing each hour of the day, the time diference histogram is divided into values ranging from -12 to 12, with increments of one, and each interval consists of the frequency that behaviors related to the same road segment happened at a specific time diference.
A pair of appearance behaviors bi and bj refer to the same road segment if bi .e = bj .e and the correspondent absolute time diference interval is defined as |k | = |bi .t − bj .t |. Since transition behaviors consist of sequential appearance behaviors, the rationale is the same. Given a total number of appearance and transition behaviors r and q respectively, the frequency for each time diference interval value k is computed according to the 1.2 cynequ 1 e0.8 rdF0.6 ze liram0.4 oN 0.2 00
Exponential Trendline
Normalized Frequency 1Time Dif ere2nce Interval 3
4 (b) Íir=1 f rq2(tbi ) |k | = 0 f req(k) = ÍÍqiir==11 ÍÍqrjj==11 ff rrqq((btbi i))ffrrqq(b(tjb)j )+ i ,|kj |a,nd0
Since we evaluate all behaviors against themselves, only the absolute time diference intervals are calculated and equally divided for their correspondent interval. For instance, frequencies of time diference intervals of absolute value of one hour are calculated and divided in half for the intervals of -1 and 1. Finally, the obtained frequencies are normalized in the range from zero to one. For example, Figure 3a illustrates a histogram obtained from a real-world data set Geolife by the computation of time diference of behaviors of all driving travelers.
As expected, most of the frequencies are concentrated in the ifrst few intervals close to the zero interval, showing that most behaviors happen at similar time intervals. As an attempt to avoid overfitting and to reduce the noise from the data, a function can be used to represent the values with most importance, closer to the zero interval. In this study, an exponential function f (x ) = aebx is used to represent the data while conveying the notion of decay as the time interval is farther from the evaluated behavior. Figure 3b presents how closely an exponential function represents the ifrst five intervals of the distribution.
The values from the exponential function for each time interval allow weighting the behaviors frequencies from time intervals close to the recommendation time interval. In Figure 3b, for instance, the weighting values w1, w2, w3, and w4, regarding the time diference intervals of 1 to 4, are approximately 0.6, 0.3, 0.2, and 0.1, respectively. The frequencies of similar time intervals are weighted by multiplying them with the corresponding value of the exponential function for a time diference interval. The weighted frequencies are added to the frequency of the behavior at the time interval used for recommendation. For example, for two appearance behaviors bi and bj of the same road segment and user u at time intervals t and t + 1 respectively, if the recommendation is provided at time interval t and the correspondent value of the exponential function for a time difference interval of 1 is w1, the total frequency of behavior bi is f rq(u, bi ) = f rq(u, bi ) + w1 f rq(u, bj ). 3.6
Based on behavior frequencies, probabilities are computed for a user u given a route R at a specific time t . The route with maximum probability reflects the route that the user is most inclined to take, and it is preferred above all others. The route probability is defined as: P (e1, e2, e3, · · · , el , t |u) P (R |u, t ) = P (e1, e2, e3, · · · , el |u, t ) = P (t |u) where e1, e2, e3, · · · , el represent the road network edges, and e1 and el are the incident edges with the origin and destination vertices, respectively. If the user u and time t are known, P (t |u) is constant, thus simplifying the problem to the maximization of the numerator.
With the assumption that the series of behavior probabilities are described as Markov property, the probability of a user behavior depends on the immediate previous behavior, if not related to the origin, simplifying the representation of the problem. Extending the previous equation, the route probability is given by:
P (b1, b2, b3, · · · , bl |u) = P (b1 |u)P (tb1→2 |u)P (tb2→3 |u) · · · where P (b1 |u) is the appearance behavior probability of origin and P (tbi−1→i |u) is the transition behavior probability, from appearance behavior bi−1 to appearance behavior bi .
Since traditional pathfinding algorithms search for the path with the minimal weight, the probability function is transformed in order to shift the problem objective from maximization to minimization. It is achieved by using the logarithm of inversed probabilities as follows:
L = ln L = ln ln L = ln
1 P (b1 |u)P (tb1→2 |u)P (tb2→3 |u) · · · P (tbl −1→l |u)
1 P (b1 |u)
i=1 P (b1 |u)P (tb1→2 |u)P (tb2→3 |u) · · · P (tbl −1→l |u) 1 + Õ−1 l ln 1
P (tbi→i+1 |u)
If there is no historical data of users’ travels through some road segments, the related behaviors will not exist. To prevent the designation of zero to the probabilities of nonexistent behaviors, the Laplace smoothing method is employed for both appearance and transition behaviors by considering the following: P (tbl −1→l |u) f drq(u,b)+α P (b |u) = Íbi ∈So f drq(u,bi )+α d
α Íbi ∈So f drq(u,bi )+α d f drq(u,tbi→j )+α P (tbi→j |u) = Íd k=1 f drq(u,tbi→k )+α d
α Ídk=1 f drq(u,tbi→k )+α d drq(u, f b) > 0 otherwise drq(u, f tbi→j ) > 0 otherwise where drq f represents the estimated behavior frequency, P (b |u) is the probability of appearance behavior b of user u at time t , So is the set of appearance behaviors starting at origin o, P (tbi→j |u) is the probability of transition behavior tbi→j , α is the smoothing parameter, and d is number of appearance behaviors – the behaviors related to the destination road segment, in the case of transition behavior. 3.7
The structure of the road map network graph does not allow the representation of travel behavior probabilities as weights in 3b e3 v1 v6 (a) Road network (b) Behavior graph edges. Therefore, a diferent structure is constructed to enable graph traverse considering probabilities. It is denominated behavior graph and its structure is illustrated in Figure 4. The behavior graph represents each vertex as an appearance behavior and each edge as a transition behavior. The weight ϑ defines the correspondent behavior probability. In addition, the origin and destination vertices of a given trajectory are included in the structure and their edges represent appearance behaviors, illustrated with a diferent notation from other edges and vertices in the graph.
Despite adding complexity in the process by generating a new structure to represent probabilities, the personalized recommended route can be computed as the least log-inverse probability path, which can be solved by any traditional shortest path algorithm. 4
In this section, the performance of the proposed BR2 is evaluated
through the experiments on two real data sets. The first data set,
Geolife [
Four accuracy measures are considered to evaluate the performance of the model: precision and recall based on the number of road segments and based on the distance of road segments. The measures definitions are presented as follows.
Precisionsegments =
# of correct road segments # of road segments on recommended route
Recallsegments = Precisiondistance =
# of correct road segments # of road segments on true route distance of correct road segments distance of recommended route distance of correct road segments
Recalldistance = distance of true route The diferent aspects of the route recommendation performance are assessed by the conduction of experiments. First, we compare the performance of BR2 with other baseline methods. Second, we evaluate the route recommendation performance based on behavior estimation, considering the ORWR in the proposed BR2 method and the previously discussed CF techniques. Last, the influence of temporal dependency on the performance of route recommendation is assessed. 4.1
In this experiment, the recommendation performance of BR2 is
compared against MaP2R [
The obtained results show that BR2 outperforms the other methods in all accuracy measurements. For Geolife data set, BR2 performs on average 38.9% better than the shortest distance route method and 8.5% better than MaP2R. Similarly, for Shenzhen data set, BR2 shows an average enhancement of 38.6% and 11.5%. The better performance of BR2 is due to a more efective estimation of users’ travel behaviors using RWR and to the consideration of temporal dependency between travel behaviors. 4.2
The efective estimation of users’ travel behaviors is critical for personalized route recommendation. In this experiment, we compare the route recommendation performance of ORWR against two popular CF methods, i.e. the item-based CF (represented as IBF) and MF, in the estimation of the frequencies of missing behaviors. We do not consider the temporal dependency in the experiment.
In this analysis, the number of latent factors in matrix
factorization was set as 30, the Laplace smoothing parameter as 1.0−5
for Geolife data set and 1.0−7 for Shenzhen, the convergence
value in ORWR as 5.0−10, and the restart probability as 0.5 for
Geolife and 0.1 for Shenzhen. The results are shown in Table 3.
Due to the large size of the Shenzhen data set, the experiment
with the item-based CF could not be conducted, as a result of
scalability issue [
As seen in the results, for both data sets, the route recommendation with the ORWR obtained the highest precision and recall values for the number of road segments and distance compared to IBF and MF due to its capability to better handle implicit data. In addition, the higher amount of data in Shenzhen justifies a larger gap in performance between the ORWR and the other methods. 4.3
This experiment evaluates the influence of the temporal dependency (TD) in the accuracy of recommendations. The exponential functions, y = 1.067e−0.57|x | for Geolife data set and y = 1.0057e−0.038|x | for Shenzhen data set, were built to represent the generated data distribution histogram, as exemplified in Figure 3b. The weight for the behaviors with diferent time intervals was determined according to the function. These functions were obtained considering behaviors of the closest three time intervals, as it yielded the best accuracy gain in the recommendation. The results presented in Table 2 show the diference in precision and recall of BR2 when temporal dependency was not considered.
As seen in the results, the overall accuracy of the model considerably decreased when temporal dependency was not considered, negatively impacting the accuracy, on average, by 5.6% and 5.1% for Geolife and Shenzhen data sets, respectively. The impact of temporal dependency depends on the behavior distribution and the amount of similar behaviors considered in the recommendation process. 5
In this study, we proposed the Behavior-based Route Recommendation (BR2) to provide personalized routes based on users’ preferences. The methodology uses the appearance and transition behaviors to capture users’ travel preferences, adopts the ORWR to estimate missing behavior frequencies, evaluates temporal dependency through a time diference interval histogram, and searches for the route with maximum probability on the behavior graph. Experiments show the efectiveness of the proposed method.
The lack of data of users with few behaviors was alleviated with temporal dependency but the problem with routes without any previous data was not focused in this research. It is believed that with the inclusion of spatial correlation and other data such as road type, number of lanes, speed limit, and trafic density can lead to a more concise and robust recommendation. Future work also includes the comparison of the optimized model with other personalized route recommendation methods that may provide a treasure trove of improvements to be incorporated to the model. Acknowledgments. The research is supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant to Xin Wang.