scroll identifier for mobile
main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.12.2019 | Research | Ausgabe 1/2019 Open Access

# Bi-level route guidance method for large-scale urban road networks

Zeitschrift:
EURASIP Journal on Wireless Communications and Networking > Ausgabe 1/2019
Autoren:
Dan Wei, Zhaosheng Yang
Abbreviations
FIFO
First-in-first-out constraints
GMFD
Generalized macroscopic fundamental diagram
MFD
Macroscopic fundamental diagram
MSA
Method of successive averages
OD
Origin destination

## 1 Introduction

Dynamic traffic routing guidance is an effective way to alleviate urban traffic congestion problem; it is based on dynamic traffic assignment, which influences travel decision making of travelers through releasing dynamic guidance information and generating guidance path and adjusts traffic flow of urban road networks so that traffic flow can be assigned into entire urban road network evenly. Thereby, traffic congestion problem can be alleviated and operation level of entire road network can be promoted. Traffic guidance system is divided into two categories: ‘Central traffic guidance’ and ‘Distributed traffic guidance,’ which have different ways of information processing and guidance path generating. There are two effective thinking to promote traffic guidance path generation efficiency: first, it considers data processing capacity, through limiting the path (node) searching range to reduce the scale of data processing [10]; second, from the perspective of data processing, adopting parallel computing, bidirectional search, and other methods to improve computing efficiency [11, 12].
Central traffic route guidance can improved the overall operation efficiency of road network. However, it is difficult to achieve the real-time requirement of real-time traffic induction because of the need for massive data calculation. Distributed traffic route guidance computing time and space complexity are lower, which can satisfy the real-time requirement, but it may cause congestion transfer and new congestion. Therefore, this paper proposes a bi-level path guidance strategy which combines both central and distributed traffic route guidance. In upper-level route guidance, central route guidance takes place in central end; guidance sub-region is the elementary unit of system optimal dynamic traffic assignment, and guidance path of sub-region level can be generated then sent to the vehicle terminal. In lower-level route guidance, distributed route guidance is done by vehicle terminal; it searches and generates user optimal path from guidance sub-region which is passed by guidance path of guidance sub-region level from the central end. This strategy makes a combination of central path guidance and distributed path guidance, which effectively compensates their own deficiencies of those two guidance methods. This strategy considers the intentions of both traffic management and traveler. And it reaches the compromise of system optimum and user optimum, which is a commendable attempt of improving traffic flow guidance system. The purpose is to improve the rational distribution of road traffic flow, improve the efficiency of road network operation, reduce delay, and alleviate traffic congestion.

## 2 Methodology

### 2.1 Traffic guidance sub-region division based on MFD

#### 2.1.1 Macroscopic fundamental diagram model specification

With the number of network operation vehicles (N) as the abscissa, road network operating capacity (P) as the ordinate, reflect the whole process of the road network shifting from heavy to smooth. The network operating capacity is represented as operating vehicle mileage in the road network per unit time (the product of network operating vehicle and average travel speed ‘V’).
$$P=h(N)$$
(1)
$$P=N\cdot V=N\cdot \frac{\sum \limits_i{v}_i\cdot {l}_i}{\sum \limits_i{l}_i}$$
(2)
In the equation, h(•) is the functional relationship between the vertical and horizontal coordinate variables, vi is the travel speed of road section i (m/s), and li is the length of road section i.
The operating capacity P can be obtained through real-time monitoring the average speed V.and the number of operating vehicles N and then get the MFD scatter plot of the road network.
Obtained scatter points are used for curve fitting by cubic polynomial with the constant term of zero:
$$P(N)={m}_1{N}^3+{m}_2{N}^2+{m}_3N$$
(3)
In the equation, m1, m2, m3 represent the parameter calibrated in the model.
Considering the impact on MFD caused by the in homogeneity of spatial distribution of road network density, the nonuniform coefficient σ can be introduced in the model, then obtain the generalized macroscopic fundamental diagram (GMFD):
$$P\left(N,\sigma \right)=\left({m}_1{N}^3+{m}_2{N}^2+{m}_3N\right)\left(a\cdot {e}^{b\cdot \sigma }+c\right)$$
(4)
In the equation, m1, m2, m3, a, b, c represent the parameters calibrated in the model.
$$\sigma =\sqrt{\sum \limits_i\frac{{\left({k}_i-{k}^w\right)}^2}{I}}$$
(5)
In the equation, ki represents the density of road section i, kw represents the average density of the road network, and I represents the number of road sections in the road network.

