Model for Microcirculation Transportation Network Design

Abstract

The idea of microcirculation transportation was proposed to shunt heavy traffic on arterial roads through branch roads. The optimization model for designing micro-circulation transportation network was developed to pick out branch roads as traffic-shunting channels and determine their required capacity, trying to minimize the total reconstruction expense and land occupancy subject to saturation and reconstruction space constraints, while accounting for the route choice behaviour of network users. Since micro-circulation transportation network design problem includes both discrete and continuous variables, a discretization method was developed to convert two groups of variables (discrete variables and continuous variables) into one group of new discrete variables, transforming the mixed network design problem into a new kind of discrete network design problem with multiple values. The genetic algorithm was proposed to solve the new discrete network design problem. Finally a numerical example demonstrated the efficiency of the model and algorithm.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Recommended by Wuhong Wang

School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China

Received 2 August 2012; Revised 8 November 2012; Accepted 21 November 2012

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Urban microcirculation transportation is an impersonate noun borrowed from human blood circulation system [ 1]. In the blood microcirculation system, blood flows from arterioles to microcirculation vessels and then flows from the microcirculation vessels back to venules. Similar to the blood microcirculation, traffic microcirculation can be defined as traffic flows from arterial roads to branch roads (microcirculation roads) and then flows from branch roads back to arterial roads. In general, most of vehicles run on the arterial roads, so arterial roads usually become very congested at peak hours. If microcirculation transportation network is designed around "jam points" of arterial roads, traffic on arterial roads can be shunted, and part of vehicles can go through the microcirculation roads (branch roads).

In reality, owing to narrow road surface and complicated functions, some branch roads are primarily for in-area traffic (e.g., pedestrian, bicycles, and few vehicles) [ 2, 3] and do not have the ability of shunting traffic of arterials. For the purpose of traffic shunting, the microcirculation road systems need to be designed. Some branch roads with good conditions need to be picked out for reconstruction. So, there are two problems to solve: one is to determine which branch roads are picked out as traffic-shunting channels; the other is to determine the required capacity of these selected roads after reconstruction. Microcirculation transportation presented an effective and economical way for reducing traffic congestions because it does not need to add new roads but utilizes the existing branch roads to shunt traffic. Recently, in China, some big cities like Beijing and Kunming have established the microcirculation transportation systems in some congested segments.

Microcirculation transportation network design problem belongs to the family of network design problems (NDPs). The NDP is normally formulated as a mathematical program with equilibrium constraints (MPEC) in which the planner aims to define modifications to a network so as to optimize an objective function, whilst considering the response of travellers to the changes following an equilibrium condition. Often, the travellers' responses are assumed to follow Wardrop's user equilibrium condition (deterministic UE). Typical models for the NDP under DUE have been developed by Tobin and Friesz [ 4], Yang et al. [ 5], and Chiou [ 6]. Users' route choice behaviour is also usually characterized by the stochastic user equilibrium (SUE) [ 7]. Davis [ 8] and Uchida et al. [ 9] extended the NDP under the DUE to the SUE case.

The NDP is usually classified into three categories: the discrete network design problem (DNDP), the continuous network design problem (CNDP), and the mixed network design problem (MNDP) that combines both CNDP and DNDP in a network. The DNDP deals with the selection of the optimal locations of new links to be added and is normally applied in the design of new road systems. Leblance [ 10], Chen and Alfa [ 11], Gao et al. [ 12], and Jeon et al. [ 13] researched DNDP and developed mathematical models and solution algorithms. The CNDP determines the optimal capacity enhancement for a subset of existing links and is especially suitable for the design of widening the existing roads. Abdulaal and LeBlanc [ 14], Friesz et al. [ 15], Meng et al. [ 16], Chiou [ 17], and Wang and Lo [ 18] researched CNDP and developed mathematical models and solution algorithms. Yang and Bell [ 19] provided a comprehensive review of the models and algorithms for the NDP, in which MNDP was mentioned. The MNDP is normally formulated as a nonlinear mixed integral bilevel programming problem that is very hard to solve. Luathep et al. [ 20] developed a mixed-integer linear programming approach for solving the MNDP.

