Academic Journal of Science and Technology ISSN: 2771-3032 | Vol. 5, No. 3, 2023 253 Equilibrium Assignment of Traffic Networks Based on Path Selection Lirong Lin College of traffic & Transportation, Chongqing Jiaotong University, Chongqing, 400074, China Abstract: Traffic assignment is a crucial phase in transportation planning, involving the distribution of trip data between origin and destination points obtained from surveys across the existing or planned road network. This process helps estimate the traffic volume on each road segment. In this study, we propose a traffic assignment model utilizing the Logit methodology. As a comprehensive path-based assignment model, the Logit approach determines the probability of users selecting each route. Subsequently, the overall traffic demand and route selection probabilities are employed to calculate the traffic volume on each route. Keywords: Traffic network allocation; Logit model; MSA algorithm. 1. Transportation Network Overview According to the graph theory definition, a transportation network is defined as a directed graph, where vertices represent the origin points of the actual network, and edges correspond to road segments within the network[1]. Figure 1.1 depicts a simplified city road network, represented by a directed graph G=(N,A), where N denotes the set of nodes and A signifies the set of road segments. The origin and destination points represent the traveler's starting and ending nodes, respectively[2]. Figure 1. Simplify the urban road network 2. User Optimal Equilibrium Model The initial research on user travel behavior originated from the first and second theorems of traffic network balance proposed by Wardrop in 1952[4]. In Wardrop's first equilibrium principle, it is assumed that all travelers within the network possess complete information about the network. Each traveler aims to select the shortest travel path for themselves[5]. In the network equilibrium state achieved under this condition, the travel time for the path chosen by the traveler between the same Origin-Destination (OD) pair is equal and shorter than that of any unselected path, resulting in the shortest travel time[6]. In this state, no traveler in the network can reduce travel time by altering their route. Generally, Wardrop's first equilibrium principle is referred to as Wardrop equilibrium or User Equilibrium (UE). Assuming that the traffic demand between OD pairs in the network is fixed, and the travel time of road segments increases as traffic volume rises, the network achieves UE equilibrium as illustrated below using an OD pair connected by two paths[3]. Figure 2.1 displays a simplified network diagram, with points O and D representing the origin and destination points, respectively, while LINK1 and LINK2 denote the two paths between the OD pair. Figure 2. Simplified network diagram Figure 2.3 illustrates the relationship between travel time and traffic volume for road segments. Q1 and Q2 represent the traffic volumes on road segment 1 and segment 2, respectively[7]. Meanwhile, t(q1) and t(q2) denote the respective relationships between travel time and traffic volume for each road segment, conforming to the following equation: q = q1 + q2. (1) Figure 3. Road section travel function Where q represents the traffic demand between OD pairs. As can be observed from Figure 2.2, when the traffic demand between OD pairs is minimal, only segment 1 has traffic 254 volume, as the travel time of road segment 1 is shorter than that of road segment 2. As traffic demand continues to increase and reaches q*, the travel times for road segments 1 and 2 become equal. At this point, some travelers begin to choose road segment 2 for their journey. Consequently, under this condition, certain travelers who initially opted for route 1 will switch to route 2, leading to an increase in the travel time of road segment 2. This change affects subsequent travelers, who may then choose route 1 for their journey[8]. This process repeats until the network attains a new equilibrium state. The network travel time under this condition is depicted in Figure 2.3: Figure 4. Network travel time function Among them, the abscissa d represents the traffic demand of the network, the ordinate represents the network travel time, and t(q) represents the network travel time function. It can be seen from the figure that when the traffic demand between OD pairs is less than q*, the network traveler will only select route 1, and the total travel time of the network will be the same as the travel time of selecting road segment 1, that is, the traveler only chooses the path to travel. When the traffic demand between OD pairs is greater than q*, the traveler chooses two paths at the same time, and the function of traffic demand and travel time after the whole network reaches balance is shown in t(Q), when the traffic demand is equal to Q, the total travel time of the network is t*, the traffic volume through section 1 is q1, and the traffic volume through section 2 is district q2. Wardrop's User Equilibrium (UE) state can be characterized by the integral difference between the actual travel time and the shortest travel time for all travelers, equating to zero[9]. This concept can be articulated using Equations 1.2 and 1.3: f c μ 0 ∀r ∈ R ,∀w ∈ W (2) c μ 0, ∀r ∈ R , ∀w ∈ W (3) Among them, c represents the actual travel time of section r ∈ R between OD and w ∈ W , μ represents the shortest travel time between w ∈ W, and f represents the traffic volume of section r ∈ R between w ∈ W. Beckmann equates the UE equilibrium to the KKT condition of the following mathematical programming model, and obtains the traffic volume distribution that meets the UE requirements by solving the model[10]. The formula is as follows: minZ v ∑ t s ds∈ (4) ∑ f d , ∀w ∈ W∈ (5) ∑ ∑ f δ v , ∀a ∈ A∈∈ (6) f 0, ∀r ∈ R ，w ∈ W (7) 3. Logit Model The Logit method is a typical probability random assignment method. Assume that each road user between a certain OD point pair (r, s) always chooses the path k that he thinks has the least impedance. At this time, the impedance value subjectively judged by the road user is called "perceived impedance", expressed by C , and expressed by c represents the actual impedance of the path, then there is C c λ ，∀k, r, s (8) In the formula: λ is the random error term, and E λ 0 According to the Wardrop path selection principle, the probability that the kth path is selected is μ μ C C ，∀l k; ∀k, r, s (9) At this time, the selection of the path is a problem of selecting the most effective choice branch from multiple choices. According to the random utility theory, it is assumed that λ is independent of each other and obeys the same Gumbel distribution (at this time, a λ can be used to represent all λ ’s condition) the selection probability of path k is: μ ∑ ，∀k, r, s (10) In the formula, θ is a parameter related to the variance of λ. It can be proved that θ （ ） , formula (10) is the Logit model[11]. 4. Path-Based MSA Algorithm The Method of Successive Averages (MSA algorithm for short) is widely used to solve the stochastic user equilibrium model, and the MSA algorithm can be solved based on path variables and road section variables[12]. The original algorithm for addressing traffic assignment problems is the all-or-nothing allocation method, also known as the 0-1 distribution method. This approach tends to cause the congregation of similar users on specific roads, leading to an uneven distribution of traffic in urban networks and less- than-ideal simulation effects[13]. It is most suitable for underdeveloped transportation areas. Subsequently, the incremental allocation method and the Method of Successive Averages (MSA) algorithm were proposed. The traffic assignment performance of the incremental allocation method surpasses that of the all-or-nothing allocation method. Developed as an approximate balance algorithm based on the 0-1 allocation method, it equally divides the Origin- Destination (OD) traffic volume into N parts. It then allocates the N-part traffic volume to the network's shortest path, updating the impedance of each road segment after each cycle. The algorithm finds the shortest path based on the new road segment impedance and assigns the subsequent OD traffic volume to the new shortest path in the next cycle. This process is repeated until the distribution of OD traffic in N equal parts is completed. Although the incremental allocation method is simple and feasible, with adjustable accuracy through N, it is still widely used in practice. However, it has certain 255 shortcomings. As an approximation method, when the road segment impedance function is not highly sensitive, excessive traffic may be allocated to road sections with limited capacity. Both the MSA (Method of Successive Averages) algorithm and the incremental allocation method are iterative allocation approaches. However, the MSA algorithm serves as an intermediate cyclic allocation method between the incremental allocation method and the User Equilibrium (UE) allocation method. It overcomes the traffic assignment issues caused by the incremental allocation method, while also addressing traffic distribution problems when the impedance of road segments varies with the flow. In the User Equilibrium (UE) model, if the path traffic f is considered a variable, a solution algorithm based on path variables can be derived. Path-based solving algorithms require determining the set of paths either prior to or during the solving process[14]. Algorithm steps: Step 1: Complete the logit loading in the zero-flow network to obtain the initial path traffic q0, so that the number of iterations is i=0. Step 2: Update time. Calculate the path travel time ti of each path. Step 3: Determine the search direction. Based on the current route travel time ti, the logit loading is completed and the auxiliary road traffic q is obtained, and the search direction can be expressed as q q . Step 4: Update road traffic, order q q 1 i q q Step 5: If the convergence indicator requirements are met, stop the iteration, otherwise let i=i+1 go to Step2. MSA algorithm process: Figure 5. Block diagram of the M S A program algorithm 5. Original Case Analysis Figure 6. Traffic network diagram Path 1 travel cost function: C1=1+2q1 Path 2 travel cost function: C2=2+q2 In the formula, q is the path flow value. The iterative calculation process is as follows: Table 1. Iteration Process i=1 𝑞 𝐹 q 𝑞 Path traffic selection probability Path impedance selection probability path traffic Path1 5 0.5 11 0.12 1.2 Path2 5 0.5 7 0.88 8.8 𝑞 𝑞 1 1 𝑞 𝑞 i=2 Path1 1.2 0.12 3.38 0.98 9.76 Path2 8.8 0.88 10.81 0.02 0.24 𝑞 𝑞 1 2 𝑞 𝑞 i=3 Path1 5.48 0.55 11.95 0.06 0.62 Path2 4.52 0.45 6.52 0.94 9.38 𝑞 𝑞 1 3 𝑞 𝑞 ...... i=6 Path1 3.95 0.395 8.9 0.395 3.95 Path2 6.05 0.605 6.05 0.605 6.05 Converged 6. Case Analysis 6.1. Traffic network diagram Logit model has been widely used in traffic assignment problems. as the picture shows. There is a pair of OD pairs in the network, which is composed of 9 nodes, 5 sections, and 3 paths. The relevant variables in the network are shown in the table. Figure 7. Traffic network diagram No. of iterations：i=0 Generating initial flow solutions，𝑞 Calculating the mapping function，F q Calculate the optimal direction of descent on the basis of F q ：𝑞 Updating the flow： 𝑞 𝑞 1 𝑖 𝑞 𝑞 Convergence or not Update flow：i=i+1 End of output：𝑞 No Yes O D Q=1 0 Route 1 Route 2 256 Table 2. Road Section Parameters in the traffic network Section number Starting point end Section capacity 1 O A 700 2 O H 1000 3 A B 700 4 B E 500 5 B C 700 6 C F 600 7 E F 800 8 E B 900 9 H A 400 10 H E 1100 11 H G 400 12 F D 600 13 G D 400 Table 3. O D pairs of feasible paths path number Include sections 1 O-A-B-C-F-D 2 O-A-B-E-F-D 3 O-H-E-F-D 4 O-H-E-B-C-F-D 5 O-H-G-D 6 O-H-A-B-C-F-D 7 O-H-A-B-E-F-D 6.2. Traffic network diagram The algorithm iterates 26 times, and the error value is 0.000964682247. Table 4. Results path path traffic path impedance Selection probability 1 260.65 45.23 0.2 2 163.36 49.9 0.12 3 177.95 49.03 0.14 4 49.13 61.89 0.04 5 474.50 39.27 0.36 6 119.52 53 0.09 7 74.91 57.67 0.06 By changing the size of θ, the probability of path selection will also change. Table 5. Effect of values on path selection path selection probability θ 0.1 θ 0.2 θ 0.3 θ 0.4 1 0.2 0.22 0.23 0.24 2 0.12 0.09 0.06 0.04 3 0.14 0.1 0.07 0.05 4 0.04 0.01 0 0 5 0.36 0.51 0.6 0.66 6 0.09 0.05 0.02 0.01 7 0.06 0.02 0.01 0 7. Conclusion Based on the network equilibrium model and logit model, this paper studies the objective function and constraints of UE users, and uses the MSA algorithm to allocate traffic to the traffic network. In order to make the calculation easier, the algorithm is programmed in python language. At the same time, it is found that the logit model uses different θ values, and the user's selection probability for the same traffic network path is also different.. References [1] Xu WQ, Han DQ, Liu MJ. Activity-based stochastic equilibrium analysis of traffic congestion networks[J]. Transportation System Engineering and Information, 2014, 14(03):174-178. [2] Zhou Bomi,Li XH,He J. A new algorithm for solving path- based logit-type stochastic user equilibrium model[J]. Chinese Journal of Highways,2014,27(03):100-107. [3] Liu Shixu,Chi Qiyuan,Yan Hao,Guo Lidan,Tang Yingnuo,Yan Hai. A multi-modal stochastic user equilibrium allocation model based on hierarchical logit[J]. Journal of Chang'an University (Natural Science Edition),2018,38(05):114-122. [4] Yu, Lijun. Optimal traffic assignment for generalized systems with roadway capacity constraints[J]. Journal of South China University of Technology (Natural Science Edition),2021,49(04):140-148. [5] Chen Xianlong,Zhou Ribo,Xu Liang. Practice of developing mesoscopic traffic simulation model based on dynamic traffic distribution[C]//Chinese Simulation Society. Proceedings of the 33rd China Simulation Conference. [publisher unknown], 2021:8. [6] ZHANG Jinwei,WU Zhong. Traffic distribution model considering intersection impedance [J]. Science and Technology Bulletin, 2020,36(10):73-76+81. [7] Cheng S.Y., Liu Y., Guo J.H.. A method for computing user equilibrium allocation uncertainty[J]. Journal of Nanjing University of Information Engineering (Natural Science Edition),2019,11(04):421-427. [8] Gao M.Y.,Shi H.G.. Node assignment algorithm for large-scale road traffic volume allocation[J]. Journal of Transportation Engineering and Information,2020,18(02):119-124. [9] He Shengxue. Traffic allocation model and algorithm considering environmental impact constraints[J]. Journal of East China Jiaotong University,2019,36(01):87-93. [10] Zhang W.Y., Li Z., Li H.L., et al. A C-Logit stochastic traffic assignment model based on probabilistic dominance[J]. Journal of Beijing Jiaotong University,2018,42(06):61-66. [11] Liu BQ, Chen B, Du Wei. An efficient algorithm for capacity- constrained traffic assignment in asymmetric elastic demand networks[J]. Practice and understanding of mathematics, 2018, 48(11): 133-139. [12] Liu H X, Rong X. Research on multi-path traffic assignment based on K short circuit [J]. Comprehensive Transportation, 2018, 40(01):68-72. [13] Liu Yuan. Research on dynamic traffic allocation based on flow restrictions of key road sections [J]. Journal of Transportation Engineering and Information, 2017,15(02):125- 130. [14] Liu BQ, Du Wei. An improved artificial fish swarm algorithm for solving Logit stochastic user equilibrium problem[J]. Modern Electronics Technology, 2016,39(03):127-130.