#### 2.1.2 Traffic guidance sub-region division

The more uniform the spatial distribution of section density of the road network is, the lower the dispersion of the scatter gained from MFD is, the more accurate the MFD model can be built; furthermore, when the MFD model is applied to traffic route guidance, the error caused by data aggregating is much smaller and the guidance effect is better. Therefore, the ‘homogeneity’ of road network is a principle need considering when conduct the traffic guidance sub-region division based on MFD. However, MFD is also the macroscopic property of road network; moreover, in order to facilitate the development and implementation of traffic guidance strategy, it also need cooperating with other principles. The principles of traffic guidance sub-region division based on MFD are as follow:
1.
The guidance sub-region has ‘homogeneity.’ This is the prerequisite of MFD stably existence and its good performance, and the basic of applying MFD model into traffic guidance.

2.
The guidance sub-region must have a certain scale. MFD reflects the macroscopic characteristics of road network, and it shows the result of aggregate and statistical regularity generated from the traffic parameters of a certain number of road sections. Thus, guidance sub-region division must ensure that the sub-region has a certain size of space.

3.
The number of guidance sub-region must be reasonable and determined through considering the actual traffic condition and guidance objectives. Central traffic guidance in upper-level route guidance of bi-level path guidance strategy proposed by the paper is that abstract guidance sub-region into road section and carry out system optimum dynamic traffic assignment by using sub-region as elementary unit. If the number of sub-region is too much, then the operation efficiency is reduced. If the number of sub-region is too little, it is hard to promote the operation efficiency of the whole road network.

4.
The guidance sub-region must have internal connections and external connections between adjacent sub-regions. It is aimed to provide travelers who pass within the sub-region or pass through multiple sub-regions a complete and connected path from the perspective of guidance path generating.

After analyzing above principles, it is easy to find that the less road sections in each sub-region is, the more easily the sub-region is in the ‘homogeneous’ state; nevertheless, that leads to much smaller scale of the sub-region, which is inconsistent with the second principle mentioned above; moreover, the number of sub-regions will get too much after this division way, which does not match the third principle. In addition, it can easily lead to internal disconnections of sub-regions and external disconnections among adjacent sub-regions, which is incompatible with the fourth principle. However, the second, third, and fourth principle are the essential requirement for the stably existence of MFD and that MFD model can be applied to traffic guidance and gain better effects. Therefore, when dividing the sub-region based on MFD, it must ensure that the principle 1 is satisfied as far as possible on the basis of not breaking the principle 2, 3, 4.

### 2.2 Bi-level path guidance strategy

#### 2.2.1 Main idea of bi-level path guidance strategy

