Simulation model based on Monte Carlo method for traffic assignment in local area road network

Abstract

For a local area road network, the available traffic data of traveling are the flow volumes in the key intersections, not the complete OD matrix. Considering the circumstance characteristic and the data availability of a local area road network, a new model for traffic assignment based on Monte Carlo simulation of intersection turning movement is provided in this paper. For good stability in temporal sequence, turning ratio is adopted as the important parameter of this model. The formulation for local area road network assignment problems is proposed on the assumption of random turning behavior. The traffic assignment model based on the Monte Carlo method has been used in traffic analysis for an actual urban road network. The results comparing surveying traffic flow data and determining flow data by the previous model verify the applicability and validity of the proposed methodology.

Keywords

traffic assignment / local area road network / turning ratio / Monte Carlo method

Introduction

Due to the great importance of efficient traffic for modern society, the investigation of traffic flow problems is a very attentive topic of deliberation and research for engineers and scholars nowadays because it directly relates to the adjustment, construction, and management of traffic. Considering restrictions of labor and materials, direct measurement by manual observation or automatic survey equipment is not suited for urban road networks that include large numbers of intersections and road links. Mathematical modeling for the assignment traffic flow of networks has been a key tool to understanding the behavior of the transportation system. There has been a lot of literature on the traffic assignment problem of networks. One of them with the greatest impact is the Wardrop equilibrium condition that has considered the road congestion effect [1], which is also called the user equilibrium condition. The user equilibrium assignment problem has been the focus in the past five decades. As a result of Refs. [2-8] we have gained substantial knowledge on the formulations, properties, and solution methods of user equilibrium assignment. During the past 20 years, software systems have matured, and today several international firms, such as Caliper, Citilabs, INRO, and PTV, dominate this market.

However, even though these user equilibrium assignment models and software systems have been widely used in transportation planning and traffic management, there are some arguers on the usability and reliability of these methods, especially in a local area road network [9-11]. One key point is that these equilibrium assignment methods are made on the basis of the OD matrix. The assumption of trip Origin and trip Destination is used quite often in the complete traveling chain of city level. In terms of the road networks in small areas, it is hard to define and record the OD of a traveler. The available traffic data of traveling are the flow volumes in the key intersections of a local area road network, not the complete OD matrix [12]. On the other side, the user equilibrium assignment method takes the center of mass in the traffic sub-areas as the Origin point or Destination point. However, this definition method often makes the traveling activities in the small scopes network concentrated on the same point, and the excessive concentration may lead to the failure of analysis of the microcosmic road network structure.

In road networks, most travelers make turns according to their planned routes, which they choose in order to arrive efficiently from a starting location to an ending location. That is the turning ratio that reflects the overall option behavior of all travelers at the downstream intersection. A number of studies on the turning ratio of an intersection can be found in the literature, and they can be broadly classified into two categories: estimated turning proportions statistically from automatic traffic detectors [13-15], and estimated OD flows in networks from link flows [16, 17]. The focus on turning ratio in urban traffic studies and models is mainly due to the simplification of model formulation, derivations, computations, and input specification.

Considering the circumstance characteristic and the data availability of local area road networks, we attempt to make a new model for traffic assignment based on Monte Carlo simulation of intersection turning movement. This model only needs traffic volume data of the inlet road links and the turning ratio of intersections, which can be easily attained from automatic field traffic survey equipment and manual survey.

This paper is organized as follows. We first introduce the modeled local area road network with the definitions and notation adopted in this paper. Then the stability of the urban intersection turning ratio is discussed. And then we describe the formulation for the local area road network assignment problem. A simulation solution algorithm is proposed to solve the resultant problem, and then an actual example is given to demonstrate the applicability and validity of the proposed methodology.

Modeled local area road network

Consider a local area road network like Zone A in Fig. 1, which is encircled by trunk roads. In this local area road network, streets and sideways are dispersed. And the whole urban network consists of dozens of local area road networks like Zone A.

For the sake of easy expression, the local area road network in Zone A is abstracted to the schematic road network shown in Fig. 2. It is a network consisting of a lot of connecting links and nodes.

