Keywords

1 Introduction

Path observation is one of the research materials of an overview of urban traffic networks [1] and a part of the spatial analysis method's spatial analysis method [2]. It is commonly used in urban road maintenance, network coordination [3], traffic planning, and others [4]. The center of route analysis is the shortest path and the safest path, and the path optimization is to use the concept of tactical research planning to maximize the organizational efficiency and usage and road network, vehicle routing, delivery of goods, etc. [5]

In the case of confidence, there have been several studies on the shortest path analysis algorithm, e.g., Bellman algorithm [6], Dijkstra algorithm [7], and Dreyfus algorithm [8] have been the traditional algorithms. Nonetheless, under complexity, the shortest path problem can be loosely separated into four parts. This paper looks at the most straightforward path of random road length change, the shortest route with different cost functions, the shortest path with random road length change under the condition of time independence, and the shortest path of interval length.

Nevertheless, in the actual driving of urban vehicles, the above shortest path studies do not consider unknown considerations of the other road route conditions, e.g., rush hours, limited speed, or road situation [9]. Therefore, this study does more work focused on optimization allocation based on the Dijkstra algorithm. First, the urban road network is transformed into a driven graph, including nodes and connections, using the geographic information network mapping technology. The municipal road is transformed into a directed graph. Second, we consider several factors, e.g., the type of route, node stay time, speed limit, the direction of driving of vehicles, and other factors. A starting point to the endpoint is measured and evaluated with the time and cost to optimize global results. It means that the time or expense from the starting point to the parameter is calculated according to the time cost and distance.

Besides the expense restriction considerations and the calculated optimum paths, the shortest route scenarios under unconstrained conditions [10], hazard road condition, and speed limit mode are also considered for testing on the spot.

2 Related Work

2.1 Dijkstra Algorithm

Dijkstra algorithm is a standard algorithm for finding the shortest path in graph theory proposed by Dijkstra, a Dutch computer scientist, in 1959 [11]. The algorithm can find the shortest path from a point in a graph to any other vertex. Dijkstra algorithm divides network nodes into three parts: unlabeled in the network graph, all nodes are initialized as unlabeled nodes. In the process of searching, the nodes that are connected in any path and travel nodes are temporarily marked nodes. In each cycle, the shortest path length from the origin point is searched from the temporarily marked nodes as the permanently marked nodes until the nodes are found. As shown in Fig. 1, assuming that the origin point of the node network is node 0 and the target point is node 4, the shortest path distance between node 0 and node 4 is calculated (the length between nodes is assumed).

Fig. 1
figure 1

Meshed network of the route

Full size image

Suppose each node has a pair of labels \(\left( {w_{i} ,p_{j} } \right)\), \(w_{i}\) is the length of the shortest path from the origin point to the target point, \(w_{j}\) is the shortest path length from the origin point s to any node j (the shortest path from the vertex to itself is the zero path (the path without arc), and its length is equal to zero), and \(p_{j}\) is the length from the origin point s to the node j. The shortest path from the origin point I to the target node j is solved. The basic process is as follows:

  1. (1)

    Initialization. The origin point is set to

    1. (i)

      If the shortest path length \(w_{s} = 0\), \(p_{s}\) is null;

    2. (ii)

      The path length of all other nodes is \(w_{i} = \infty\), \(p_{i} = s\);

    3. (iii)

      Mark the origin point S. mark all marked nodes \(k = s\), and set other nodes as unmarked.

  2. (2)

    Verify the distance from all marked nodes K to their directly connected unlabeled nodes J, and set

    $$w_{j} = \min \left\{ {w_{j} ,w_{k} + d_{kj} } \right\}$$
    (1)

    where \(w_{j}\) is the shortest path length of unlabeled node j, \(w_{k}\) is the shortest path length of labeled node k, and \(d_{kj}\) is the direct connection distance from node k to node j.

  3. (3)

    Select the next point. From all unlabeled nodes \(w_{j}\), select the smallest labeled node i, that is, \(w_{i} = {\text{min}}w_{j}\) (all unlabeled nodes j), and node i is selected as the point in the shortest path and set as the marked point

  4. (4)

    Find the previous point of node I. find the point \(j^{\prime}\) directly connected to node i from the marked node. As the previous point, set \(i = j^{\prime}\)

  5. (5)

    If all nodes have been marked, the algorithm will find the shortest path; otherwise, mark \(k = i\) and go to step (2). Table 1 shows a list of an example of the shortest path of node 0 to node 4 processing.

    Table 1 List of an example of the shortest path of node 0 to node 4 processing
    Full size table