Shi et al. [ 21] modelled one-way traffic organization in microcirculation transportation network. In addition, Shi et al. [ 22] presented a model for reconstruction of urban branch road, but it only considered the cost target and optimized improvements of all branch roads. In fact, the microcirculation network design is a two-stage problem: the first is to determine which branch roads are picked out as traffic-shunting channels (0-1 variables); the second is to determine the required capacity of these selected roads (continuous variables). Microcirculation transportation network design problem includes both 0-1 discrete variables and continuous variables, so it also can be considered as one of the MNDPs. But it is different from the previous MNDPs. The conventional MNDPs combine both DNDP and CNDP in a network; discrete variables (for new road links) and continuous variables (for modified road links) are independent and for respective problems. However, in the microcirculation transportation network design problem, it needs to firstly select road links to be reconstructed, and then the required capacity of these selected road links can be determined. So it is a two-stage planning problem, in which determination of discrete variables' values is prior to determination of continuous variables' values. It is more difficult to solve than the conventional MNDPs. This paper presented a discretization way to convert two groups of variables (discrete variables and continuous variables) into one group of new discrete variables, and then the MNDP is transformed into a new kind of DNDP. The new DNDP is different from the conventional 0-1 DNDP because the variable of the new DNDP can take multiple values. The genetic algorithm was proposed to solve the new DNDP.

Moreover, compared with the conventional NDPs, the microcirculation transportation network design problem has different objectives. Microcirculation transportation network is a little local network whose objective is to shunt traffic from arterial roads. Because the size of network is small, passing time of vehicles is very short if the network is not congested, so the factor of travel time may be ignored in the model which is usually taken into account by the conventional NDPs. The main objective of the microcirculation network design problem is to minimize the total reconstruction expense under a saturation constraint. Also, the objective of minimizing land occupancy is taken into account to minimize interference with in-area residents. In addition, microcirculation transportation network design problem considers some other constraints, such as reconstruction space constraint and restriction for the number of cross-points of microcirculation roads and arterial roads.

The remainder of the paper is organized as follows. Section 2presents the optimization model for designing the microcirculation transportation network. Section 3introduces a discretization way to solve the model. In Section 4, a numerical example is given to demonstrate the application of the model and algorithm. The final section concludes the paper.

2. Optimization Model for Designing Microcirculation Transportation Network

In Figure 1, road network N = ( V ,A ∪B ) , V is the set of all nodes, n = | V | . A is the set of arterial roads, and B is the set of candidate branch roads. ( _{q rs ) n ×n} is traffic distribution between origins and destinations. For branch road a (a ∈B ) , e (a ) equals 1 if it is selected and 0 if not selected. All the selected branch roads construct the microcirculation transportation network. The existing capacity of each road is C (a ) , a ∈A ∪B . For the selected branch road a (a ∈B ) , its required capacity after reconstruction is X (a ) , a ∈B . Apparently, X (a ) ...5;C (a ) , a ∈B . e (a ) , X (a ) , a ∈B are the optimization variables.

Figure 1: Arterial roads, candidate branch roads, and selected branch roads.

[figure omitted; refer to PDF]

In general, there are two road links with opposite directions between two adjacent nodes, and their capacities are usually the same.

Before reconstruction the branch roads do not have the ability of shunting traffic from arterial roads. They are for in-area traffic and often crowded with pedestrians and bicycles and even occupied by some other temporary facilities, and so would not have their original designed capacity unless they are cleaned up or reconstructed.

The main optimization objective is to minimize the total reconstruction cost which lies on the length and capacity of the reconstructed roads. If the capacity is improved more, the reconstruction expense will become more.

In addition, the objective of minimizing land occupancy (expressed as land use cost) should be taken into account to reduce interference with the area. Although microcirculation transportation can shunt arterials' traffic, the shunted traffic will interfere with residents' life inside the area and may cause environmental pollution. Reducing land occupancy (including road length and width) of microcirculation transportation can reduce interference scope. So, for those unselected branch roads, some management measures need to be taken to bar the traversing traffic, making traffic shunting restricted within the selected roads.

From the previous analysis, the cost function of candidate branch road a can be expressed as [figure omitted; refer to PDF]