The nodes in Fig. 2 represent the intersections and are the cross points of links. The links represent the direction road links and the direction of link is the same as the driving direction of vehicles. The surrounding area of the local area road network is a closed boundary line, shown as the virtual lines in the figure. The areas within the virtual lines are the study scope of the traffic volume distribution problem about the local area road network. For the sake of consequent analysis and discussion, the inlet road link from which the vehicles enter the area through the boundary is defined as the mark i and the inlet road link collective is the mark I. The exit road link from which the vehicles go out of the area through the boundary is defined as the mark e and the exit road collective is the mark E. The road link surrounded by the boundary is the internal road link, with the mark k; this internal road collective is the mark K. The inlet road links are connected by important intersections of trunk road, in which automatic field traffic survey equipment are usually installed.

Stability of turning ratio in intersections

In general, when driving in the urban road network the vehicles must go through many intersections before arriving at their destination. In their trips, the turning movements of vehicles in the intersections are the embodiment of selecting the route. In terms of the network analysis, the turning ratio of intersection reflects the distribution details of the overall options of travelers.

Reference [18] discussed the stability problem of turning ratio in the intersections of urban road networks and concludes that the stability of turning ratio is caused by the relatively stable traveling routes of drivers. On the condition that the traffic pressure of the city is very large and the transportation infrastructure resources are intense, the drivers are often inclined to select the fixed routes; they will not change their traveling routes unless some very serious traffic congestion or emergency events occur. On the other hand, the uncertainty of traveling time caused by the route change will increase the opportunity cost of options and this makes the travelers hesitate to try a new route.

Based on the historical flow volume data in 76 main intersections collected by the urban road traffic information system in Shanghai (a successive week from May 16, 2006 to May 22, 2006), the changes in turning ratio were analyzed. Table 1 presents the statistical results about changes in turning ratio of 76 intersections each day; Figs. 3(a) and (b) are the time-varying drawings of turning ratio fluctuation in some intersections. From these table and figures, it can be found that the turning ratio of road intersections has good repeatability each day and good stability within one day.

The good daily repeatability of the turning ratio in the intersection makes it a good parameter to be used for the traffic analysis of urban road networks. On the other hand, the time-serials stability of turning ratio ensures the reliability to take the actual measured intersection turning ratio value in a small time slice (usually 15 min) as the representative value of turning ratio at this intersection. This point will reduce the workload of field investigation to some extent and strengthen the applicability of this parameter.

Traffic assignment model based on Monte Carlo method

Introduction of Monte Carlo method

The Monte Carlo method, also called the random sampling method or the statistic testing method, is a branch of computational mathematics. It originates from the earlier mathematics thoughts of “the frequency approximates the probability.” When the solution problem is the occurrence probability of a certain event, or is an expected value of any variant, they may make use of a “testing” method to get the occurrence frequency of an event or the average value of this variant and these may be used as the solutions to problems. These are the basic thoughts of the Monte Carlo method.

The Monte Carlo method is a process in which, based on the probability model and in accordance with the process described by this model, the simulation test results will become the approximate solutions. Compared with other value calculation methods, the Monte Carlo method has the following advantages:

1) The convergence speed is not related to the problem dimensions.

2) It has strong applicability and is less influenced by the limit of problem conditions.

3) The program structure is very simple. In performing the calculation of the Monte Carlo method in computers, the program structure is very clear and simple and is easily programmed and commissioned.

In recent years, with the fast development of computer technologies, the Monte Carlo method has been widely applied to scientific studies about physics and engineering, etc.

Monte Carlo simulation of turning behavior in intersections

From the perspective of traveling individuals, the turning ratio of intersections represents the optional probability of vehicles turning to various directions in the downstream intersection. And the turning behavior in the intersection is the micro embodiment of option behavior of vehicle trips. Therefore, the Monte Carlo method is used in this paper to perform the simulation of driving behaviors of vehicles in the local area road network.

More specifically, when the “simulation vehicle” arrives at the downstream intersection in the local area road network, a random variant will be produced to determine the turning behaviors of vehicles. The turning ratio reflects the overall option behavior of all vehicles at the downstream intersection. In terms of the individual “simulation vehicle,” its turning behavior is randomly selected and the turning ratio value of this intersection is the probability of a certain turning behavior.

