Turning Delay Stochastic User Equilibrium Model based on the Weibull Distribution

<jats:p>With the continuous expansion of urban scales and the constant growth of traffic demands, it has become important to accurately predict the distribution of traffic flow so as to relieve the traffic jams and lower the energy consumption. This research mainly focuses on the distribution problem of traffic flow in the urban traffic network. A minimization program has been provided as an alternative formulation for the turning delay stochastic user equilibrium problem. The paper derives the Weibull distribution-based node-link random loading mechanism of turning delay for direct calculation of link and turning flows that are consistent with thepath flow, thus avoiding the enumeration of turning paths. Numerical examples are provided to illustrate the turning delay stochastic user equilibrium (SUE) model and the nodelink- based algorithm. The experiment demonstrates that the present method can reflect the relative performance of link and turning costs well, while presenting its advantages in the simulation of large-scale turning delay flow  ssignment.</jats:p>

section_content: With the rapid development of social economy and urbanization progress and the continuous expansion of urban scales, the social economic activities have become more and more frequent and the traffic demands grow continually. Consequently, urban issues like the shortage of land resource and the traffic jams faced by urban traffic are more and more prominent. As one of the most effective means to improve the land utilization level, relieve traffic jams, and lower energy consumption and noise pollution, the prediction of traffic flow distribution has been extensively considered by urban traffic management department. 

In urban traffic assignment, the link travel time is generally composed of two parts. The first part is the travel time that takes place in the road section. The second part is the intersection delay which occurs at the downstream road junction. The turning delay considers the delay problems caused by traffic flows that travel into the intersection from the same entrance with different turning directions [1] as shown in Figure 1. According to the literature statistics [2], delays occur at intersections under moderate levels of traffic congestion and account for 17%-35% of the entire travel time. It can be seen that in urban traffic within the Los Angeles metropolitan area. Ermagun et al. [17] proposed a two-level Cross-Nested Logit model. It overcomes the problem of the model being limited to descriptive analyses quantifying the active component of public transit. Lai et al. [18] presented an operational estimation procedure for the estimation of route choice multivariate extreme value models. Haghani et al. [19] proposed a double-class stochastic TA approach to dealing with the challenge of lack of observed data before system installation. (iii) Methods with overlap factor, i. e. additional utility factor, included in the utility function, such as C-Logit model [20, 21], Path Size Logit model (PSL) [22] and Extended Path Size Logit model [23, 24]. Zhong et al. [25] proposed two versions of the C-Logit SUE model that captures the route similarity using different attributes in the commonality factors. Xu et al. [26] provided a formulation for the C-Logit stochastic user equilibrium problem with elastic demand in the route domain. Tan et al. [27] proposed a new path-size formulation accounting both for the correlation of the route choice modelling in public transport networks. 

It can be found that almost all of the methods have borrowed some overlap processing features from the Probit model. But as they still use the Gumbel distribution, the variance of estimated path cost distribution remains fixed. In fact, paths with larger actual cost should have greater error term of variance than those with smaller actual cost, because the greater the cost of path, the smaller the possibility for traveller to make accurate estimation. Castillo et al. [28] have proposed a method for solving SUE problem where the Gumbel distribution is replaced by the Weibull distribution. The variance of this distribution is an increasing function of its mean, being a more natural assumption. On the basis of this paper, Kitthamkesorn et al. [29, 30] provided an unconstrained minimization program that considers non-identical perception variances for different trip lengths. Provided the equivalency and uniqueness of the Weibull SUE model the link-based algorithm for solving the model has been developed. Yao et al. [31] examined the stochastic paradox of a Weibull route choice model and extended the stochastic paradox results to a general network. 

In this paper the solution to the turning delay SUE problem when independent Weibull distributions are used for different path traffic costs has been extended. The lengths of different paths are distinguished with different variances provided by the Weibull distribution. The problem of similarity among paths is solved by introducing the C-Logit correction factor. The Weibull distribution-based node-link turning flow assignment algorithm is proposed, and the corresponding mathematical programming model is proven. Numerical examples are also provided to illustrate the features of the turning delay model. network, intersection delay has a significant impact on the calculation of link cost as well as path selection. Therefore, delay at intersections should be considered in the urban traffic assignment model aside from the travel time on the road. 