In ( 2.1), item 1 of the right side is reconstruction expense and item 2 is land use cost of microcirculation transportation. The optimization goal is to minimize _{∑ a ∈B} P (a ) , namely: [figure omitted; refer to PDF]

l (a ) is the length of candidate branch road a , p (a ) is unit reconstruction expense, and h (a ) is unit land use cost: [figure omitted; refer to PDF]

In ( 2.3), for branch road a , p (a ) is an increasing function of X (a ) ; namely, the required capacity is greater, the reconstruction expense is higher: [figure omitted; refer to PDF]

Equation ( 2.4) implies that h (a ) is an increasing function of X (a ) , because land use of microcirculation roads depends on their length and width, while land use cost h (a ) of unit length is decided by the road width which corresponds with the capacity after reconstruction ( X (a ) ). In general, for branch road a , if the capacity X (a ) after reconstruction is greater, the road width should be greater, and so h (a ) becomes greater.

The constraints are as follows.

(1) Saturation constraint of arterial roads: since the function of the microcirculation transportation network is to shunt traffic from arterial roads, the first target is to make the saturation of arterial roads less than an allowed value. But the saturation of arterial roads should not be too small; otherwise, their capacity cannot be brought into full play. The key is to attain the goal of no more very congested: [figure omitted; refer to PDF] where u (a ) , x (a ) , a ∈A are, respectively, the saturation and flow of arterial road a and U (a ) is the allowed saturation of arterial road a .

(2) Saturation constraint of branch roads: the saturation of microcirculation branch roads should also be under an allowed value to avoid traffic congestions on branch roads and ensure the safety of pedestrians and bicycles on the branch roads: [figure omitted; refer to PDF] where v (a ) , x (a ) , a ∈B are, respectively, the saturation and flow of branch road a and V (a ) is the allowed saturation of branch road a .

(3) Capacity constraint of branch roads. Capacity enhancement of branch roads is affected by some actual conditions, such as land use restriction, building restriction and geological condition: [figure omitted; refer to PDF] where _{X 0} (a ) is the available maximal capacity of branch road a after reconstruction.

(4) Restriction for the number of cross-points of microcirculation and arterial roads : reducing the number of cross-points of microcirculation and arterial roads can reduce interference with arterial traffic. Microcirculation roads are for shunting arterial traffic and so generally have a relatively big traffic flow; signal controls normally need to be taken when they cross arterial roads. More signal-control intersections imply more of traffic delay on arterial roads (waiting time and the time needed for starting and braking of vehicles).

_{d i -j} denotes the number of cross-points of arterial road ( i -j ) and microcirculation roads. Suppose _{d i -j} should not exceed _{D i -j} (maximal allowed value): [figure omitted; refer to PDF]

x (a ) ,a ∈A ∪B is calculated via the user equilibrium (UE) traffic assignment model: [figure omitted; refer to PDF] s.t. [figure omitted; refer to PDF]

^{f k rs} is the flow of path k between origin-destination (OD) pair (r ,s ) , L (r ,s ) is the number of paths between OD pair (r ,s ) , and _{q rs} is traffic demand between OD pair (r ,s ) . x (a ) is the flow of link a . ^{δ a ,k rs} equals 1 if link a is on path k between OD pair (r ,s ) , otherwise 0. _{t a} is travel time on link a . Here BPR (bureau of public road) link impedance function is applied: [figure omitted; refer to PDF]

In ( 2.11), M (a ) is link capacity; for arterial roads, it is C (a ) ; for branch roads, it is X (a ) . α , β are parameters, and BPR suggested that α =0.15 , β =4 . _{t a0} is free-flow travel time of link a .

3. Solution Algorithms

There are two groups of variables ( e (a ) ,X (a ) ) in the above model, so the solution is very hard. But if the two groups of variables can be converted into one, then the solution will become much easier.

For branch road a ,a ∈B (the existing capacity C (a ) ), its capacity enhancement via reconstruction can be discretized if it is selected. Let capacity enhancements be 0, σ , 2 σ , 3 σ , 4 σ , ..., where σ denotes one added unit and 0 denotes that capacity enhancement is 0. This discretization way can accord with the real case. On the one hand, in reality, capacity enhancements via reconstruction are always discrete values instead of continuous; on the other hand, use of many discrete values is also able to reach the precision.