If the turning ratios at the downstream intersection are separately measured as follows: turn to the left: go straight: turn to the right={\xi }_1:{\xi }_2:1-{\xi }_1-{\xi }_2, the probabilities of the individual “simulation vehicle” turning to the left, turning to the right or going straight at this intersection are randomly {\xi }_1,{\xi }_2,\mathrm{1}-{\xi }_1-{\xi }_2.

To enable computer programs to perform the turning behavior simulation, γ is defined as the random number uniformly distributed within the [0,1) interval and the following specification is also made:

(1)

In accordance with the principle of the Monte Carlo method, we know that if N “simulation vehicles” make the turning options at the this downstream intersection, the frequencies of turning to the left, turning to the right, and going straight are ν₁, ν₂ and ν₃ respectively, so when the N is large enough: the frequency for turning to the left {\overline{p}}_{\mathrm{1}}, the frequency for going straight {\overline{p}}_{\mathrm{2}}, and the frequency for turning to the right {\overline{p}}_{\mathrm{3}} are respectively calculated as follows:

(2)\{\begin{array}{l}{\overline{p}}_{\mathrm{1}}=v_1/N\approx {\xi }_{\mathrm{1}},\hfill \\ {\overline{p}}_{\mathrm{2}}=v_2/N\approx {\xi }_{\mathrm{2}},\hfill \\ {\overline{p}}_{\mathrm{3}}=v_3/N\approx 1-{\xi }_{\mathrm{1}}-{\xi }_{\mathrm{2}}.\hfill \end{array}

Traffic assignment model in local area road network

Consider the closed local area road network shown in Fig. 2, including N_I inlet road links, N_E exit road links, and N_K internal road links. Based on the description of formula (1) about the turning option behaviors of vehicles at the intersection, the ratio relationship between the flow volume at each road link and the flow volume at each inlet road link may be solved with the Monte Carlo method.

For each vehicle that goes from the inlet road link i to the road network, whether it arrives at an exit road link e (or internal road link k) is a random event. Set \xi as a random variant; if the vehicle arrives at the exit road link e (or the internal road link k), \xi will be valued at 1; in other conditions, \xi will be valued at 0. In the driving process of one vehicle, the mathematic expectation E(\xi) of random variant \xi is equal to the vehicle arrival probability P(ie) from the inlet road link i to the exit road link e [or equal to the vehicle arrival probability P(ik) from the inlet road link i to the internal road link k]. The formula is shown as follows:

(3)\{\begin{array}{l}P(ik)={\displaystyle \sum _{\alpha =1}^{t_k}p{(ik)}_{\alpha }}={\displaystyle \sum _{\alpha =1}^{t_k}({\displaystyle \prod _{j=1}^{N\alpha }{\overline{p}}_j}}),\hfill \\ P(ie)={\displaystyle \sum _{\alpha =1}^{t_e}p{(ie)}_{\alpha }}={\displaystyle \sum _{\alpha =1}^{t_e}({\displaystyle \prod _{j=1}^{N\alpha }{\overline{p}}_j}}),\hfill \end{array}

in which t_k represents the potential path quantity from the inlet road link i to the internal road link k; t_e represents the potential path quantity from the inlet road link i to the exit road link e; p(ik)_α represents vehicle arrival probability through path α from the inlet road link i to the internal road link k; p(ie)_α represents vehicle arrival probability through path α from the inlet road link i to the exit road link e; and {\overline{p}}_j represents the frequency of turning in the intersections of path α.

Further, the vehicle arrival probability p(ik) of the internal road link k and the arrival probability p(ie) of the exit road link e may be assembled into a matrix BoldItalic: N₁(N_K+N_E). This matrix BoldItalic is called the traffic assignment coefficient matrix of the local area road network and is shown as Eq. (4):

(4)\mathit{Q}=\left(\begin{array}{cccc}{q}_{11}& q_{12}& \cdots & q_{1(N_K+N_E)}\\ q_{21}& q_{22}& \cdots & q_{2(N_K+N_E)}\\ ⋮& ⋮& & ⋮\\ q_{N_{I}1}& q_{N_{I}2}& \cdots & q_{N_I(N_K+N_E)}\end{array}\right),

in which q_mn represents the flow arrival probability from the inlet road link i to the internal road link k or the exit road link e. q_mn is shown as

(5)q_{mn}=\{\begin{array}{l}P(ik),\mathrm{1}\le m\le N_I,\mathrm{1}\le n\le N_K,\hfill \\ P(ie),\mathrm{1}\le m\le N_I,N_K+\mathrm{1}\le n\le N_K+N_E.\hfill \end{array}

For the closed local area road network shown in Fig. 2, on the condition that the flow volume data of all inlet road links are known, the flow volumes of each internal road link within the network and each exit road link can be solved with Eq. (6):

(6)\mathit{\zeta }=\mathit{\lambda }\mathit{Q}\mathit{,}

in which ζ represents the flow volume vector of each internal road link and exit road link, ζ=(v{\prime }_{\mathrm{1}},v{\prime }_{\mathrm{2}},\mathrm{...},v{\prime }_{N_{\mathrm{k}}+N_{\mathrm{E}}});BoldItalic represents the traffic assignment coefficient matrix of local area road network, BoldItalic is N_I(N_K+N_E)matrix, shown in Eq. (4); λ represents the flow volume vector of each inlet road link to the local area road network, λ=(v_{\mathrm{1}},v_{\mathrm{2}},\mathrm{...},v_{N_I}).

Simulation method for traffic assignment coefficient matrix of local area road network

For a local area road network which only has several links, it is still difficult work to find all available paths between two arbitrary links. Therefore, it is hard to solve formula (3) directly. In accordance with the Monte Carlo principle, a simulation method for the traffic assignment coefficient matrix BoldItalic of the local area road network is provided in this paper. The simulation process of the road network includes the following steps:

1) Set the quantity of “simulation vehicles” entering each inlet road links that will be inputted to the local area road network as ν_i(i∈I), and each “simulation vehicle” is a traveling unit. At the same time, the flow of vehicles within the network is set as 0.

2) Randomly sample an inlet road link i and input one traveling unit from this road to the local area road network. When this “simulation vehicle” arrives at a downstream intersection, the above Monte Carlo method may be used for route options, i.e., automatically produce the random number γ that is uniformly distributed within [0,1) interval via the computer, and determine its turning direction in accordance with the interval of γ. After the turning direction is determined, one traveling unit is added to the road where the “simulation vehicle” drives, and so on, until this “simulation vehicle” arrives at a certain exit road link e (e∈E) of this road network. Then, the simulation process of the next traveling unit at the inlet road link i may be calculated in the same way, until the quantity of simulation vehicles amounts to ν_i.

It should be specially emphasized that in the whole driving process where each “simulation vehicle” enters the road network and leaves the road network, the computer program will “track” the traveling unit’s route for two purposes: first of all, to ensure that the driving routes of simulation vehicles are reasonable and effective and there is no “loop”; secondly, to record the flow volume data of all road links in the road network to establish the correspondence relationship between the flow volume of inlet road links and the flow volume of other road links. Although the driving routes and OD pairs of “simulation vehicles” can be obtained from this simulation method, they are not in accord with the actual travel paths. In fact, the purpose of this simulation method is to provide the precise traffic volume data of road links in a local area road network.

3) Once again, randomly sample one inlet road link in which flow simulation assignment has not been made and repeat the above simulation process, until the simulation process of the flow volume in all inlet road links is done.