Random flow assignment method with turning delay has been established based on the stochastic user equilibrium (SUE) model [1, 3], where the link-based algorithm is solved after the addition of turning constraints. At SUE, no motorists can improve their perceived travel time by unilaterally changing routes [4]. There are two main models involved in the study of SUE problems. One is the multinomial Logit (MNL) SUE model [5], based on the Gumbel random error term, that has a closed form solution. MNL model has a simple form and effective realization algorithm, but it has two deficiencies: (i) The estimated cost distribution of alternative paths is assumed to be mutually independent, thus leading to loading of excessive flow on mutually overlapping paths. (ii) The estimated cost distribution of paths has a fixed variance which does not change with path features; this way, the impact of path cost cannot be reflected on the path choice. The other is the multinomial probit (MNP) SUE model [6, 7], based on the normal random error term. MNP model completely abolishes the assumption of independent and identical distribution of utility stochastic term, and can eliminate the situation where the deviation and selection probabilities depend only on the utility difference, but it lacks a closed form solution. Thus, stochastic utility terms of various samples are pairwise correlated, which makes the model too complex. The calculation of multiple integrals is needed, or even numerical method can hardly solve it, thus almost losing its usefulness. Therefore, further improvement of MNL model, especially the independence of irrelevant alternatives (IIA), comparative rationality, as well as flexibility and correlation among alternative terms have become the main direction of Logit model in traffic applications currently. 

To overcome the deficiencies of SUE model, many scholars have proposed the modified forms of MNL model, which can be classified into 3 categories: models using covariance matrix, models using nested selection structure and methods with overlap factor. (i) Models using covariance matrix, where covariance information is added, such as Logit-Kernel model. Bolduc et al. [8] focused on the major issue that arises from applying hybrid choice models with Logit-Kernel to large scale problems. (ii) Models using nested selection structure, such as Nested Logit model [9, 10], Cross Nested Logit model (CNL) [11, 12] and Paired Combinatorial Logit model (PCL) [13, 14]. Qin et al. [15] analyzed the correlation between travellers' parking behaviour and their travel characteristics by two Nested Logit models. Hou et al. [16] applied discrete choice model to examine the location choices Because the estimated cost of each path is a random variable, it has the corresponding probability distribution characteristics. For a certain traveller, each path has a probability to be selected. Probability P k rs for path k between OD pair rs to be selected by traveller is the probability for its estimated cost to be the smallest among all possible path costs between that OD pair, that is, l Krs 6 !,

It can be seen from the definition of stochastic equilibrium assignment that all of the selected paths between a certain OD pair do not necessarily have the same value of actual cost under equilibrium state. But the paths satisfy the following conditions

In this formula, path flow f k rs is related to P k rs ; and P k rs is related to the size of estimated path cost. The size of estimated path cost is related to the estimated link cost, which is a random variable as well. An actual link cost is a function of flow. This way, SUE conditions are ultimately reached. The path flow satisfies the constraints Here, the link cost and the turning delay are processed separately. The former is regarded only as a function t(x) of link flow x. The latter only as a function d(y) of turning flow y. However, there is an inherent relationship between x and y. Furthermore, there are indirect relationships between t and y as well as between d and x. But the correctness of these relationships is assured automatically through the characteristics of traffic assignment algorithm below without the need to be satisfied constrainedly with additional constraints.
section_name: INTRODUCTION

section_content: Assuming that C k rs ~Weibull(p rs, a k rs, b rs ) distribution, its survival function is as follows

where a k rs >0 is the size parameter; 0≤p rs <t is the location parameter; b rs ≥0 is the shape parameter. The mean of function is expressed as The rest of this paper is organized as follows: Section 2 provides some background of the Weibull turning delay SUE problem. Section 3 presents the equivalent MP formulations for the turning delay SUE models and a node-link-based algorithm for solving the turning delay SUE formulations is provided. Numerical results are presented in Section 4, and some concluding remarks are provided in Section 5.
section_name: Route choice probabilities

section_content: Given a traffic network G=(N,A), where node set is N, link and turning set is A. Assuming the function of link and turning costs for the traveller in traffic network is composed of identified cost and random error. The mathematical expectation of random error is zero. The link cost T a on link a and turning cost D ab from link a to link b estimated by the traveller can be expressed as follows