2.2 Algorithm Optimization

The optimization is implemented based on the Dijkstra algorithm as follows: firstly, the temporary set \({\text{NB}}_{s}\) of the starting point, the neighbor nodes \(k\) with the smallest distance is selected as the transition point, and at the same time, it is assigned to the identification set \(S\). The union of the temporary set of all nodes in the identification set s and the difference set of the identification set (\(\cup {\text{NB}}_{s} S\), \(i \in S\)), a node \(W_{k}\) with the minimum path distance value is selected as the next transition point and is assigned to the identification set S. Repeat the above process until all nodes are identified \(\left| s \right| = n\), and the algorithm ends. Let \({\text{NB}}_{i}\) be the temporary set of nodes i, S be the identification set, \(w_{i}\) be the shortest path length from source point s to node j, \(P_{i}\) be the previous node of j point in the shortest path from s to j, and \(D_{ij}\) is the distance from node i to node j.

  1. (1)

    Initialize identity collection \(S = \left\{ s \right\}\), \(w_{i} = d_{si} \;\;i \in {\text{NB}}_{s}\) otherwise \(w_{i} = \infty \;i \in {\text{NB}}_{s} ;P_{i} = s\).

  2. (2)

    If the distance between \(k\) temporary set node and origin point is the smallest \(d_{sk} = {\text{mind}}_{si}\), then \(S = S \cup \left\{ k \right\},j \in {\text{NB}}_{s}\)

  3. (3)

    Modify the \(w_{i}\) value in k temporary set node \({\text{NB}}_{k} = S\), \(w_{i} = \min \left\{ {w_{i} + d_{ki} } \right\}\); if \(w_{i}\) value changes, then \(P_{j} = k,j \in {\text{NB}}_{s} - S\)

  4. (4)

    Select the minimum value of \(w_{i}\) in the marked temporary node, set a and classify it into s, \(w_{k} = {\text{min}}w_{i}\), \(S = S \cup \left\{ k \right\}\) if \(\left| s \right| = n\), the node has been identified, and then the algorithm is terminated; otherwise, go to step (3).

For the network graph with n nodes, the Dijkstra algorithm needs a total of \(n - 1\) iterations to solve the shortest path, and a new node is added to the temporary node set in each iteration. Because the number of nodes not in the temporary node set is \(n - i\) in the ith iteration, then \(n - i\) is needed in the ith iteration. The number of nodes processed is

$$\mathop \sum \limits_{i = 1}^{n - 1} \left( {n - i} \right) = \frac{{n\left( {n - 1} \right)}}{2}$$
(2)

When the number of network nodes in Eq. (2) is n, the time complexity of the path solution is \({\text{O}}\left( {n^{2} } \right)\), which is the time complexity of the shortest path from the origin point to the other nodes in the network graph. With the increase of the total number of nodes n, the calculation efficiency and storage efficiency decrease.

The time complexity \({\text{O}}\left( {n^{2} } \right)\) depends on the number of elements in the temporary set \({\text{NB}}_{s}\) of the transition point k, and then the space complexity of the optimization algorithm is \(O \left( {n \times P} \right)\), where p is the space occupied by the node object under the adjacency matrix storage structure \(N \times N\), which is a constant. According to the number of points and road sections, the average out degree e of nodes can be obtained, i.e.,

$$e = \frac{m}{n}$$
(3)

where m is the number of road sections.

Generally, in the geographic information system network diagram, \(e \in \left[ {1,4} \right]\), because step (3) and step (4) are search and \(V_{i}\) (i = 1, 2, 3, …, n). The time complexity of step 4 is \(O \left( m \right)\), i.e.,\(O\left( {n \times e} \right).\)

3 Model Construction

We assume the road network of a center city by generating randomly to facilitate the experiment. The vector elements of options are imported into the local geographic database, e.g., the expressway, national road, provincial road, and county road. The topological grade is specified as vector elements of the participating road network. The tolerance limit value, such as the speed limit and traffic restriction and turning model, is set up, and the road arc segment node is established. The cost and constraint variables are set according to the connection rule between the road network node and arc segment. The cost variable is path cost expense, and the attribute field of the constraint variable is a Boolean value, namely a single line or double line, respectively.