4) Calculate the vehicle flow volume at each inlet road link within each road link of the local area road network, and the results are stored at the matrix BoldItalic of N_I(N_K+N_E), and the matrix BoldItalic is called the simulation flow matrix of the local area road network, just as shown in the form

(7)\mathit{T}=\left(\begin{array}{cccc}{t}_{11}& t_{12}& \cdots & t_{1(N_K+N_E)}\\ t_{21}& t_{22}& \cdots & t_{2(N_K+N_E)}\\ ⋮& ⋮& & ⋮\\ t_{N_{I}1}& t_{N_{I}2}& \cdots & t_{N_I(N_K+N_E)}\end{array}\right),

in which t_mn(1≤n≤N_K) represents the flow volume of vehicles that go from inlet road link i to internal road link k in the simulation process; and t_mn(N_K≤n≤(N_K+N_E)) represents the flow volume of vehicles that go from inlet road link i to exit road link e in the simulation process.

In accordance with the Monte Carlo principle,

(8)q_{mn}=\{\begin{array}{l}P(ik)=\underset{v_i\to \infty }{{\displaystyle \lim }}{\displaystyle \frac{t_{mn}}{v_i}}\begin{array}{ll},& \end{array}\mathrm{1}\le m\le N_I,\mathrm{1}\le n\le N_K,\hfill \\ P(ie)=\underset{v_i\to \infty }{{\displaystyle \lim }}{\displaystyle \frac{t_{mn}}{v_i}}\begin{array}{ll},& \end{array}\mathrm{1}\le m\le N_I,N_K+\mathrm{1}\le n\le N_E.\hfill \end{array}

When ν_i is large enough, based on the Monte Carlo principle, we know that the matrix BoldItalic obtained from the simulation analysis will be converged to a steady result. Therefore,

(9)q_{mn}\approx {\displaystyle \frac{t_{mn}}{v_i}}\begin{array}{ll},& \end{array}\mathrm{1}\le m\le N_I,\mathrm{1}\le n\le N_K+N_E.

How many “simulation vehicles” are enough for the Monte Carlo simulation method in a local area road network? Different “simulation vehicle” amounts are applied in a testing road network just as in Fig. 2 to ascertain the criterion of “simulation vehicle” amount. The mean absolute value of relative tolerance between initialization turning ratios and turning ratios of simulation procedure is used to determine the variability of simulation results. Figure 4 shows the relationship between the mean absolute value of relative tolerance and “simulation vehicle” amount.

From Fig. 4 we can find that the mean absolute value of relative tolerance decreases quickly just when the “simulation vehicle” amount increases in the initial phase. When the “simulation vehicle” amount reaches 2000 vehicles, the mean absolute value of relative tolerance remains at a steady level of 0.01. That means that 2000 vehicles can be regarded as a large enough amount for the Monte Carlo simulation method. This criterion of “simulation vehicle” amount ensures the precision of the Monte Carlo simulation method for the traffic assignment coefficient matrix BoldItalic. It also saves the computer time and improves the efficiency of the simulation program.

Experimental result

To verify the applicability of the traffic assignment method put forward in this paper to the actual analysis of a local area road network, we select a true local area road network in Changning District, Shanghai, China as the road network for testing. We employed the “traffic assignment model based on the Monte Carlo method” for the traffic volume distribution of the road network and the comparison of true data results.

Profile of road network for testing

This road network for testing is a close road network consisting of four trunk roads, namely, Changning Road, West Yan’an Road, West Zhongshan Road, and Jiangsu Road, as shown in Fig. 5. This road network has 38 intersections, 21 inlet road links, 21 exit road links, and 124 internal road links.

Traffic volume assignment

Among the 21 inlet road links within this road network for testing, the Shanghai Municipal Engineering Management Department installed embedded loop detectors in 14 intersections which were distributed in Changning Road, West Yan’an Road, West Zhongshan Road, and Jiangsu Road. The input flow data of these road sections may be available from the historical database of the real-time traffic survey system. For the remaining inlet road links, we performed a long-time (2 h) manual investigation. We also made a short-time (half an hour) manual investigation into the turning ratio of 38 intersections in the road network for testing.

Based on this, we made good use of the Monte Carlo simulation method to get the simulation traffic assignment coefficient matrix BoldItalic of this local area road network. Then, we made good use of real-time traffic data of automatic field survey equipment in intersections and manual investigation data to get the input flow volume vector of this area λ, and employed Eq. (6) to calculate the flow volume values of 21 exit road links and 124 internal road links within this area.

We marked the flow volume values at each road link within the road network for testing in the GIS drawing with the different width lines. Please refer to Fig. 6. We know from the figure that, among all roads of the road network for testing, the flow volumes of the main roads, including West Zhongshan Road, West Yan’an Road, Jiangsu Road, and Changning Road, are the largest. At the same time, parts of Kaixuan Road and Dingxi Road within the road network for testing also have large flow volumes.

Result comparison

For the 14 exit road links within the road network for testing that are equipped with the automatic traffic survey equipment, we may compare the actual measured data provided by these equipment and the calculation results of the model to verify the applicability and validity of the method provided in this paper. Table 2 shows the comparison results between the calculation volume data of the model and the actual traffic volume data collected by automatic traffic survey equipment. After comparing these data, we find that the calculation results of the model are generally very approximate to the actual measured data of field survey equipment. The absolute value of relative tolerance is 7.86%. Therefore, the “traffic assignment model based on the Monte Carlo method” has good applicability and validity in the actual road network.

Conlousion

The urban road network is a whole structure with good relationships. Only after fully understanding the traffic conditions of each road link in the road network can we make out the scientific and reasonable traffic control and management plan. Aiming at the traits of traffic assignment in the local area road network, this paper has performed relevant studies on figuring out the traffic volume of road links and made the following conclusions:

1) Verify the time-serial stability of the turning ratio in the urban road network and ensure it as a key parameter suitable for the analysis of the local area road network;