where t a (x a ) is the ascertainable cost on flow of link a by the traveller. It is in a monotonically increasing relationship with the link flow, which exhibits the crowding effect; d ab (y ab ) is the ascertainable cost on flow of turning a→b by the traveller, which is in a monotonically increasing relationship with the turning flow; f a, f ab are the random errors on link a and turning a→b by the traveller, respectively. The mathematical expectations are E(f a )=0, E(f ab )=0. The estimated link costs T a, D ab are random variables, and E(T a )=t a, E(D ab )=d ab. Given the Origin-Destination (OD) pair, the origin set is R={r}, the destination set is S={s}. It is assumed that there is an effective path set K rs between OD pair rs in traffic network. The estimated path cost C k rs in the traffic network by the traveller can be expressed as the sum of costs of all links and turnings comprising the path, i. e.
section_name: THE WEIBULL TURNING DELAY SUE PROBLEM 2.1 The turning delay stochastic user equilibrium model

section_content: The above formula shows that the conditional expectation of C k rs relative to c rs is calculated on the link flow vector and turning flow vector. The partial derivative of expected estimated cost is the selection probability, that is

Equation 4 is substituted into the above Equation 16. After integration, it can be observed that the Weibull model-based S rs (c k rs ) should satisfy

The solutions of Equation 14 can be proven to satisfy the turning SUE conditions. For this optimization model, the first-order necessary conditions on its extreme point are: dZ=0. For the first term of objective function, there is The above equation can be written by Equation

This way, the first-order necessary conditions for mathematical programming model can be written as

where C is Gamma function. Variance is expressed as

According to Castillo et al. [19], the route choice probability can be determined by Meanwhile, b rs is independent of cost as a dimensionless constant, which can be considered an index of network familiarity degree of the measure. The b rs of each traffic network often needs to be calibrated by maximum likelihood method using current OD amount and traffic volume of road section. To avoid excessive flow load on mutually overlapping paths, the location parameter p rs is set as an additional utility factor, and its correction term is defined as [14]

where w a k is the proportional weight of link a for path k; c is the factor; N a is the count of paths, connecting the same OD pairs, which share link a.
section_name: C T D

section_name: SOLUTION ALGORITHM

section_content: The following mathematical programming model is used to describe the turning problem Step 1: Initialization. Pre-links, turnings and post-links are added at the starting and ending positions, respectively. The number of links added is set to 0, and the number of turning delays added to be 0. The shortest path with turning delay is calculated, as well as r(a). For each turning, the likelihood value of turning delay is calculated according to Equation 23. The results are shown in Figure 3., ( )

Step 2: Forward calculation of link weights. Each link a is considered according to the ascending order of r(a) from the starting point. The weight value ~ab of turning a→b is calculated according to Equation 24, where I a is the back collection adjacent to arc a. The results are shown in Figure 4.,,
section_name: Formulation

section_name: L a L if is starting point otherwise

section_content: During the loading process of stochastic networks with turning delays, the originally efficient Dial algorithm is unable to properly handle the OD loading work where consideration of turning delay is needed. This is manifested as follows. (i) The size of turning delay cannot be reflected in the link likelihood values. And thus it cannot be reflected in the link weight and path selection probability. Ultimately, the impact of turning delay on flow assignment cannot be considered. (ii) Dial algorithm [20] is a link-based assignment method. The path variable does not appear in the middle section of the algorithm. This is exactly how the algorithm successfully avoids path enumeration. But it also makes it impossible to obtain directly the turning flow we needed. Therefore, the turning delay has an impact on the network load. Even though the shortest path from a certain origin point to the rest junctions is found accurately using the shortest path algorithm with turning delay, random network loading with turning delay cannot be achieved by directly employing the Dial algorithm. 

The path from junction r to link a=(i,j) is defined, which refers to the path setting out from r. It travels through a series of intermediate links, and ends at its destination j via starting point i of link a. 

The concept of effective path with turning delay is built upon the concept of path from junction to link. For a certain OD pair rs, the shortest path length from travel origin point r of OD to link a is denoted by r(a).
section_name: Weibull-based turning delay stochastic loading

section_content: That is to say, effective turning allows travellers to be further away from the starting point. A certain path connecting rs is valid if and only if every turning it contains is valid. 

The algorithm solving process is given combining the simple network shown in Figure 2. The link cost of the network is consistent with the Dial's example [20]. The main steps of the algorithm are as follows
section_name: Turning a→b is valid if and only if it satisfies r(a)<r(b).

section_content: The link cost is updated and the iteration direction based on the node-link-based method is determined. The major steps of the node-link-based algorithm are as follows. 

Step 1: Initialization. For 6r!R, based on t a (0) =t a (0) and d ab (0) =d ab (0). The length of the shortest path from r to all links is calculated using the shortest path algorithm with turning delay to obtain r(a). The stochastic flow assignment is performed once using the algorithm in the previous section to obtain the initial link flow x (1) and turning flow y (1). Let n=1. 