Suppose that the urban road network is divided into nine rectangular guidance sub-region, as shown in Fig. 1. Ensure the relative homogeneity of traffic flow density among each guidance sub-region which has stable MFD property.
According to bi-level route guidance strategy of this paper, at some point, conduct the route guidance to the traveler whose starting point is the red pentagram position and destination is the blue pentagram position shown in Fig. 1. In upper-level path guidance, central end needs to confirm the guidance path of guidance sub-region level. For instance, at the moment, central end can lead the traveler move along the sub-region 1 → 2 → 3 → 6 → 9 or 1 → 4 → 7 → 8 → 9 or 1 → 2 → 5 → 8 → 9 to finish this journey, which the route has been shown in Fig. 1 using three different colors. In such a situation, central end obtains the macroscopic traffic state of each guidance sub-region based on MFD theory, which abstracts the sub-region as road section to build the function relationship between road impedance and traffic flow. Conduct the dynamic traffic assignment of guidance sub-region level optimally based on system optimum and send the guidance path of sub-region level to vehicle terminal. Suppose that the travel sequence of guidance sub-region is 1 → 2 → 5 → 8 → 9.
In lower-level route guidance, vehicle terminal receives the guidance path of sub-region level (1 → 2 → 5 → 8 → 9) sent by the central end, and only in region 1, region 2, region 5, region 8, region 9, which this path passes. According to the real-time information of traffic condition, conduct vehicle route optimization based on user optimum, and suppose that the final generating path is that the red arrow shows in Fig. 2.
This strategy considers the will of both transport manager and traveler; it is the combination of central guidance and distributed guidance, and the compromise of system optimum and user optimum.
Consider two extreme cases, that is, the maximum and minimum number of guidance sub-region generated by urban road network division:
1.
The number of guidance sub-region is maximum: it means that each road section is divided into a guidance sub-region; at this point, the number of guidance sub-region is equal is the number of total road sections of the road network, which is the most ‘homogeneity’ situation of the guidance sub-region. Under this circumstance, the central end conducts system optimum dynamic traffic assignment of every guidance sub-region, namely each section is assigned in proportion; at this point, bi-level route guidance is equal to central guidance based on system optimum.

2.
The number of guidance sub-region is minimum: that is, the whole road network is a single guidance sub-region; at this point, the number of guidance sub-region is 1. In this situation, guidance path of guidance sub-region level which the vehicle terminal received only contains one guidance sub-region; in addition, it contains all sections of the road network, and it is easy to understand that, at this point, bi-level route guidance degenerates into distributed guidance based on user optimum.

Consequently, controlling the number of guidance sub-region reasonably based on actual traffic condition and need can effectively adjust the effect of bi-level route guidance.

#### 2.2.2 Upper-level path guidance based on system optimum