2) Establish the traffic assignment model of the local area road network based on the simulation thoughts of the Monte Carlo random system and provide the simulation calculation method for the traffic assignment coefficient matrix of local area road network;

3) Perform the actual traffic assignment work of the road network by the traffic assignment model based on the Monte Carlo method and compare it with the actually measured data to verify the applicability and validity of this method.

References

[1] Wardrop J G. Some theoretical aspects of road traffic research. In: Proceedings of ICE, Part II. 1952, 1: 325-378

[2] Bechmann M, Mcguire C B, Winsten C B. Studies in the Economics of Transportation. CT: Yale University Press, 1956

[3] LeBlanc L J, Morlok E K, Piersskalla W P. An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research, 1975, 9: 309-318

[4] Aashitiani H Z, Magnanti T L. Equilibrium on a congested transportation network. SIAM Journal of Algebraic and Discrete Methods, 1981, 2: 213-226

[5] Fernandez L J E, Freisz T L. Equilibrium predictions in transportation markets: the state of the art. Transportation Research, 1983, 17B: 155-172

[6] Carey M A. Optimal time-varying flows on congested networks. Operations Research, 1987, 35 (1): 58-69

[7] Ran B, Boyce D E, Leblanc L J. A new c1ass of instantaneous dynamic user—optimal traffic assignment models. Operations Research, 1993, 41(1): 192-202

