J. Cent. South Univ. Technol. (2009) 16: 0172-0176

DOI: 10.1007/s11771-009-0029-z

Bi-level programming model for reconstruction of urban branch road network

SHI Feng(史 峰)¹, HUANG En-hou(黄恩厚)^{1, 2}, CHEN Qun(陈 群)¹, WANG Ying-zi(王英姿)³

(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;

2. Planning Bureau of Nanning City, Nanning 530004, China;

3. College of Civil Engineering, Hunan University, Changsha 410082, China)

Abstract: Considering the decision-making variables of the capacities of branch roads and the optimization targets of lowering the saturation of arterial roads and the reconstruction expense of branch roads, the bi-level programming model for reconstructing the branch roads was set up. The upper level model was for determining the enlarged capacities of the branch roads, and the lower level model was for calculating the flows of road sections via the user equilibrium traffic assignment method. The genetic algorithm for solving the bi-level model was designed to obtain the reconstruction capacities of the branch roads. The results show that by the bi-level model and its algorithm, the optimum scheme of urban branch roads reconstruction can be gained, which reduces the saturation of arterial roads apparently, and alleviates traffic congestion. In the data analysis the arterial saturation decreases from 1.100 to 0.996, which verifies the micro-circulation transportation’s function of urban branch road network.

Key words: branch road; reconstruction; bi-level programming model; micro-circulation traffic

1 Introduction

Nowadays, traffic jams have become increasingly pressing in many large cities. Confronting with traffic congestion, planning departments always try to plan more roads and widen the road. However, these measures cannot solve traffic problem, since the speed of road construction is always lower than that of traffic demand increase [1-3]. Comparatively, lots of branch roads are left unused while arterial roads are heavily congested [4-5]. The reasonable figuration of urban road network frame should be in the form of pyramid with expressway, arterial road, sub-arterial road, and branch road [6-8]. Recently, the concept of “micro-circulation transportation system” has been proposed and implemented in several large cities such as Beijing, Kunming, and Shenzhen [9-10]. “Micro-circulation transportation system” focuses on the capillary function of branch road network throughout urban traffic system, which can alleviate the traffic pressure of arterial roads, bring about a rational form of urban traffic network, and improve the loaded capacity of the whole road network. It also emphasizes to reconstruct the branch roads and enlarge their capacity, which are densely distributed but not utterly utilized owning to various restrictions (road condition, environment, and historical heritage preservations). Hence, using this system can share a part of traffic flow and solve traffic congestion.

Micro-circulation transportation system is to design the road network. TAM and WILLIAM [11], LAMMER et al [12], and FENG et al [13] studied the characteristics and functions of web road system, the total increase of traffic capacity, as well as the flexibility in variable traffic conditions. ZHAO [14], and WANG and ZHAO [15] analyzed the defects of wide streets and sparse road network in China. However, these existing researches lacked theories and methods for reconstructing and optimizing the micro-circulation branch network. In the process of reconstructing urban branch road network and enlarging its capacity, there is a need to take account of the practical traffic demands in order to relieve traffic jams, obtain minimum cost, and make reasonable plans and reconstruction. Aiming at the reconstruction of urban branch road network, a bi-level programming model was established and an optimum method was put forward.

2 Reconstruction of urban branch road net- work

2.1 Problem of branch road network’s reconstruction

Urban districts surrounding arterial roads are divided into several sub-districts. Around these sub-districts there are some branch roads (or embryonic form of branch roads). When one reconstructs branch roads and combines them with peripheral arterial roads to form a network within a certain district composed of several sub-districts, on one hand the traffic fluency towards outside regions can be improved, on the other hand, traffic flow of arterial roads can be distributed to some extent and traffic pressure in arterial roads can be reduced.

However, not all the embryonic form of branch roads can be converted into branch roads with reconstruction. For example, due to road reconstruction, the important cultural heritage can be damaged, the conflicts between pedestrians and vehicles become more serious in certain crowded regions such as commercial districts, and important official and educational places can be affected. For the branch roads that have been reconstructed, the fluency of branch roads should be concerned when traffic operation is organized; the traffic flow entering into branch roads should be restricted, especially when there are traffic jams in arterial roads. Lots of vehicles want to enter the branch road network to avoid traffic congestion. However, if branch roads become congested, it will be more difficult to relieve the congestion in branch roads than to relieve that in arterial roads. Additionally, changing some narrow roads into one-way street can be another method to solve the problem.