Suppose that the urban road network is divided into K guidance sub-regions, k = {1, 2, ⋯K}, each guidance sub-region has relative homogeneity of traffic flow density and stable MFD features.
Upper-level path guidance is to carry out dynamic traffic assignment of guidance sub-region based on system optimum, which is different from the traditional link and node oriented dynamic traffic assignment; it needs to abstract sub-region into road section and the boundary of adjacent guidance sub-regions is abstracted as node, and re-build the function relationship between the road impedance function and flow variation, yet the non negative constrains, initial conditions are similar to those in traditional dynamic traffic assignment; only the object turns from road section to guidance sub-region.
First, define the following symbolic variables:
Nk(t)—time t, the number of vehicles running in the guidance sub-region k, unit is veh;
Pk(Nk(t))—operating capacity of guidance sub-region k at time t, the value is the operating vehicle mileage of guidance sub-region k per unit time, unit is veh ⋅ m/s;
Vk(t)—at time t, the average operating speed of guidance sub-region k, unit is m/s;
Mk(t)—at time t, travel completion rate of guidance sub-region k, unit is veh/s, it is defined as the vehicle outflow of sub-region k per unit time; it is worth noting that it includes the number of vehicles of both arrive in and leave from this region;
Lk—the average travel distance of guidance sub-region k, unit is m. Once the guidance sub-region division is determined, it is a fixed value;
Tk(t)—at time t, reactionary average travel time of guidance sub-region k, unit is s.
Through the above definition, according to MFD theory, there are:
$${V}_k(t)={P}_k\left({N}_k(t)\right)/{N}_k(t)$$
(6)
$${M}_k(t)={P}_k\left({N}_k(t)\right)/{L}_k$$
(7)
$${T}_k(t)={L}_k/{V}_k(t)={L}_k\cdot {N}_k(t)/{P}_k\left({N}_k(t)\right)$$
(8)
Tk(t) is a function of Nk(t), which can be considered as road impedance function of guidance sub-region k.
Define $${N}_{rs}^{pk}(t)$$ representing the number of vehicles operating in the guidance sub-region k at time t whose origin and destination are sub-region r and sub-region s respectively and travel route is path p. Here, p is a sequence of guidance sub-regions which consist of a series of guidance sub-regions that from starting sub-region r to final sub-region s; obviously, guidance sub-region k belongs to route sequence p, then there are:
$${\sum}_r{\sum}_s{\sum}_p{N}_{rs}^{pk}(t)={N}_k(t)$$
(9)
Define $${M}_{rs}^{pk}(t)$$ representing the completion rate of the vehicles at time t in the guidance sub-region k whose origin and destination are sub-region r and sub-region s respectively and travel route is path p, then there are:
$${M}_{rs}^{pk}(t)=\frac{N_{rs}^{pk}(t)}{N_k(t)}\cdot {M}_k(t)=\frac{P_k\left({N}_k(t)\right)}{N_k(t)}\cdot \frac{N_{rs}^{pk}(t)}{L_k}={V}_k(t)\cdot \frac{N_{rs}^{pk}(t)}{L_k}$$
(10)
Define Qrs(t) representing the traffic demand generated at time t which starts at sub-region r and ending at sub-region s; $${Q}_{rs}^p(t)$$ represents the travel demand assigned to the path p, then there are:
$${\sum}_p{Q}_{rs}^p(t)={Q}_{rs}(t)$$
(11)
Define p+(k) representing the sub-region next to sub region k in the route sequence p.
Define p+(k) representing the sub-region closely after the sub-region k on the route sequence p, and p _ (k) representing the sub-region closely before the sub-region k on the route sequence p.
$${M}_{rs}^{k\to {p}_{+}(k)}(t)$$ represents the diverted traffic volume from sub-region k to sub-region p+(k). Traffic volume variation function relationship is shown in the equation below. (In order to simply express the formula, time t is omitted):
$$\frac{dN_{rs}^{pk}}{dt}=\left\{\begin{array}{l}{Q}_{rs}^p-{M}_{rs}^{pk}\kern2em k=r\ \mathrm{and}\ k=s\\ {}{Q}_{rs}^p-{M}_{rs}^{k\to {p}_{+}(k)}\kern1.62em k=r\ \mathrm{and}\ k\ne s\\ {}{M}_{rs}^{p_{-}(k)\to k}-{M}_{rs}^{pk}\kern1.5em k\ne r\ \mathrm{and}\ k=s\\ {}{M}_{rs}^{p_{-}(k)\to k}-{M}_{rs}^{k\to {p}_{+}(k)}\kern1.12em \mathrm{else}\end{array}\right.$$
(12)
Dynamic system optimal state requires equal and minimum marginal travel time $${\tau}_{rs}^p(t)$$ in all optional paths; therefore, the vehicle can be assigned to a path with minimal time-varying marginal cost. Identify those paths through calculating the marginal travel time of guidance sub-region τk(t) and applying the algorithm of solving dynamic minimal path. The marginal travel time of guidance sub-region k can be calculated from the equation below (In order to simply express the formula, time t is omitted):
$${\displaystyle \begin{array}{l}{\tau}_k={T}_k+{N}_k\cdot \frac{\mathrm{d}{T}_k}{\mathrm{d}{N}_k}=\frac{L_k\cdot {N}_k}{P_k\left({N}_k\right)}+{N}_k\cdot \frac{\mathrm{d}}{\mathrm{d}{N}_k}\frac{L_k\cdot {N}_k}{P_k\left({N}_k\right)}\\ {}\kern1.1em ={L}_k\cdot {N}_k\left(\frac{2}{P_k\left({N}_k\right)}-{N}_k\cdot \frac{\mathrm{d}{P}_k\left({N}_k\right)/\mathrm{d}{N}_k}{{\left[{P}_k\left({N}_k\right)\right]}^2}\right)\end{array}}$$
(13)
Through above process and calculation, upper-level route guidance—system optimal dynamic traffic assignment problem based on guidance sub-region can be abstracted into traditional system optimal dynamic traffic assignment problem based on links and nodes to describe and solve. Method of successive averages (MSA) is a kind of common heuristic algorithm which is suitable for solving the problem of balanced traffic flow assignment. MSA algorithm is applied in this paper to obtain the solutions to dynamic traffic assignment problem of upper-level path guidance.

#### 2.2.3 Lower-level path guidance based on user optimum

Lower-level path guidance is that under the premise of fully accepting the instructions of upper-level path guidance, within the range of guidance path of sub-region level generated from upper-level path guidance, vehicle path optimization based on user optimum is achieved through solving the optimal (short) path problem of time-varying road network.
For the classic algorithms of dynamic shortest route, including Dijkstra algorithm, A algorithm, Floyd algorithm, etc., as long as the time-varying road network meet the first-in-first-out constraint (FIFO) features, it can be used to solve the dynamic optimal path problem. The research priority of this paper is the bi-level path guidance strategy not the user optimal path solving algorithm itself, hence, the commonly used A algorithm is chosen in the paper. This algorithm has higher calculative efficiency comparing with Dijkstra algorithm.
A algorithm is a heuristic search algorithm; it is not to treat all nodes equally but only choose those nodes which have the greatest probability, until the target nodes are found. Therefore, comparing with Dijkstra algorithm, it reduces the number of nodes required for searching, and promotes calculative efficiency.
Note that vehicle path optimization in lower-level route guidance is realized on the basis of upper-level path guidance of sub-region level. Searching of links and nodes is only carried out in the specific guidance sub-regions; in other words, only the sub-regions on the sequence identified by upper-level route guidance are passed. In this situation, the road sections outside the defined range of the sub-regions are regarded as disconnection, and the travel time is considered as infinite, and the intersection nodes outside the range are not extended. Under such limitation condition, the above-mentioned A algorithm is applied to achieve the optimization of vehicle path in lower-level route guidance.

## 3 Results and discussion

The study designs a simulation experiment by use of ArcGIS and Paramics software, which chooses local road network of Changchun city. The division of sub-region is shown in Fig. 3.
By importing traffic demand files and OD matrix and loading different flow to simulate traffic demand of different time, and replace and modify the original core model of dynamic traffic assignment through API interface to simulate the dynamic traffic assignment based on system optimum, user optimum and bi-level path guidance strategy of this paper, and make the comparative analysis of simulation results. Simulation time is set to 2 h, sampling period is 300 s.
ArcGIS is used for road network building and data storage, and it achieves the function of path searching via secondary development. Load the traffic information generated by the paramics simulation on ArcGIS, which can be used as the base data for the path searching.
Under the bi-level path guidance strategy, network operating vehicle variation with time in each guidance sub-region is shown in Fig. 4.
Take sub-region 1 as an example, where MFD of local road network is drawn and shown in Fig. 5. As can be seen from Fig. 5, under three different path guidance, with the increase of road network congestion, the operation capacity of road network shows a downward trend, and the decline scope is different: under system optimal condition, the decreasing amplitude is not obvious; and under bi-level path guidance condition, there is a slight drop; however, under user optimal condition, the operation capacity of road network has a significant decline. It demonstrates that bi-level route guidance strategy can well adjust the number of operation vehicles in guidance sub-region and ensure that the operation capacity of road network keeps at a relatively high level.
Total delay of road network under different traffic guidance is used for comparative analysis, and the results are shown in Table 1.
Table 1
Total delay of road network (107(veh·s))

0.3
0.4
0.5
0.6
0.7
User optimum
0.35
1.02
2.29
3.14
4.38
System optimum
0.34 (2.9%)
0.93 (8.8%)
1.97 (14.0%)
2.65 (15.6%)
3.58 (18.3%)
Bi-level route guidance
0.35 (0)
0.99 (2.9%)
2.10 (8.3%)
2.73 (13.1%)
3.81 (13.0%)
It can be seen from Table 1 that the total delay of road network under bi-level path guidance strategy is lower than that under user optimal condition, yet higher than that under system optimal condition. Those discrepancies are related to the congestion state of road network; the more serious the congestion state is, the more the discrepancy between bi-level path guidance and user optimum mode is; on the contrary, the smoother the road network is, the lesser the discrepancy between bi-level path guidance and user optimum mode is. This fully shows that the bi-level path guidance proposed in this paper is the compromise situation between user optimum and system optimum.
Table 2 shows that the efficiency of guidance path generation under bi-level route guidance is higher than that in overall path searching algorithm. Therefore, it is fully proved that bi-level path guidance of this paper can effectively promote real-time capacity of dynamic traffic guidance.
Table 2
Performance of different path searching algorithm

Failure rate of path searching
Average time of path searching (s)
Minimum time of path searching (s)
Maximum time of path searching (s)
Node number
Overall path searching
2/1000
2.67
0.80
7.22
68
Algorithm of this paper
7/1000
1.68
0.42
4.59
36
Load the traffic state information from paramics simulation into ArcGIS, and generate guidance paths of the same OD at various departure times under different traffic guidance, as shown in Fig. 6 and detailed results are shown in Table 3.
Table 3
The results of different guidance path generation
Departure time (s)
Guidance mode
Actual travel time (min)
Travel distance (km)
Guidance path (indicated by path number in Fig. 6)
3500
Distributed guidance
54
3.2
Path 2
Central guidance
42
4.2
Path 3
Bi-level guidance
47
4.2
Path 3
2200
Distributed guidance
30
3.3
Path 1
Central guidance
35
4.2
Path 3
Bi-level guidance
32
3.3
Path 1
5000
Distributed guidance
13
3.2
Path 2
Central guidance
14
3.2
Path 2
Bi-level guidance
14
3.2
Path 2
As can be seen from Table 3, different time, road network under different flow distribution state, the guidance paths generated from different traffic guidance mode are not the same. It can be found that bi-level route guidance does not excessively sacrifice benefits of individual traveler and do reduce the journey time that traveler needs under heavy traffic congestion state, from making comparison between the actual travel time and journey distance of individual traveler. Through the simulation analysis, it is found that the traffic guidance strategy proposed in this paper can not only improve the benefit of the whole traffic system but also improve the individual travel benefit of travelers.
There are some shortcomings in the research of this paper. In the dynamic division of guidance sub-region based on MFD, only the road physical properties and signal control parameters of road network are considered in the initial division. In the bi-level route guidance method based on MFD, the average travel distance of the guidance sub-region is only a simple determination of the size of the sub-region and the relative position of the sub-region, and there is no actual investigation of the travel rule and characteristics of the sub-region traveler. It is hoped that the improvement of these shortcomings will promote the in-depth study and application of related theories, and provide valuable directions for further research.

## 4 Conclusions

This research proposes a bi-level path guidance strategy of urban road networks; it considers the intentions of traffic administration and travelers, which is a combination of central and distributed route guidance and a compromise of system optimum and user optimum. Traffic dynamic evolution model of route guidance sub-region based on MFD is constructed and system optimal dynamic traffic assignment method on traffic guidance sub-region level is proposed in upper-level route guidance. In lower-level route guidance, the traffic guidance paths are generated by solving the optimal path problem of the reactive users. Through analysis of actual examples, the method not only can meet the real-time requirements of dynamic traffic guidance but also provides benefits for the whole traffic system and individual traveler.

## Acknowledgments

Not applicable.

Not applicable.

Not applicable.

### Competing interests

The authors declare that they have no competing interests.

### Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Unsere Produktempfehlungen

### Premium-Abo der Gesellschaft für Informatik

Sie erhalten uneingeschränkten Vollzugriff auf alle acht Fachgebiete von Springer Professional und damit auf über 45.000 Fachbücher und ca. 300 Fachzeitschriften.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Maschinenbau + Werkstoffe​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Weitere Produktempfehlungen anzeigen
Literatur
Über diesen Artikel

Zur Ausgabe