This paper addresses the task of automatic checking of the road network model. Under the road network model checking, we mean checking completeness and topology of the road network. We propose an original algorithm based on a direction of movement criterion. The proposed algorithm is compared with an existing algorithm based on an optimal distance criterion. The algorithm was implemented and tested using the large transport network of Samara, Russia.
Geoinformation systems are widely used in many areas of our life, including municipal management, transport systems, economics, etc. The question about quality of spatial data becomes more and more important because of increase in the intensity of their usage. In this paper under quality we mean completeness and correctness of the data.
Road network model is the basis for many transport problems, such as the optimal
network planning, optimization of the public transport routes, navigation problems
and so on. The paper deals with one of the possible formulations of the road network
checking tasks: checking connections between road links and correctness of turns
between links. The solution to this problem is necessary for the further use of the road
network in more complex problems, such as shortest path calculation and reliable
routing in stochastic networks [
Completion of incompletely extracted road networks is an important part of road
network model with the use of digital imagery [
The article [
In this paper we use a complex road network graph, that includes the permitted /
prohibited turns between road links. We propose a road network checking algorithm
based on a direction of movement factor. The proposed algorithm is compared with
an existing algorithm based on detour factor and described in [
The paper is structured as follows. In the second section we introduce the basic notation, describe the graph structure and give a problem statement. Existing and proposed algorithms are described in sections 3 and 4. In the fifth section we present the experimental results. Finally, we make conclusions and provide recommendations for further work. 2
We consider a road network as an oriented graph G V , E , where V is a set of nodes corresponding to the road intersections, E is a set of edges corresponding to the road links. Direction of the edge is defined by the driving direction at the corresponding road link.
We assume that the graph has a spatial reference, i.e. each node of the graph has the coordinates (x, y) that are determined by the location of the corresponding road intersection in the real road network.
In this paper we consider an oriented graph, each edge of which has two weight coefficients: ─ t is the travel time on the edge; ─ l is the length of the edge.
Each intersection is converted into a set of geometrically coinciding graph nodes. Each road link is presented by a pair of graph edges with different directions. We add new edge between pair of nodes, if a turn between this nodes is allowed. Additional edges do not have geometric characteristics, their weights are defined by average travel time. Figure 1 shows a diagram of the intersection with the possibility of movement in any direction.
The formal statement of the road network model checking problem can be defined as
follows: develop and implement algorithms for checking the topology of a large city
road network.
We check the connectivity of nodes of the road network and correctness of turns
between road links. The following sections provide algorithms for checking link
hypotheses between nodes in the network, based on a detour factor and a movement
direction factor.
In the paper [
Let ks be the shortest path distance between nodes k and s. Shortest paths are
calculated using Dijkstra algorithm [
ks The detour factor shows the ratio of the distance between nodes in a road network to the optimal distance between these nodes.
For each pair of nodes involved in checking we calculate distances ks and ks . Then we check the following criterion: dc dmcax where dmcax is predetermined threshold coefficient.
If the criterion (1) is satisfied, then all the links of the road network, included in the shortest path between two nodes, is the candidates for additional check, further study is needed for their analysis. (1) Experiments, how the road network checking results depend on the threshold coefficient dmcax , are presented in section 4. 4
Algorithm based on the detour factor has a drawback. If the Euclidian distance between pair of nodes is large, then the distances ks and ks will be almost equal, even if the connectivity of road links is broken. In this section we propose an algorithm based on a different hypothesis, which eliminates this drawback. Let dks v1 , v2 ,, vn be the shortest path from the node k to the node s, where vi , i 0, N 1 is the node in the shortest path with index i.
N is a number of nodes in the shortest path.
The proposed algorithm consists of the following steps: 1. For pair of nodes k and s shortest path d ks is calculated. 2. For each node vi d ks , i 0, N 1 the optimal (Euclidian) distance vis is calculated. 3. Direction of movement factors βi , i 0, N 2 are calculated using the following expression: i vi1s , vi d ks , i 0, N 2 .
vis
i : βi 1, i 0, N 2 .
If the criterion (2) is satisfied, then all the links of the road network, included in the shortest path between two nodes, is the candidates to check. The criterion (2) means that the Euclidian distance to the destination node should decrease during the trip. Such criterion also has a drawback: it can gives false positive error if the optimal distance is slightly increased. To avoid this, we introduce threshold coefficient max . So the criterion is modified as follows: i : i max , i 0, N 2 .
(2) (3)
Experiment 1. Study of the threshold coefficient dmcax impact on the results of the algorithm based on the detour factor. Experiment 2. Experimental study of the algorithm based on the direction of movement factor.
The algorithms are tested on the road network of Samara, Russia. The network consists of 52175 nodes and 76636 links. For experiments 400 graph edges ek E has been artificially removed. The experiment results are presented below. 5.1
For this experiment we choose 10 origin nodes (k1, k2 ,..., k10 ) and 10 destination nodes (s1 , s2 ,..., s10 ) , located in different areas of the city. We choose the following threshold coefficient values θ dmcax 1.08,1.15,1.2,1.3,1.35,1.4.
Firstly for each pair of nodes k, s we calculate the shortest path d ks in the original graph (without removed edges). Next step is performed using the changed graph with removed edges ek . For each pair of origin-destination nodes we calculate the shortest path distance ks , the optimal distance ks and the detour factor ks . If the shortest path d ks in the original graph contains some edges e ek , and the criterion (1) for the changed graph is satisfied, then we suppose, that removed edges is found. If the criterion (1) is satisfied, but the shortest paths in the original and changed graphs are equal (i.e. the shortest path does not contain removed edges), then road network check completed with error. The number of successfully found edges and the errors number are shown on figure 2. Chosen value of the threshold coefficient dmcax depends on the allowable number false positive errors of the algorithm. Using the threshold value in the range 1.2,1.35, we detect about 75-85% of the road network topology errors. Level of incorrectly defined edges is about 4-6%. 5.2
In these experiments we use the same graph and pairs of origin-destination nodes, defined in the previous section.
Again, for each pair of nodes k, s we calculate the shortest path d ks in the original graph, the shortest path d k's in the changed graph and the direction of movement factors βi , i 0, N 2 .
If the criterion (2) for the pair of origin-destination nodes k, s is satisfied and the shortest path d ks contains removed edges e ek , then the algorithm completed successfully. If the criterion (2) is satisfied, but the shortest path d ks does not contain removed edges e ek , then the algorithm completed with false positive error. The results of the experiment are shown in table 1. The proposed algorithm based on the direction of movement factor shows the similar results with the algorithm based on the detour factor with the threshold coefficient value dmcax 1.2 . We detect 88% of the removed edges with false-positive errors in 5.5%. 6
In this paper we propose the algorithm for road network checking based on the direction of movement factor. Under road network checking we mean checking the connectivity of the road links and correctness of turns between links. The proposed algorithms was compared with the base algorithm based on the detour factor. The conducted experiments was performed using the road network of Samara, Russia. The proposed algorithm showed similar results with the base algorithm with the threshold coefficient value dmcax 1.2 . It should be noted, that the proposed algorithm showed good results even in the case, when Euclidian distance between origin and destination nodes are large enough. We plan to conduct the experiments, how the threshold coefficient value max influence on the results of the algorithm based on the direction of movement factor.
This work was supported by the Russian Foundation for Basic Research (RFBR) grant №16-37-00055-mol-a.