$$\left\{ {\begin{array}{*{20}c} {R_{w} = \left( {N,R,L_{R} } \right)} \\ {R = \left\{ {\left( {x,y} \right)|x,y \in N,\;{\text{and}}\; L\left( {x,y} \right)} \right\}} \\ {L_{R} = \left\{ {l_{xy} |\left( {x,y} \right) \in R} \right\}} \\ \end{array} } \right.$$
(4)

where \(R_{w}\) represents the road network; \(N\) represents the node set; \(R\) represents the set of road sections, whose elements are ordered pair \(\left( {x,y} \right)\), and indicates that there is a directed path from node x to node y; \(L_{R}\) represents the weighted length of the section, and its elements \(L\left( {x,y} \right)\) denote the weighted length of the directed section \(\left( {x,y} \right)\); \(l_{xy}\) is the length of any section from node x to node y.

The weighted length \(L_{R}\) of a road segment refers to the optimal path which is solved by integrating various dynamic and static attribute constraints according to the multi-objective function and planning requirements, rather than the actual distance or length of the path. Therefore, the optimal path not only refers to the shortest distance in the general geospatial sense. It can also be extended to time, cost, and line capacity.

Some constraints are also considered when nodes or sections in the network cannot operate due to some emergencies, such as traffic accidents, or the original optical path needs to be modified. For example, the road is under maintenance, the distance of the optimal path changes, and maintenance status. If there is a traffic accident at the intersection, it is temporarily not passable; that is, the nodes in the network cannot run, thus, prolonging vehicles’ travel time.

The comprehensive road resistance C of any path is calculated by the weighted summation method

$$C = \mathop \sum \limits_{i = 1}^{n} C_{i} = \mathop \sum \limits_{i = 1}^{n} \left( {D_{i1} a_{1} + D_{i2} a_{2} + \cdots + D_{ij} a_{j} } \right)$$
(5)

where \(C_{i}\) is the comprehensive road resistance of section i, \(D_{ij}\) is the score of the road resistance factor, and \(a_{j}\) is the weight of j road resistance factor. A parameter is used to adjust the weight according to the situation of environmental conditions.

$$a_{j}^{t} = \mu \times a_{j}^{t - 1}$$
(6)

where \(\mu\) is an adjusting variable based on the scenario of environmental conditions.

The upper limit measure is used to calculate the \(D_{ij}\) a score of any road section, and the calculation formula is

$$D_{ij} = d_{ij} {/}d_{j,\max }$$
(7)

where \(D_{ij}\) is the score of \(j\) road resistance factor of section \(i\); \(d_{ij}\) is the actual value of road resistance factor; \(d_{j,\max }\) is the maximum actual value of J road resistance factor.

Algorithm 1. The adjusted optimal path based on the Dijkstra algorithm

Input: A bi-directed graph with weights \(D_{ij} { } = { }\left( {N_{ij} ;{ }C_{ij} } \right)\), the set of all nodes \(N,{ }\) and the set of weighted edges of connected nodes \(C\). The source and target node \(n_{s}\) and \(n_{t}\), respectively.

Output: Shortest path and the length from the source node \(n_{s}\) to the target node \(n_{t}\)

1: Initialization

Visited nodes \(Ne{ } = { }ns.{ }d\left( {ns} \right){ } = { }0\), where \(d\left( {nti} \right)\) is the minimum cost of the shortest path from ns to \(n_{ti}\). \(Nu{ } = { }N{ } - { }Ne\), where Nu is the set of nodes to ns with the undetermined shortest path. \(d\left( {nti} \right){ } = { }min\left( {C\left( {ns;{ }nti} \right)} \right)\), if \(nti{ }\) is a successor to \(n_{s}\), or else,\(d\left( {n_{ti} } \right) = 1\), where \(C\left( {i;{ }j} \right){ }\) is the cost between node i and node \(j\) as Eq. (5)

2: Repeat the following steps until there are no nodes in the set \(N_{u}\)

2.1 Put the node in Nu that has the minimum cost to the old ns as the new source ns. Move the new source node ns to \(N_{e}\); adjust the weight according to the situation of environmental conditions as Eq. (6)

2.2 Set \(d\left( {n_{ti} } \right){ } = { }d\left( {n_{s} } \right){ } + { }min\left( {C\left( {ns;{ }n_{ti} } \right)} \right)\)

3: Find the shortest path from the source node ns to the target node nt

4: Return d(nt), Ne

The initial work of the Dijkstra algorithm is only dealing with the shortest path between two points. Mathematically, these points must be represented by nodes in the graph network. Bellman Ford implemented the possibility of fixing

4 Results and Discussion

In order to test the performance of the proposed scheme, some lines assuming roads are generated randomly in a specified metro urban area based on the grid and sample points under constrains of the condition roads and obstacles. Table 2 lists the comparison of theoretical and actual driving time of the optimized route. It is seen that the travel time of the optimized route, the real travel time is longer, and the difference between the minimum and maximum travel time is 1.2 min and 2.9 min, respectively. In the obstacle mode, the driving time of line 4 is 1.0 min longer than that of line 3. The driving time of line 4 is 1.0 min longer than that of line 3. In the speed limit mode, the actual driving time of urban vehicles inline 5 is limited by road congestion, traffic capacity, and traffic information, which is 1.2 min longer than the real driving time on line 6 is 2.3 min longer than the theoretical driving time of line 6. In the case of a 30 s delay at the intersection node, the actual driving distance is more reasonable, and the real driving time is longer. Therefore, the node delay, road conditions, and speed limit are the main factors affecting the urban vehicle route selection. The number of nodes in the optimal path plays a leading role in the driving time and distance.

Table 2 Obtained results of the optimization of the Dijkstra algorithm for actual driving time and vehicle routing
Full size table

Figure 2a displays the setting for generating points in the road network. Figure 2b shows the generated obstacle maps and the roads’ points as road network grade and speed limit mode, randomly prioritizing provincial roads, national highways, and urban trunk roads and then choosing urban secondary trunk roads and township roads. Figure 2c displays the proposed method's optimal paths close to the actual travel time and distance cost. Drivers would be advised as a priority to these kinds of conditions as assuming that the speed limit of trunk roads is 30 km/h, and of crowed streets is 35 km/h. In the speed limit mode, the shortest path needs to drive 4455.3 m, and the travel time cost is 13.2 min.

Fig. 2
figure 2

Proposed scheme's optical paths based on the Dijkstra for analysis of urban traffic vehicle routing in terms of the travel time and distance cost

Full size image

Figure 2d shows the shortest distance between Hoabinh park and the Linhnam-Hoang Mai, Hanoi, as an example of the most straightforward under the condition of daily road status and vehicle speed in the middle afternoon. Assuming that Hoa Binh the park, Hanoi is the initial source point and the Linhnam–Hoangmai, Hanoi as the target node, the optimal distance, and time path between Hoa Binh park and the Linhnam–Hoangmai can be calculated at any intersection. The route length is 19,377.8 m, and the time cost is 25.7 min, while the route distance under time constraint mode is 19,374.9 m, and the minimum driving time is 24.7 min. In actual driving, route selection is affected by drivers’ preference for the shortest time and shortest distance. Figure 3 shows a comparison of the suggested approach's outcomes regarding the average optimization error rate with the A* algorithm and dynamic programming schemes to analyze urban traffic vehicle paths. It can be seen that the suggested approach based on Dijkstra algorithm optimization produces the lowest average converge error rate in comparison with other methods.

Fig. 3
figure 3

Comparison of the suggested approach's outcomes regarding the average optimization error rate with the A* algorithm and dynamic programming schemes to analyze urban traffic vehicle paths

Full size image

Table 3 illustrates the comparison of the proposed scheme's results with the A-star algorithm and dynamic programming methods. It is seen that the proposed approach produces the results efficiently for the analysis of urban traffic vehicle routing planning.

Table 3 Comparison of the results of the proposed scheme with the A-star algorithm and dynamic programming methods
Full size table

5 Conclusion

This study proposed an analysis of urban traffic vehicle routing based on the Dijkstra algorithm optimization for suggesting road selection and optimization under various constraints jointly built in the central metropolitan area. The optimal path cost depends on the number of path nodes, link constraints, and speed limit conditions. In this planned scheme of the road network, the specified for both origin point and the target point, the Dijkstra's obtained optimal path was implemented under distance and time cost constraints. The analysis and realization are verified with the geocoding, network topology, and network analysis tools. The results show that the integration of network analysis technology and the Dijkstra algorithm realizes the urban vehicle route's optimization decision. Also, the Dijkstra algorithm reduced the number of node visiting and time complexity. Under the driving time and distance constraints, the speed limit, road hierarchy, and road conditions are the line selection's restrictive factors. The graphical description could provide technical support and reference for the driver's driving strip and traffic management department for decision making.