One group of new discrete variables ( λ (a ) ) can be defined to convert two groups of variables ( e (a ) ,X (a ) ) into one group of variables ( λ (a ) ): [figure omitted; refer to PDF]

λ (a ) , a ∈B is the optimization variable. If λ (a ) is calculated, e (a ) and X (a ) can be obtained.

The real coded genetic algorithm is applied to solve the optimization model. The chromosome is made up of λ ( 1 ) , λ ( 2 ) , λ ( 3 ) , ... .

Steps of solving the model using genetic algorithm are as follows.

Step 1.

Initialization: set population size ( E ), chromosome length ( J ), iteration number ( _{g max} ), probability of crossover ( _{P c} ), and probability of mutation ( _{P m} ).

Step 2.

Construct a fitness function: F (m ) = _{C max} -O (m ) , where F (m ) is the fitness of individual m , O (m ) is the function value of individual m and _{C max} is the estimated maximal function value. Randomly produce the initial population and set g =1 .

Step 3.

Calculate link flows via UE traffic assignment model, and then calculate the fitness and excess over constraints of each individual. If g = _{g max} , output the best individual; otherwise, turn to Step 4.

Step 4.

Use roulette wheel selection operator based on ranking [ 23] to select the population of next generation. Feasible solutions rank from high to low by fitness, and then infeasible solutions rank from small to much by excess over constraints.

Step 5.

According to probability of crossover ( _{P c} ), make multi-point crossover. Crossover points can be randomly selected without repeat. Variables between crossover points interchange alternately to produce two new individuals.

Step 6.

According to probability of mutation ( _{P m} ), make single point mutation. Randomly produce an integer between [-1 J ] ( J is the maximal value of λ (a ) ) to replace the current value of the variable. Set g =g +1 , and return to Step 3.

4. A Numerical Example

In Figure 2, the thick lines around the area denote arterial roads and the thin lines inside the area denote candidate branch roads. Each line includes two links with opposite directions and equal capacity. Traffic distribution during peak hours is in Table 1.

Table 1: Traffic distribution between OD Pairs (unit: veh/h).

Node	1	2	3	4
1	0	800	2600	800
2	800	0	1000	2200
3	2600	1000	0	1000
4	800	2200	1000	0

Figure 2: Original road network.

[figure omitted; refer to PDF]

The capacity of arterial road is 3000 (veh/h); the existing capacity of candidate branch road is 500 (veh/h). The length of each link is 1 km. Unit reconstruction cost function of branch roads is p (a ) = (X (a ) -500 ) × ^{10 4} ($/km); unit land use cost function is h (a ) = ( 1 / 4 )X (a ) × ^{10 4} ($/km). Road saturation should not exceed 1. The available maximal capacity of each branch road after reconstruction is 1000 (veh/h). _{t a0} of arterial roads is 1 min and that of branch roads is 1.1 min. _{d 1 -2} ...4;1 , _{d 1 -4} ...4;1 , _{d 3 -4} ...4;1 , _{d 2 -3} ...4;1 .

Let σ =100 ; the solution set of λ (a ) is { -1 ,0 ,1 ,2 ,3 ,4 ,5 } since the available maximal capacity is 1000 and the existing capacity is 500. The selected branch roads are shown in Figure 3; the total cost is 8000 × 10⁴ $. Saturations of arterial and branch roads are all less than 1. Flows and saturations of arterial roads are in Table 2; capacities, flows, and saturations of the selected branch roads for constructing the microcirculation network are in Table 3.

Table 2: Flows and saturations of arterial roads.