In the process of reconstructing branch roads, firstly some optional branch roads should e chosen as possible reconstructed object set; then the engineering budget of each traffic capacity grade of branch roads should be planned; finally considering multi-objects such as alleviating traffic congestion and reducing reconstruction costs, parts of branch roads to be reconstructed can be from the optional branch roads’ set.

2.2 Optimal object of reconstruction of branch road network

Reconstructing urban branch road network can involve various optimal objects such as traffic flow’s assignment and engineering costs, and the detailed analyses are as follows.

(1) There is a slight drop in the saturation degree of arterial road network. Because the function of “micro-circulation transportation system” is to solve or alleviate the traffic pressure of arterial roads, one of the objects is to plan reconstructed road network that may lead to lower the saturation and the traffic burden of arterial roads to some extent. Apparently, the arterial roads’ saturation decreases slightly, or else traffic capacity of arterial roads cannot be fully used.

(2) The costs of reconstruction should be as lowest as possible. Besides the engineering cost, the reconstructing costs are composed of other expenses of cultural and environmental preservation. The engineering cost depends on the length and range of the reconstructed roads (Reconstructed range can be denoted by the improved amount of traffic capacity, and the wider range the reconstruction, the higher the reconstruction can cost and the larger capacity the reconstructed roads). The engineering cost is expected to reduce to the lowest on the premise of satisfying the traffic demands as much as possible.

3 Bi-level programming optimal model

Consider the road network of a certain district N=(V, A∪B), where V is the set of all nodes, denoted as n=|V|. A is the set of arterial roads, and B is the set of optional branch roads. The traffic demand of origin-destination (OD) pair is (q_rs)_n×n, where q_rs is the flow from node to node s. Before roads are reconstructed, the capacity is C(a), aA∪B, and then the reconstructed capacity is X(a), aB. Apparently, X(a)≥C(a), aB.

Generally, the average price per length of the road section a, of which the capacity increases from C(a) to X(a), is represented as follows:

p(a)=Z_a(C(a), X(a)), aB

In the above unit cost function p(a), when X(a)=C(a), the road section will not be reconstructed, so the cost is zero; and when X(a)＞C(a), the reconstruction cost includes the expense of road reconstruction, the environmental and cultural protection cost, etc.

Hence, the price of the road section a for its increased capacity from C(a) to X(a) is

l(a)p(a)=l(a)Z_a(C(a), X(a)), aB

where  l(a) is the length of the road section a. Therefore, an optimal target of the cost of branch road network’s reconstruction is put forward, that is

In order to evaluate the flow redistribution of arterial roads because of reconstructing the branch roads, the maximum saturation U(a) (aA) of the arterial road section is introduced, and the saturation u(a) is required to be less than the maximum saturation U(a), that is

≤U(a), aA

where  x(a) is the flow of road section a (aA). Because the reconstruction potentiality of the branch roads network is not infinite, the arterial roads saturation cannot be required to decrease to a certain designated level absolutely. So the above inequality can not become a hardy constraint which can only be an optimal object, that is

The reconstruction capacity X(a) (aB) of branch road section must be less than the maximum reconstruction capacity X₀(a) and more than the lowest limit capacity C(a), which is formulated as

C(a)≤X(a)≤X₀(a), aB

In order to avoid the emergency that may result in the branch road congestion, the maximum saturation V(a) of section aB is imported, and the saturation v(a) is less than the maximum saturation V(a), that is

≤V(a), aB

where  x(a) is the flow of road section a (aB). Therefore, the restricted condition of branch road section flow is

x(a)≤V(a)X(a), aB

The above conditions can be realized by restricting the entrance flows into the branch road section in the traffic organization.

If the branch road section capacity and the maximum saturation are given, the road section flow can be obtained from the user equilibrium traffic assignment.

In summary, branch road network’s reconstruction can be described by a multi-objects bi-level programming. The optimal target of the upper level is to minimize the reconstruction cost, satisfying the maximum saturation of arterial roads as much as possible. The reconstructed capacity of branch road sections should satisfy the upper and lower limit. At the time, the user equilibrium rule should be satisfied by the restriction of each section flow under the arterial section capacity, the branch section capacity and the branch section saturation, that is, the lower level. It can be seen that the decision-making variable of the upper level is the reconstruction capacity of branch road section, and that of the lower level is the road section flow. The bi-level programming of branch road reconstruction problem can be described as follows:

The upper level programming is

s.t.   C(a)≤X(a)≤X₀(a), aB

where  all x(a), aA∪B satisfy the lower level programming:

≥0, r, s=1, 2, …, n; k=1, 2, …, L(r, s)

