-The paper considers the problem of matching GPS tracks to a road network. We presented a map-matching algorithm based on dynamic programming. We collected the tracks of movement around the city of several users on personal vehicles with various trip types to test the proposed algorithm. The data collected after matching to the road network can be used to further identify user preferences and to build a transport recommender system.
The area of recommendation systems has increased significantly over the past few years. Advertising on online resources offers users various products [1,2], based on the purchase history and viewing products in online stores. Streaming services select films and compose playlists of musical compositions for each individual user [3]. Research teams and large IT companies compiled data sets for each field of application to compare the various machine learning methods used in recommender systems. Transport navigation systems are one of the new areas of application of recommendation systems [4,5]. However, generally accepted machine learning methods and datasets for such systems do not yet exist. At the moment, researchers are trying to use publicly available data about user trips, such as OpenStreetMap, Strava or data on taxi driver trips [6,7]. The main disadvantage of such data is the inability to divide the available tracks by users to identify their preferences in choosing a route. Another drawback is the lack of information about the type and purpose of the trip. In the case when the trip is working or a navigation system has been used with the definition of the shortest path, the user preferences received will be unreliable.
The second section presents data on the collected tracks of user trips by personal vehicles. The second section presents data on the collected tracks of user trips by personal transport. The algorithm for linking tracks to the road network and the experimental results are described in the third section. At the end of the work, we presented a conclusion and possible directions for further work and research.
We collected data in Samara in a large city with a population of about a million for 6 months from June to December 2019. Nine people of different sex, age, marital status and income, who are employees of Samara University, recorded the tracks of their trips. Users recorded work trips (a trip from home to work and from work to home) in an amount of at least 25 tracks and personal trips (all other trips) in an amount of at least 25 tracks. We define the route from the departure point to the destination point as a trip. In total, users recorded 489 tracks. 338 tracks were recorded on weekdays and 151 tracks were recorded on weekends. The generalized characteristics of the obtained data for all recorded tracks are presented in table 1.
GENERALIZED CHARACTERISTICS OF THE DATA
Trip distance 4523 km 9249 m 5783 m 74405 m 1264 m
Trip time 183 h 54 min 20 s 22 min 33 s 16 min 35 s 2 ч 18 min 50 s 2 min 13 s
Users recorded trips using personal smartphones with Android and iOS operating systems. Such a recording method is close to the real scenario of using navigation systems, in which the user receives a route or information about the load on the transport network through his smartphone. In this case, the navigation application on the smartphone can record data on the user's movement during interaction with the application.
All recorded tracks on google maps are shown in figures 1 and 2. The recorded tracks cover a significant part of the city's road network. Figure 2 left shows a user who, for six months, used the same route to and from work, and in Figure 2 right, the user used various routes to travel, depending on the congestion of the road network and weather conditions. III. ALGORITHM FOR BUILDING A TRACK USING GPS POINTS
Let { x i , ti }i 0 , I 1 - the data recorded during the trip, where xi ( xi , y i , z i ) are the GPS coordinates of the trip, ti is the recording time of the i-th route coordinate. We take t0 0 for the recording start time.
We describe the road network as a directed graph G (V , W ) , where V - is the set of vertices of the graph, and W - is the set of edges of the graph connecting the vertices of V . Vertices have coordinates xv ( x v , y v , z v ) and the traffic 0 , la c k , light presence S ( v )
1, p r e s e n c e , if th e r e is n o w a y fr o m v1 to v 2 , w v1,v 2 (l w mwax ; h w ; X w ; c w ), o th e r w is e length w , mwax - maximum permissible speed on w , X w - set of points defining an edge w , road network ring code . We describe the edge as , where l w - edge c w 0 , n o t in th e r in g r o a d , . Edge type h w can take the r in g r o a d c o d e , o th e r w is e following values: 0 - 1 la n e 1 - 2 la n e s 2 - 3 la n e s h w 3 - 3 la n e s w ith o u t a c e n tr a l d iv id in g s tr ip .
4 - 2 la n e s w ith a c e n tr a l d iv id in g s tr ip 5 - 4 la n e s w ith a c e n tr a l d iv id in g s tr ip , (C o n tr o lle d a c c e s s h ig h w a y ) The maximum permissible speed in the graph m0 ax m a x mwax and current average speeds awvr for each edge.
wW
Let m in - minimum matching distance (10 m); m ax maximum matching distance (50 m); - time increase factor; - increasing the field of view step (0,2 m); K - the number of points in the group (3-5). Custom parameter : 2 2 1 , 2 0 . x i X wi and the outliers indicator ri that
K 3 : xi 1 , xi , xi 1 . If all xi k w i & ( xi k , xi k ) m in , then
The result of the algorithm is the set { x i , ti , w i , ri , i }i 0 , I 1 , consisting of an adjusted sequence of points { x i , ti }i 0 , I 1 , for any of which an edge in the road network is indicated w i that 1, i - th p o in t is n o t a n o u tlie r , ri 0 , o th e r w is e , speed at the point is i .
Step 1. For each point x i , ti we find the nearest edge w and match the point onto the edge as follows ( Euclidean): and the estimated w i a rg m in ( x i , w ),
wW x i a rg m in ( x , x i ).
x wi
Step 2. Consistently look at all the points by K pieces. For write the points to the result xi k : xi k , w i k : w i k , ri k : 1 .
Then we select and consider all such sequences of points, find the minimum and maximum. In the case when the sequence is violated in time and position, we use the algorithm for linking points to a specific path described below.
After performing step 2, we get the matched sections of the path with gaps as shown in Figure 3. The blue color represents the attached points to the corresponding edges of the graph of the road network.
Next, we consider some arbitrary fragment from i0 to i1 , i.e. points { x i0 , x i0 1 , ..., x i1 } .
Step 3. We determine the time interval for each point from i0 i1 to the extreme and determine the appearance physical possibility of this point. If
ti ti0 ti1 ti then the point is not taken into account and is further ( x i , x i ) 0 m ax or ( x i1 , x i ) m ax considered an outlier ri : 0 .
Step 4. We define a subgraph from point i0 to i1 . We define the shortest path for this i0 i1 [8,9]. After that, we find a point x in the center of the shortest path and build a circle with a radius R (1 ) m a x ( ( x i , x i0 ), ( x i1 , x i )) . In the subgraph we include all the vertices that fall into this circle and the corresponding edges.
Step 5. We find all the paths without loops in the resulting subgraph between i0 and i1 . Denote this set Pi0 ,i1 , where p Pi0 ,i1 : p ( w i0 ,i* ; w i*,... ; ...; w...,i1 ) .
For each path p Pi0 ,i1
we apply the developed algorithm for matching points to a specific path based on dynamic programming. Dynamic programming is often used to solve the map matching problem, which is confirmed by a large number of works [10-12].
Further, to simplify the presentation (but without loss of generality), we consider i0 0 and i1 I 1 . As a criterion for the quality of matching, we use the following:
J p I1 e x p ( x i x ip i 0 2 ) .
n j1 possible has coordinates, v n j
Suppose we have points { x i }iI01 (i1 i0 1 I ) and they must be matched on the path p {v n0 , v n1 , ..., v K 1 } , where v n and v connected by an edge. We discretize
the positions of points p ( w vn j vn j1 ) {v n0 , v n1 , ..., v K 1 } . For car discretization 2 м. Let the total number of positions N , moreover p ( 0 ) ~ v n0 , p ( N 1) ~ v nK 1 . We calculate I arrays of characteristics of the proximity of a point xi to p how 2 i ( n ) e x p ( x i p ( n ) ) .
The task is to find the
I 1 n (i ) i 0 , I 1 : i ( n (i )) m a x , where n (i ) n (i 1) . i 0 sequence
The main recurrence ratio (for the dynamic programming algorithm):
I 1 m a x i ( n ( i )) n (i ) i 0 i ( n ( il )) il 1 m a x m a x i ( n ( i )) , n ( il ) n ( il1 ), N n (i ) n ( il ) i 0 I 1 m a x i ( n ( i )) n ( i ) n ( il ) i il 1 j Denote j ( n ) m a x i ( n (i )) , i ( n ) - similarity, i ( n ) n (i ):i j i 0 - max integral similarity, i ( n ) - point position list.
The result is contained in 0 ( 0 ) and 0 ( 0 ) .
Algorithm (start from the end): for i I 1, 0 for n N 1, 0 if ( i I 1 ) else i ( N 1) i ( N 1) i ( n ) i ( n 1) i ( n ) i ( n 1) else / / ( i I 1 ) else else i ( N 1) i ( N 1) i 1 ( N 1) i ( N 1) i 1 ( N 1) i ( N 1).a d d ( N 1) if i ( n ) i 1 ( n ) i ( n 1) else i ( n ) i ( n 1) i ( n ) i ( n 1)
The result of the algorithm for matching the track to the road network is shown in Figure 4. The purple line shows the GPS coordinates of the track, the green line shows the matching to the road network.
In our work, we presented a dataset containing tracks of user trips by personal vehicles. The paper also presents an algorithm for matching GPS travel tracks to a road network. The results of the algorithm are demonstrated on the city's road network. The presented data set of matched tracks to the road network can be used in the transport recommendation system development to obtain a profile of individual user preferences as a further area of research.