Link	Flow (veh/h)	Saturation (%)
1 [arrow right]7	2978	99.3
1 [arrow right]12	2959	98.6
2 [arrow right]5	2930	97.7
2 [arrow right]8	2993	99.8
3 [arrow right]13	2978	99.3
3 [arrow right]18	2998	99.9
4 [arrow right]17	2940	98.0
4 [arrow right]20	2936	97.9
5 [arrow right]2	2930	97.7
5 [arrow right]6	2930	97.7
6 [arrow right]5	2930	97.7
6 [arrow right]7	2978	99.3
7 [arrow right]1	2978	99.3
7 [arrow right]6	2978	99.3
8 [arrow right]2	2993	99.8
8 [arrow right]13	2978	99.3
12 [arrow right]1	2959	98.6
12 [arrow right]17	2940	98.0
13 [arrow right]3	2978	99.3
13 [arrow right]8	2978	99.3
17 [arrow right]4	2940	98.0
17 [arrow right]12	2940	98.0
18 [arrow right]3	2998	99.9
18 [arrow right]19	2936	97.9
19 [arrow right]18	2936	97.9
19 [arrow right]20	2936	97.9
20 [arrow right]4	2936	97.9
20 [arrow right]19	2936	97.9

Table 3: Capacities, flows, and saturations of the selected branch roads.

Link	Capacity (veh/h)	Flow (veh/h)	Saturation (%)
6 [arrow right]10	1000	714	71.4
8 [arrow right]9	800	620	77.5
9 [arrow right]8	800	620	77.5
9 [arrow right]10	700	374	53.4
9 [arrow right]14	700	323	46.1
10 [arrow right]6	1000	714	71.4
10 [arrow right]9	700	374	53.4
10 [arrow right]11	700	424	60.6
10 [arrow right]15	500	101	20.2
11 [arrow right]10	700	424	60.6
11 [arrow right]12	800	686	85.8
11 [arrow right]16	500	262	52.4
12 [arrow right]11	800	686	85.8
14 [arrow right]9	700	323	46.1
14 [arrow right]15	600	360	60.0
14 [arrow right]18	800	683	85.4
15 [arrow right]10	500	101	20.2
15 [arrow right]14	600	360	60.0
15 [arrow right]16	500	262	52.4
16 [arrow right]11	500	262	52.4
16 [arrow right]15	500	262	52.4
18 [arrow right]14	800	683	85.4

Figure 3: Microcirculation road network.

[figure omitted; refer to PDF]

Comparatively, if only arterial roads exist (without microcirculation road network), the saturation of arterial roads goes beyond 1 (Table 4).

Table 4: Saturations and flows.

Link	Flow (veh/h)	Saturation (%)
1 [arrow right]2	3278	109.3
1 [arrow right]4	3297	109.9
2 [arrow right]1	3278	109.3
2 [arrow right]3	3303	110.1
3 [arrow right]2	3303	110.1
3 [arrow right]4	3321	110.7
4 [arrow right]1	3297	109.9
4 [arrow right]3	3321	110.7

5. Conclusions

This paper defined the concept of urban microcirculation transportation. Microcirculation transportation network is a little local network and can shunt traffic from arterial roads. Through the microcirculation transportation network design model in this paper, the branch roads as traffic-shunting channels and their required capacity after reconstruction can be decided.

Since microcirculation transportation network design problem includes both discrete variables and continuous variables, this paper developed a discretization method to convert two groups of variables (discrete variables and continuous variables) into one group of new discrete variables, transforming the solution of MNDP into the solution of a new kind of DNDP with multiple values, and the genetic algorithm was proposed to solve the new DNDP.

A numerical example demonstrated the application of the model and algorithm and compared the results with or no microcirculation transportation network. The method and model proposed in this paper provided a new effective way for solving urban traffic congestions.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (Grant no. 50908235) and the Hunan Province Social Science Fund (Grant no. 12YBB274).

References

[1] F. Shi, E. H. Huang, Y. Z. Wang, "Study on the functional characteistics of Urban transrortation micro-circulation system," Urban Studies , vol. 15, no. 3, pp. 34-36, 2008.

[2] W. H. Wang, Q. Cao, K. Ikeuchi, H. Bubb, "Reliability and safety analysis methodology for identification of drivers' erroneous actions," International Journal of Automotive Technology , vol. 11, no. 6, pp. 873-881, 2010.