In the above programming, L(r, s) is the path number in OD pair (r, s),  is the traffic flow of the kth path in OD pair (r, s),  equals 1 if the road section a is on the kth path in OD pair (r, s), otherwise  equals 0. t_a(x(a)) is the road impedance function developed by BPR(Bureau of Public Road ), which is

where  t_a0 is the travel time of the road section a on free flow, α and β are the parameters, and usually, α=0.15, β=4.

The restriction of capacity and the saturation of the above branch road sections are embodied by the BPR, that is to say, there is no strict capacity restraint besides the road impedance. The capacity restrict can be added to the lower level programming, which can seriously restrict the flow of the branch road if necessary.

4 Genetic algorithm

In view of the complexity of bi-level programming, the genetic algorithm designed for the model is shown as follows.

X=(X(a), aB) is obtained by coding the branch road section capacity. The double object functions are transformed into a single object function by using the equivalent factor (ξ), that is

The object function upper limit is denoted as Z_max, and the fitness function is constructed as F(X)=Z_max-Z(X). The genetic algorithm of the branch road network’s reconstruction is shown as follows.

Algorithm 1 Genetic algorithm of branch road network’s reconstruction

Input road network N=(V, A∪B), traffic demand (q_rs)_n×n, capacity C(a), road section length l(a), aA∪B, unit cost Z_a(C(a), X(a)), aB, saturation of the branch road section V(a), aB, and saturation of the arterial road section U(a), aA.

Output reconstruction capacity X(a), a∈B, road section flow x(a), aA∪B, saturation of the branch road section v(a), aB, saturation of the arterial road section u(a), aA, and total reconstructing cost of branch road network.

Begin

The initial colony is produced at random on the condition of C(a)≤X(a)≤X₀(a), aB.

Do while()

For each individual X=(X(a), aB), with the restriction of the capacity C(a), aA and V(a)X(a), aB, the road section flow x(a), aA∪B is obtained by carrying out the user equilibrium assignment with the Frank-Wolf algorithm or the direction search method.

Calculate the individual object function and the fitness degree by using X(a), aB and x(a), aA∪B.

Construct the next colony by using selection, exchange, variation and copy.

Whether the algorithm is terminated or not is based on the genetic generation and the update frequency of the object function.

Return

End

5 Numerical example

Road network N=(V, A∪B) is shown in Fig.1. Numerals denote nodes, the thick lines denote arterial roads and the thin lines denote the optional branch roads. The traffic demands q₁₄=1 500 veh/h, q₂₃=3 000 veh/h. The average artery capacity is 2 000 veh/h, the capacity of each optional branch road is 400 veh/h. Each road section length is 1 km. The reconstruction cost function of branch roads per length is shown as follows:

×10³ yuan/km

Fig.1 Network structure of artery and micro-circulation road

The anticipant saturation of artery is less than 1, and that of the branch road is less than 0.8. After being reconstructed, the upper limit of the branch road capacity is 800 veh/h. The travel time of free flow on artery is 1 min, and the travel time function of branch road is shown as follows:

The problems to solve are which branch road should be reconstructed and how big their capacities should be after being reconstructed.

Let the equivalent factor ξ=0.5, population size is 300, cross rate is 0.7, variation rate is 0.1, and iteration number is 30. The programming of Algorithm 1 was implemented with MATLAB6.5. The calculating curve is shown in Fig.2. Table 1 lists the flow and saturation on artery.

Fig.2 Variation curves of fitness with evolution generation

Table 1 Flow and saturation on artery

The traffic capacity, flow and saturation of the reconstructed branch roads are listed in Table 2.

Table 2 Traffic capacity, flow and saturation on reconstructed branch roads

According to Tables 1 and 2, the saturation on arterial roads drops to 0.996, and the saturation on branch roads is less than 0.778. It also shows that there is no need to enlarge capacity of branch road section (8, 9) when its flow is 0. There is only single direction flow on branch road sections (5, 8), (8, 11), (6, 9), so they can be organized as one way street, while section (9, 12) can keep the current situation.

Without the branch road network, while other conditions and the traffic demand OD remains constant, the bi-direction flows of arterial road sections (1, 2) and (3, 4) are 1 489, 729 and 771, 1 510 veh/h, respectively, the saturations are 74.5%, 36.5% and 38.5%, 75.5%, respectively, the flows of arteries (1, 3) and (2, 4) with one-way flow are 2 260 veh/h and 2 239 veh/h and the saturations are 113.0% and 112.0%, respectively.