Step 2: Update. t a (n) =t a [x (n) ] and d ab (n) =d ab [y (n) ] are calculated based on link cost function to obtain each t (n) and d (n). 

Step 3: Direction finding. Stochastic flow assignment is performed once based on t (n) and d (n) to obtain each additional link flow x ^(n) and turning flow y ^(n). 

Step 4: Determination of new iteration point. Let x (n+1) =x n +m n (x ^(n) -x (n) ), y (n+1) =y n +m n ( y ^(n) -y (n ), where step size m n =1⁄(n+1). 

Step 5: Convergence detection. If ║x ^(n+1) -x (n) ║ 2 <f 1 and ║y ^(n+1) -y (n) ║ 2 <f 2, the algorithm is terminated. [x x (n+1), y (n+1) ] is the equilibrium solution. Otherwise, let n=n+1, and go to Step 2. 

Since the link cost and turning delay change with the flow in each iteration, the valid path set connecting a certain OD pair is variable in each iteration according to the definition of the valid path. The link flow obtained thereof is non-continuous, causing the convergence of the algorithm unable to be guaranteed. To overcome this difficulty, the valid path set connecting a certain OD pair can be considered unchangeable with the flow in each iteration. The valid path is determined by the cost under zero flow. The loading algorithm in each iteration process no longer redefines the valid path. Such a method optimizes the time efficiency of the algorithm while avoiding non-convergence.
section_name: Turning delay algorithm

section_name: NUMERICAL RESULTS

section_content: There are two routes between OD in the network shown in Figure 6. A(L 1,L 2 ) and B(L 1,L 3 ). And there is an overlapping link L 1 between routes A and B. Assuming that the link cost of L 1 is x 1, the turning cost from Step 4: Cumulative flow. Let x a =x a +x a r, y ab =y ab +y ab r. If r is the origin point of last OD, the algorithm terminates. Otherwise, let r be the origin point of next OD, and go to Step 1. 

The algorithm takes advantage of the link flow conservation. The sum of flows flowing into a link from different turnings, flows on the link and the sum of flows flowing out of the link from different turnings satisfy a distribution does not change with the path features, and set turning cost as 0, x 2 =1, x 3 =2. Figure 7 shows the performance of various selection models along with changes in x 1. The horizontal axis is the value of x 1. The vertical axis is the probability if x 1 is selected. As can be seen, the path selection probability slowly tends towards actual results with an increase in parameter b rs for MNW. Especially, when b rs =10, the relativity results of path selection are basically in line with the actual situation. Meanwhile, we also conducted comparative analysis on other algorithms using the Gumbel distribution. CNL model [10] flattens out as the parameter tends to 0, which performs well when the parameter is 0. 75; nevertheless, its probabilistic lower bound still has a relatively large error. Graphs of MNL [5], PSL [22] and C-Logit [20] models tend to be flat, which fail to reflect the relativity of path selection. On the other hand, changes for GNL [9] and PCL [13] are just the opposite to the actual selection, where the selection probability tends to 1 with the increase in parameter x 1. This is because the similarity parameter in the PCL model tends to 1, whereas the branching degree parameter in GNL model parameter tends to 0 with the increase in x 1, indicating that when two routes are highly similar, these two methods handle them as a single route. The comparison results show that the Weibull distribution-based turning delay method performs well in the handling of route relativity. When the relative difference of two routes is too small to matter for the users, the probabilities of being selected are the same for these two routes.
section_name: Link relativity analysis

section_content: We tested and compared the algorithm for solving of the Weibull type stochastic network loading problems with turning delays on actual network data sets of different sizes. The test process is as follows. For each network, the link-based turning delays stochastic network loading and the model established in this paper are applied to the same network, respectively. The link L 1 to link L 2 is 1, and the turning cost from link L 1 to link L 3 is 2, then the link costs of links L 2, L 3 are x 2, x 3, respectively. It can be obtained from the actual network analysis that: as L 1 increases, the probability for route A to be selected shall be gradually reduced. And when L 1 =0, the two paths do not overlap, and the probability of being selected for A is 100%. When L 1 approaches positive infinity, the probabilities of being selected equal for routes A and B, which are 50%. The route choice probability include turning delay in Equation 13 which can be expressed as
section_name: Large-scale network simulation

section_content: It can be seen that when x 1 →∞, the selection probability tends to 50%. And when x 1 =0, x 2 =x 3, the route selection probability depends on turning cost. When b rs =10, the probability for route A to be selected closes to 100%. 

To facilitate the analysis of the Weibull model, the network parameters in The performance of this paper is evaluated in comparison with Dial [32] and TALL [33] over a set of real networks which contain the number of nodes, links and turns as shown in Table 1. As can be seen from Table 1, TALL and our algorithm have better relative performance on a larger network. This is because the larger the network, the more the virtual nodes and links need to be added, the greater the scale of extended network relative to the original network, and the lower the efficiency of Dial algorithm based on the extended network. In addition, when the density of OD origin point in the network is very high, the advantages of TALL and our algorithm are somewhat weakened. The reason is that compared to the node-oriented Dial algorithm, TALL and our algorithm are link-oriented algorithms, so when the density of OD origin point is very high, the time needed to map the originally node-oriented OD origin and destination points on the corresponding links is rather long. However, it can be seen from Table 1, that our method is still more efficient than TALL on the loading speed.
section_name: /

section_content: This paper presents a Weibull distribution-based turning delay path flow assignment model, and gives the path selection scheme comprising turning constraints and solution algorithm. Contribution of the method lies in the derivation of the Weibull distribution-based node-link random loading mechanism of turning delay. The algorithm directly calculates the link and turning flows consistent with the path flow without enumerating the efficient and loading path flows. The computation takes advantage of the fact that the link flow is conserved, thus avoiding the storage of paths. In the large-scale network simulation experiment, we compared the actual traffic sampling data and the experiments were carried out on a PC of Intel Core(TM) i7-2600 CPU@3. 4GHz, 4GB RAM, and NUIDIA GeForce GTX 460. Test program is written in C#. 

Figure 8 is the flow simulation on road network conducted in the flow assignment simulation system. The red colour are the links where the flow is bigger than 2,500. The blue colour are the links where the flow is bigger than 250 and smaller than 2,500. The green colour are the links where the flow is smaller than 250. It can be seen from the actual flow distribution of road network that the cross-river section connecting the main urban areas has larger flows in the two major blocks connected across the river. Besides, urban centre, resort areas and train station surroundings are also large traffic flow areas. This indicates that the flow assignment method adopted in this paper can basically reflect the actual road traffic situations. Figure 9 shows the statistics of flow comparison after considering turning delays at the intersections. The horizontal axis is the traffic flow. The vertical axis is the number of vehicles passing per unit of time. As can be seen from the figure, consideration of turning delays occurring at intersections will impact the traffic flow of the entire network; such impact of turning delay is especially obvious for road sections at high levels of congestion. This indicates that the intersection delay greatly impacts the calculation of link cost as well as path selection in urban traffic network. P k rsprobability that a random individual travelling through OD pair rs chooses path k p k rsprobability of a user to select path k of OD pair rs q rs -path flow of OD pair rs r(a) -the shortest path length from the origin point to link a rs -OD pair S rs -expectation cost between OD pair rs T a -estimated costs on link a t a -ascertainable cost on flow of link a w a kproportional weight of link a of path k x a -link path flows y ab -turning path flows a k rssize parameter of Weibull distribution b rs -shape parameter of Weibull distribution c -factor of CF k d a,k rsassociative variable of path and link f -random error m n -step size p rs -location parameter of Weibull distribution { ab,k rsassociative variable of path and turning ~ab -weight value of turning a→b C -Gamma function result data of the simulation method in Hangzhou. The experimental results show that: (i) As a kind of particular increasing function, the variance of Weibull distributed cost could result in different route choice possibilities based on its length; as for all kinds of choice alternatives, however, the variance of Gumbel is identical. This is more in line with the actual situation, because the paths with larger actual cost should have greater error term of variance than those with smaller actual cost. (ii) Node-link-based stochastic loading method has more efficient loading speed, and it is also more suitable for running on larger traffic networks. Moreover, the running results of this method in a real-size network are basically consistent with the actual traffic flow situation. 

Although the model and algorithm proposed in this paper are remarkably effective in improving the route choice relativity and computing the turning delays in large-scale networks, as the Weibull distribution is still based on the assumption of independence, we failed to completely address the multi-route overlapping problem despite our efforts to improve its properties by adding overlap factor in the model. In addition, the issues like what kinds of impacts the changes in parameter b rs have on route choice are major topics we are going to study in the next step.
section_name: CONCLUSION