[3] W. H. Wang, H. W. Guo, K. Ikeuchi, H. Bubb, "Numerical simulation and analysis procedure for model-based digital driving dependability in intelligent transport system," KSCE Journal of Civil Engineering , vol. 15, no. 5, pp. 891-898, 2011.

[4] R. L. Tobin, T. L. Friesz, "Sensitivity analysis for equilibrium network flow," Transportation Science , vol. 22, no. 4, pp. 242-250, 1988.

[5] H. Yang, Q. Meng, M. G. H. Bell, "Simultaneous estimation of the origin-destination matrices and travel-cost coefficient for congested networks in a stochastic user equilibrium," Transportation Science , vol. 35, no. 2, pp. 107-123, 2001.

[6] S. W. Chiou, "TRANSYT derivatives for area traffic control optimisation with network equilibrium flows," Transportation Research B , vol. 37, no. 3, pp. 263-290, 2003.

[7] Y. Sheffi Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods , Prentice-Hall, Englewood Cliffs, NJ, USA, 1985.

[8] G. A. Davis, "Exact local solution of the continuous network design problem via stochastic user equilibrium assignment," Transportation Research B , vol. 28, no. 1, pp. 61-75, 1994.

[9] K. Uchida, A. Sumalee, D. Watling, R. Connors, "A study on network design problems for multi-modal networks by probit-based stochastic user equilibrium," Networks and Spatial Economics , vol. 7, no. 3, pp. 213-240, 2007.

[10] L. J. Leblanc, "An algorithm for the discrete network design problem," Transportation Science , vol. 9, no. 3, pp. 183-199, 1975.

[11] M. Chen, A. S. Alfa, "Network design algorithm using a stochastic incremental traffic assignment approach," Transportation Science , vol. 25, no. 3, pp. 215-224, 1991.

[12] Z. Y. Gao, J. J. Wu, H. J. Sun, "Solution algorithm for the bi-level discrete network design problem," Transportation Research B , vol. 39, no. 6, pp. 479-495, 2005.

[13] K. Jeon, J. S. Lee, S. Ukkusuri, S. T. Waller, "Selectorecombinative genetic algorithm to relax computational complexity of discrete network design problem," Transportation Research Record , no. 1964, pp. 91-103, 2006.

[14] M. Abdulaal, L. J. LeBlanc, "Continuous equilibrium network design models," Transportation Research B , vol. 13, no. 1, pp. 19-32, 1979.

[15] T. L. Friesz, H. J. Cho, N. J. Mehta, R. L. Tobin, G. Anandalingam, "Simulated annealing approach to the network design problem with variational inequality constraints," Transportation Science , vol. 26, no. 1, pp. 18-26, 1992.

[16] Q. Meng, H. Yang, M. G. H. Bell, "An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem," Transportation Research B , vol. 35, no. 1, pp. 83-105, 2001.

[17] S. W. Chiou, "Bilevel programming for the continuous transport network design problem," Transportation Research B , vol. 39, no. 4, pp. 361-383, 2005.

[18] D. Z. W. Wang, H. K. Lo, "Global optimum of the linearized network design problem with equilibrium flows," Transportation Research B , vol. 44, no. 4, pp. 482-492, 2010.

[19] H. Yang, M. G. H. Bell, "Models and algorithms for road network design: a review and some new developments," Transport Reviews , vol. 18, no. 3, pp. 257-278, 1998.

[20] P. Luathep, A. Sumalee, W. H. K. Lam, Z. C. Li, H. K. Lo, "Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach," Transportation Research B , vol. 45, no. 5, pp. 808-827, 2011.

[21] F. Shi, E. H. Huang, Q. Chen, Y. Z. Wang, "Optimization of one-way traffic organization for urban micro-circulation transportation network," Journal of Transportation Systems Engineering and Information Technology , vol. 9, no. 4, pp. 30-35, 2009.

[22] F. Shi, E. H. Huang, Q. Chen, Y. Z. Wang, "Bi-level programming model for reconstruction of urban branch road network," Journal of Central South University of Technology , vol. 16, no. 1, pp. 172-176, 2009.

[23] X. P. Wang, L. M. Cao Theory, Application and Software Implementation , Xi'an Jiaotong University Press, Xi'an, China, 2002.

[]