The above results indicate that the arteries are in a supersaturated state without branch road network (saturations of arteries (1, 3) and (2, 4) exceed 1), and congestion will appear at any time. After being reconstructed, branch road network takes the function of “micro-circulation transportation” with alleviating the congestion on artery and utilizing the capacity of current branch road. Through the alleviation of micro-circulation branch road network, the saturation of artery is less than 1, which shows that branch road reconstruction can reduce the saturation of arterial road apparently and verifies the function of “micro-circulation transportation” of branch road network.

6 Conclusions

(1) With the advantages to actualize the appropriate grade proportion of urban transportation network, alleviate the congestion of the artery and heighten the overall efficiency of the road network, programming of urban micro-circulation transportation system of branch roads is a strategy to solve urban traffic problem.

(2) According to the function of “micro-circulation transportation” of branch road network and alleviation of traffic demand of urban artery, bi-level optimum model for the branch road network programming is established, and combined with the objection of minimum cost and traffic assignment method. This model is able to determine the branch road that can be reconstructed and what corresponding traffic capacity.

(3) Compared with examples of pre-and post traffic conditions of arterial road, the function of “micro- circulation transportation” of branch road network is verified.

(4) Although the bi-level programming depicts the designing problem of the branch road network well in the urban micro-circulation transportation system, the actual application must be verified and extended.

References

[1] DOWNS A. Smart growth: Why we discuss it than we do it [J]. Journal of the American Planning Association, 2005, 71(4): 367-378.

[2] YANG Hai, MENG Qiang. Highway pricing and capacity choice in a road network under a build-operate-transfer scheme [J]. Transportation Research, Part A: Policy and Practice, 2000, 34(3): 207-222.

[3] WANG Yan, LIU Wei-ming, LI Yun-hui. Research on relationships between road infrastructure and traffic demand based on granger causality test [J]. Science Technology and Engineering, 2008, 8(4): 1723-1726.

[4] LIN S C. The ecologically ideal road density for small islands: The case of Kinmen [J]. Ecological Engineering, 2006, 27(2): 84-92.

[5] WANG Jian-jun, WANG Ji-ping, PENG Zhi-qun. Discussion of appropriate grade proportion of urban road network [J]. Urban Transport of China, 2005, 3(1): 37-42. (in Chinese)

[6] RADNOR J P, NORMAN J A, PAUL H W. Transportation engineering planning and design [M]. Singapore: John Wiley & Sons Inc., 1982.

[7] WAYNE K T. Introduction to transportation [M]. Santa Fe: South-western Publishing Company, 1983.

[8] CHEN Xue-wu, LIU Fei, HU Qi-zhou. Appropriate road grade model of road network in small city [J]. Journal of Traffic and Transportation Engineering, 2008, 8(1): 102-105. (in Chinese)

[9] LI De-hui, LIU Xiao-ming. Research on urban transportation micro-circulation [J]. Road Traffic and Safety, 2005, 5(4): 17-19.

[10] SHI Feng, HUANG En-hou, WANG Ying-zi. Study on the functional characteristics of urban transportation micro-circulation system [J]. Urban Studies, 2008, 15(3): 34-36. (in Chinese)

[11] TAM M L, WILLIAM H K. Balance of car ownership under user demand and road network supply conditions—Case study in Hong Kong [J]. Journal of Urban Planning and Development, 2004, 130(1): 24-36.

[12] LAMMER S, GEHLSEN B, HELBING D. Scaling laws in the spatial structure of urban road network [J]. Physica A: Statistical Mechanics and its Applications, 2006, 363(1): 89-95.

[13] FENG Shu-min, GAO He, GUO Cai-xiang. Evaluation of structural types of urban road network [J]. Journal of Harbin Institute of Technology, 2007, 39(10): 1610-1613. (in Chinese)

[14] ZHAO Yan-jing. From planning to market: The shift of the road-land use mode [J]. Planning Studies, 2002, 26(10): 24-30. (in Chinese)

[15] WANG Bo, ZHAO Feng. A study on the urban transportation strategies and planning modes of medium and small cities [J]. Road Traffic and Safety, 2005, 5(5): 18-21. (in Chinese)

Foundation item: Project(2006CB705507) supported by the National Basic Research and Development Program of China; Project(20060533036) supported by the Specialized Research Foundation for the Doctoral Program of Higher Education of China

Received date: 2008-12-06; Accepted date: 2008-12-19

Corresponding author: CHEN Qun, PhD; Tel: +86-13548679364; E-mail: chenqun631@mail.csu.edu.cn

(Edited by YANG You-ping)