[8] Florian M, Wu J H, He S. A multi-class multi-mode variable demand network equilibrium model with hierarchical Logit structures. In: Proceedings of Seminar C held at the PTRC Transport and Planning Summer Annual Meeting, University of Sussex, England. 2000, 211-224

[9] Poole M R. Technical Report #11: Allocation Type Approach to Estimation of Travel for Small Urban Areas. NCDOT Statewide Planning Branch, 1989

[10] Anderson M D. Performance of single internal trip purpose methodology to model smaller urban area traffic. Journal of Urban Planning and Development, 2002, 128(1): 1-17

[11] McDonnell J T. Synthesized Through Trip Table for Small Urban Areas. NCDOT Statewide Planning Branch, 1991

[12] Sun Lijun, Yuan Wenping, Cai Xiaoyu. Traffic Impact Analysis and Management Method for Regional Development. Shanghai.2005 (in Chinese)

[13] Bell M G H. The real time estimation of origin-destination flows in the presence of platoon dispersion. Transportation Research Part B, 1991, 25 (2/3): 115-125

[14] Lan C J, Davis G A. Real-time estimation of turning movement proportions from partial counts on urban networks. Transportation Research Part C, 1999, 7 (5): 305-327

[15] Nobe S. On-line estimation of traffic split parameters based on lane counts. AZ: The University of Arizona, 2002

[16] Zhang L, McHale G, Zhang Y. Modeling and validating CORSIM freeway origin-destination volumes. Transportation Research Record, 2003, 1856: 135-142

[17] Muthuswamy S, Levinson D, Michalopoulos P, Davis G. Report number CTS 04-11: Improving the estimation of travel demand for traffic simulation. MN: Department of Civil Engineering, University of Minnesota, 2005

[18] Geng Y J,Du Y C,Sun L J. Research on the Traffic Characteristics of Ground-Level Roads in Shanghai Based on ATMS Data. In: Proceedings of the 11th International Conference of Hong Kong Society for Transportation Studies. 2006, 12: 751-757

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg