J. Cent. South Univ. Technol. (2011) 18: 1765-1772

DOI: 10.1007/s11771-011-0900-6

Modified origin-based algorithm for traffic equilibrium assignment problems

ZHANG Tian-ran(张天然)¹, YANG Chao(杨超)², CHEN Dong-dong(陈冬栋)^{2, 3}

1. Shanghai City Comprehensive Transportation Planning Institute, Shanghai 200040, China;

2. School of Transportation Engineering, Tongji University, Shanghai 201804, China;

3. Shanghai Municipal Engineering Design Institute (Group) Co., Ltd., Shanghai 200092, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2011

Abstract: Key tactics of origin-based user equilibrium (OUE) algorithm was studied, which involved the algorithm procedure and several implementation issues. To speed up the convergence, update policies of flows, costs and bushes were proposed. The methods of step-size searching and bush construction are proved to be practical. The modified OUE algorithm procedure was also optimized to take the advantage of multi-thread process. Convergence performances were compared with those of other algorithms by different sizes of urban transportation networks. The result shows this modified OUE algorithm is more efficient and consumes less time to achieve the reasonable relative gap in practical applications.

Key words: traffic assignment; origin-based user equilibrium algorithm; acyclic network

1 Introduction

Traffic assignment is an important component of the traffic demand models. It describes how travelers select travel paths in the transportation network. If travelers have exact traffic information, they will choose the path which has the minimum cost. WARDROP [1] proposed the definition of user equilibrium (UE). BECKMANN  [2] used a mathematical model to describe the UE concept. In 1975, LEBLANCE [3] applied Frank-Wolfe (FW) algorithm to solve traffic assignment problems. This algorithm has been widely used since then. In order to seek more efficient assignment algorithms to deal with large-scale urban travel forecasting applications, researchers have been studying this problem for decades. Recently, some new algorithms have been proposed. The projected gradient method [4], the nonlinear- complementarity method [5], origin-based algorithm (OBA) [6], B algorithm [7], and the revised origin-based algorithm [8-9] are representatives.

Generally speaking, traffic assignment algorithms can be divided into three categories, namely, link-based algorithm, path-based algorithm and origin-based algorithm. It needs to point out that the origin-based algorithms proposed by BAR-GERA [6] and DIAL [7] have much higher efficiency compared with others, which causes this category of algorithms to become a new focus in traffic assignment research. The comparison between OBA and FW algorithms showed that OBA was more efficient. Based on the research of single origin toll model, DIAL developed a new assignment algorithm called algorithm B, which was superior to OBA. In 2007, BAR-GERA [10] proposed the TAPAS algorithm, which was more efficient than OBA as reported. After that, destination-based method [11], LUCE algorithm, and revised origin-based algorithm [9] also improved the convergence performance.

With the development of traffic planning software, the newest algorithms have been applied. CUBE used DANEVA’s improved FW algorithm [12]. TransCAD took algorithm B as a prototype to develop the origin user equilibrium algorithm (OUE). SATURN developed BAR-GERA’s OBA. Florian’s projected gradient method was compiled into EMME, and GENTILE’s LUCE algorithm was applied in VISUM.

Different commercial software developers and researchers indicated that their own algorithm had high efficiency compared with others. But in fact, many key details of implementation did not have an open discussion, and it was difficult for all the algorithms to have a common platform for comparison. The purpose of this work is to propose an modified origin-based algorithm for user equilibrium assignment (OUE) based on the previous researches, introduce implementation issues and compare the performance of different algorithms on the same platform.

2 Formulation and algorithm

The principle of solving the OUE problem is to decompose the whole problem into a sequence of single-origin sub-problems. In each of them, it is only necessary to assign travel demand from one given origin to all destinations. BAR-GERA pointed out that the BECKMANN’s mathematical model could be reformulated with origin-based link flow variables:

dw                                       (1a)

subjected to

                   (1b)

                        (1c)

                               (1d)

where A and N are the sets of links and nodes, R and S are the sets of origins and destinations, d_rs is the travel demand from origin r to destination s,  is the traffic flow on link (ij) from the origin r, x_ij is the total flow of link (ij), c_ij(?) is the link cost function which is monotonically increased, and O(j) and P(j) are the sets of links starting in or ending at node j.

Before describing the modified OUE algorithm, it needs to present an important UE property and some related definitions of origin-based algorithms.

Proposition 1: Acyclicity of user equilibrium

For the traffic assignment problem Eq.(1), the links that have positive flow at user equilibrium never form a direct cycle.

Proof: See Lemma 1-3 (Bar-Gera [6]) or Lemma 3 (Dial [7]). Also see Newell [13].

Definition 1: Bush of the origin r

A directed network is called a bush rooted at r if it is acyclic, and has at least one route from r to every other node.

Definition 2: Topological order

In a bush network, all nodes need to be numbered based on the topological structure. If i and j are the starting point and the finishing point of a link, respectively, i will appear before j in the topological order. It is noticed that the topological order of the only origin r is 1 in this bush.

There are two key points in the principle of origin-based algorithms:

1) The network connecting a given origin and all destinations is a directed and acyclic network that Bar-Gera called the restricting sub-network while Dial called the bush. It can efficiently find the max- and the min-path with the node topological order in this directed and acyclic network.

2) In a restricting sub-network (or a bush network), flows need to be shifted from expensive paths to cheap ones. Then, update the network to get cheaper paths under the condition that the network is still acyclic. DIAL’s algorithm and BAR-GERA’s one have the similar idea. The difference between them is that the former only shifts flows from the max-path to the min-path while the latter shifts from all other paths to the shortest one. Obviously, DIAL’s method is more concise and easier to achieve the equilibrium between the max- and the min-path.

Based on the above principles, the modified OUE algorithm proceeds as follows:

1) Initialization

Perform all-or-nothing assignments for each origin. Find the min-path trees of its origin r, and add all links of them into the bush. Besides, add new links into the bush, if the minimum cost from r to i is less than the cost to j. Then, sort all nodes in the bush of origin r according to the topological order.

2) Main loop

Step 1: Inner iterations

Flows shift within a given bush. It is useful to update the origin-based link flows while keeping the bushes fixed.

Step 1.1: For each origin, update flows in their current bush. Calculate the max- and min-paths of the given origin, and scan all nodes in descending topological order. If the costs of the max- and min-path to node j are the same, go to the next node. Otherwise, find the last common node of the two paths in the upstream of node j, get two new path sections between the common node and j, and then shift flows between two path sections. It will not go to Step 1.2 until finishing flow shifts of all bushes.

Step 1.2: Update costs and the derivative of costs of links.

If the convergence criterion of inner iterations is met, jump to Step 2. If not, go back to Step 1.1.

Step 2: Update all the bushes

Find new max- and min-paths for each bush after flow shifts, drop the links with zero flow from the bush, and add new links which meet the condition mentioned in “Initialization”. If a bush is updated, all nodes of it need to be resorted according to the topological order. When all the bushes achieve the convergence criterion of modified OUE algorithm, stop. Otherwise, go to Step 1.

According to the calculation process, the modified OUE algorithm is concise and easy to understand. However, to implement this algorithm efficiently, many issues should be discussed.

3 Implementation issues

3.1 Update policy of flows

The origin-based algorithms are to decompose the traffic assignment problem into a sequence of single- origin sub-problems. In each of them, it only needs to assign travel demand from one given origin to all destinations. How to update flows in sub-problems is important to the algorithm convergence. There are two kinds of update policies of flow. One kind is to shift flows in a given bush, and then update the bush network immediately. If this updated bush achieves the equilibrium solution, recalculate the values of link cost and cost derivative, and conduct another flow shifting for the next bush until all of them are finished. If not, continue to shift flows in the updated bush, and update over again until it achieves the equilibrium. Because of the recalculation of link costs, some equilibrium solutions achieved in the beginning will no longer satisfy the equilibrium condition. Therefore, in order to achieve the equilibrium solution of the whole problem, this kind of policy always needs many times of iterations in the main loop. In algorithm B, DIAL suggested not jumping to the next bush until the bush of current origin achieved the equilibrium under the condition of newly updated cost.

It is obvious that the equilibrium solution in a single bush is only a sub-problem of traffic assignment. In the first kind of update policy of flow, it tries to get the exact equilibrium solution of the given bush through inner iterations. Actually, it has little effect to accelerate the whole convergence. In their study on four-stage combinatorial models, BOYCE et al [14] proposed two ways to get the model convergence: in the main loop, one performed the shortest path assignment and the other got the exact equilibrium solution. The test result showed that the convergence speed of the former was much faster than the latter. In both combinatorial models and OUE algorithm, the relationship between sub-problems and the whole convergence speed is similar. Therefore, the second kind of policy for OUE algorithm is more efficient, as mentioned by NIE [8]. But different from the update policy of flow in this work, NIE noted only when the current bushes reached a relative equilibrium state through inner iterations, they could be updated. BAR-GERA indicated that the restricted sub-networks (or bushes) could achieve the steady state efficiently. It was advantageous to increase the number of times for inner iterations. But, we believed that update of bushes needs much less computation expense than flow shifting. It was not worth consuming a long time to get the partial equilibrium solution, which had no effect on accelerating the convergence speed. Therefore, in our modified OUE algorithm, it only shifted flows twice for a given bush, and the convergence accuracy was not considered. Besides, our algorithm was tested under different numbers of inner-iterations. The result shows in the same network the convergence speed does not become faster when inner-iteration times increases, and moreover, in different networks, the same inner-iteration times leads to different convergence performances. Therefore, to accelerate the whole convergence, enough relative gap of a bush for inner iterations should be discussed.

3.1.1 Flow update method between max- and min-path

Let  and c be the max- and min-path costs, z is the current flow solution and ?x_r the value of flow shifting. DIAL [7] used the first-order derivative expansion to express the approximate equation as

                       (2)

It is convenient to calculate the value of flow shifting from the max- to the min-path:

                                                      (3)

DIAL’s update method of flow can be explained in Fig.1. Under the current solution, costs vary widely between the max- and min-path. On the basis of the first-order derivative information to express the costs of two paths approximately, the approximate equilibrium solution D is got at the intersection of the two straight lines. This solution D is close to the actual equilibrium solution E. According to the difference between the current solution and D, the value of flows shifting, ?x, can be solved. After several iterative calculations, it is easy to equalize the costs of the max- and min-path.

If the link flow  of the max-path is smaller than ?x_r, let  where L_p is the max-path. In the calculation process, some links may belong to both the max-path to one destination and the min-path to another. The flow shifting of such links is invalid and unnecessary. Based on our tests, using DIAL’s update method of flow without the step-size searching is difficult to achieve the convergence criterion. To solve this problem, NIE proposed a heuristic step-size searching method [8]:

if 1.1G_LC, then λ=max(λ_L?0.8, 0.05)                         (4)

where G_L is the relative gap of the latest iteration, G_C is the current relative gap and λ_L is the step size of the latest flow shifting. In Eq.(4), NIE also limited the minimum step-size to 0.05. With this method, his algorithm achieved the convergence criterion, but in our implementation, it didn’t. It is probable that the differences of algorithms in calculation process and program codes lead to the different results.

Fig.1 DIAL’s update method of flow from max- to min-path

In our modified OUE algorithm, the social pressure method proposed by KUPISZEWSKA and VAN VLIET [15], is used to calculate the step size. Here λ denotes the step size. The condition is

                                               (5)

The searching method uses the Armijo rule, letting

λ=1,   …,  in turn. It is similar to the methods

in LUCE algorithm [11] and OBA [6]. But, our method makes use of their advantages, and then improves them.

3.1.2 Method of searching for common nodes

Before shifting flows in inner iterations, it is necessary to find out path segments belonging to the max- and min-path, respectively, of the same OD pair in a bush. The two path segments have the same starting point and finishing point. The common node downstream is called “Head” and the other one called “Tail”. The flows shifted are just between Head and Tail in the different path segments. There are two methods to find out the Tail node in descending topological order. In the first method, it defines one array as MinTree [|N|] and initializes to 0. Then, it scans the min-path from Head to origin r, adds all nodes encountered into the array, and sets their values to be 1. After that, another scan of the max-path from Head needs to be executed. In the second scan, if the node of the array value is 1, it is Tail. In the other method, it only scans one node for one time along the max-path from Head, in descending topological order. Then, check whether the nodes on the min-path are common to that one. If one node of the min-path meets the condition, it is Tail. If not, continue to have another scan along the max-path, and check the nodes on the min-path again. Compared with the second method, the first one only scans the min-path once and is easy to code. But it needs more memory consuming. In network tests, the two methods show similar efficiency on the convergence performance.

3.1.3 Calculation procedure of flow update

Step 1: Calculate the max- and min-paths of the bush, and get the max- and min-path costs ( and C_i) and the cost derivative values ( and ) from the origin to the node i. If for each node i, the difference between its max-cost and min-cost is less than the default

value, namely  (ε is a small positive

number), the flow update of this bush is finished. Else, go to Step 2.

Step 2: Scan the nodes of the bush in descending topological order. If links in the max-path and the min-path to node i are all the same, jump to scan node i+1. If not, go to Step 2.1.

Step 2.1: Set node i is Head, marking as “h”, in the path segments of its max-path and min-path. Find out the other common node upstream of the two paths, and set it as Tail, marked as “t”.

Step 2.2: Calculate the temporary value of flow shifting

Save the link flow shifting value  between the max- and the min-path from h to t. (If the link needs to shift flows for a second time, when scanning other nodes, the temporary value is accumulated.)

Step 3: The Armijo rule. Set λ=1,   …,

and modify the temporary value as  until it satisfies the condition:

Step 4: For all the links of the current bush, the flows to be shifted depend on the final values of flow shifting,

For the update part of flow, there are two key points to be supplemented. First, the max-path must be built on the links whose flows are larger than 0, so that the shift of flows makes sense and it can accelerate the convergence. Second, the residual link flows could affect bush update. It is possible that the link flow after shifting produces a very small value just because of the float number calculation in computer programs. To avoid this situation, it is necessary to set a precise value of link flows in the calculation process. According to several network tests, 1.0×10^-12 is reasonable. In some other cases, small values remained in the links are not caused by the float number calculation, but are the existing residual flows after shifting. As for this problem, the algorithm needs to ensure that link flows are shifted completely when executing the flow shifting process. Both of the two key points can affect the bush update and cause the algorithm unable to achieve the convergence criterion. FLORIAN proposed to directly remove small residual flows of each OD pair (for example the default value is smaller than 0.1) in the projected gradient method. Actually, this approach is not appropriate in OUE. Even the values of residual flows are very small, quantities of the residual flows of OD pairs will be cumulated and lead to a large value removed. Therefore, FLORIAN’s suggestion and ours are essentially different.

3.2 Update policy of cost and cost derivative

In addition to flow update policies, when to update link costs of the network is also important to the convergence for traffic assignment algorithms. Take FW algorithm as an example. There are two common policies of link cost update. One is the Gauss-Seidel method, which updates the link costs once the travel demand assignment from an origin to all destinations is finished. The other is to update link costs after all-or-nothing assignments for the whole network are finished. In literature, the Gauss-Seidel method is better for convergence. But practically in the execution course of Gauss-Seidel method, the increased times of cost update additionally consume more calculation expenses, which offsets the accelerated convergence speed of FW algorithm. Therefore, whether the Gauss-Seidel method could speed up the convergence depends on the characteristics of different algorithms. It needs to test in different networks to reach a conclusion.

In the modified OUE algorithm, according to several network tests, it comes to the conclusion: updating link costs immediately after finishing flow shifting of all bushes is advantageous to accelerate the convergence. But if the update cost derivatives after the flow shifting of all bushes is finished, it decelerates the whole speed obviously. This phenomenon may have some relationship with our improved update method of flow. However, in order to prepare for the construction of new bushes, the update of link costs and cost derivatives is required. This is because the construction of bushes needs accurate values of max- and min-path costs to ensure the acyclic property of each bush.

3.3 Update policy of bushes

3.3.1 Method to guarantee bushes acyclic

In the construction of bushes, maintaining their acyclic characteristic is an important feature of origin- based algorithms. Acyclic bushes can sort the topological order conveniently and calculate the max- and min-path efficiently. DIAL [7] indicated when adding link a_ij into the bush, the condition for maintaining its acyclic characteristic is

                                                    (6)

In fact this condition is not practical. NIE [8] pointed out that it could guarantee the bush acyclic only in the state of high accuracy equilibrium. But to achieve that state, it would greatly increase the sub-problem calculation expenses. Compared with that, the condition Bar-Gera proposed is reasonable:

                                                           (7)

NIE further revised Bar-Gera’s acyclic condition. He noted that some invalid links could be added into bushes according to Bar-Gera’s condition. The revised condition is

                                                   (8)

NIE proposed if the relationship Rule 1Rule 3=  was met, Rule 3 should be used in the construction of bushes. But according to our program tests, NIE’s conditions cannot accelerate the convergence efficiently. Therefore, the condition Rule 1Rule 3 is used in the modified OUE algorithm.

The further problem is how to use Rule 3. In the procedure of flow update, it is required to build max-path on links whose flow values are larger than 0. That means that the nodes belonging to the max-paths are only part of the node set of the bush. Therefore, Rule 3 cannot be used to the node whose flow value is 0. The node without flow may turn to be on the new min-path, after flow shifting and bush update. Calculating based on Rule 1 may destroy the acyclic characteristic. To avoid this, it must search for new nodes along the min-path, in descending topological order, from node i (or j) without flow. If a node p is found whose flow value is larger than 0, the max-path cost of node i (or j) is replaced by that of node p. This method causes the logical relation of the bush to be complicated. According to our tests, the method restricts adding new links and hinders the optimization of the bush. These deficiencies cause the accuracy of traffic assignment not to be high. The relative gap of them can only reach 1.0×10^-4 or 1.0×10^-5 to the utmost. Although the calculation accuracy is acceptable, the method is inadvisable because it hinders the optimization of the bush. Therefore, it is necessary to calculate the new max-path in the bush (regardless of flow values), so that Rule 3 can be directly used. In fact, the modified OUE algorithm needs to calculate two types of max-path. One is used for the flow shifting and the other for the construction of bushes.

3.3.2 Removal of links without flow

In order to maintain the acyclic characteristic and raise the efficiency of flow update, it also needs to remove links without flow in bushes before their update. The removal should not impair the connectivity of bushes. According to different types of nodes in the bush, the removal policies vary. If one node is flowed through by travel demand, delete links connecting to the node, which belong to non-min-path and have no flows. Otherwise, only retain links belonging to the min-path, and delete all other links connecting to the node. To accelerate the convergence, it is important to save the zero-flow links.

3.3.3 Reduction in unnecessary calculations

In the modified OUE algorithm, unnecessary calculations are minimized. For example, it does not need to resort the topological order of the bush after removal of zero-flow links, because the previous order is still valid. But, if new links are added into the bush, the recalculation is needed.

4 Numerical results

Several tests were performed to examine the performance of the modified OUE algorithm. Meanwhile, FW algorithm was also taken into account because of its wide application. In order to have a same platform for comparison, the programs (Win32 console program) of modified OUE and FW algorithm were written with C language environment, and the same data structure was used. In the min-path algorithm in FW double-end queue data structure was used. OBA was implemented in his own executable files. The computational environment was the HP XW Workstation with the CPU of 8-core 3.16 GHz, 32 GB RAM and the Operating System of Windows XP-64. This study used four typical networks which were downloadable at BAR-GERA’s website. Besides, in order to observe the efficiency difference under different network sizes, the networks of Huizhou City and Shanghai City were also used. Table 1 gives the statistics of networks for performance tests.

In the tests, all algorithms used the BPR link cost function:

                                                     (9)

where t is the link travel time, t₀ is the free-flow travel time, x is the link flow and c is the link capacity.

The relative gap was used to evaluate the performance of algorithms:

                                           (10)

In this expression, it takes all links into account, and calculates the total-cost difference between UE solution and AON solution under the current flow condition. If the difference is very small, it means that all users in the network can hardly reduce their travel costs by changing their paths. Under such conditions, the algorithm achieves the user equilibrium state.

4.1 Performance of modified OUE algorithm with multi-thread process

The procedure of modified OUE algorithm can be optimized to take the advantage of multi-thread process. To prove its performance, Table 2 compares OUE algorithm and that of multi-thread process. Computational times to achieve required relative gaps, using the two different algorithms, are given.

4.2 Convergence of different algorithms

In a traffic assignment problem, the relative gap should achieve less than 1.0×10^-4 to satisfy the accuracy requirement. Table 3 gives the computational times to achieve the relative gap of 1.0×10^-4, using different algorithms in four large urban networks. Figure 2 and Figure 3 show that it needs more time to achieve the relative gap of 1.0×10^{-4 in OBA than in FW algorithm. The high-efficiency of OBA only emerges in the later stage of the convergence. However, the modified OUE algorithm occupies the superiority in the entire convergence compared with FW algorithm. The OUE algorithm of TransCAD has the similar trends. Our optimized OUE algorithm is faster than that of TransCAD5.0 in the calculation speed. Using this algorithm, it takes only a few minutes to achieve the relative gap of 1.0×10-4 in large urban networks. Therefore, our algorithm can meet the needs of transportation model calculations.}

Generally speaking, the relative gap of the value less than 1.0×10^-6 has not been widely used in the practice. But, in the view of the study on the convergence property, it is worthwhile to observe the convergence speed. Figures 2 and 3 give the high-precision convergence trends in Chicago regional network and Philadelphia network. Although the OUE algorithm of TransCAD5.0 can achieve higher precision than 1.0×10^-6, its report file does not give the exact values about that. Therefore, in the two figures, the trend lines of TransCAD5.0 OUE algorithm can only be charted to the relative gap of 1.0×10^-6. In the view of later stage of the algorithm convergences, Bar-Gera’s OBA has a linear characteristic. Our OUE algorithm also shows the linear characteristic in the convergence process when tested in Philadelphia network, but in Chicago regional network, its convergence speed decelerates a little.

Table 1 Urban network sizes in algorithm tests

Table 2 Computation time of modified OUE with and w/o multi-thread process (s)

Table 3 Computational time of algorithms in large urban networks (G_R=1.0×10^-4) (s)

Fig.2 Convergence in Chicago regional network: (a) Full; (b) Partial

Fig.3 Convergence in Philadelphia network: (a) Full; (b) Partial

According to the convergence curves, the oscillation properties in the OUE algorithms are more obvious than that in the FW algorithm. Besides, the OUE algorithms’ solutions of low-precision are unstable. Therefore, the Caliper Company advises that the FW algorithm is more appropriate under the low-precision requirement. The OUE algorithms are used to solve the high-precision solution, whose relative gap is 1.0×10^-4 or less.

5 Conclusions

1) The method of step-size searching proposed in this work can guarantee the convergence and accelerate the speed.

2) The modified OUE algorithm can be partly optimized with multi-thread process.

3) The modified OUE algorithm can raise the efficiency of traffic assignment and have practical utility. One of its outstanding advantages is that it can save the last bushes and shift flows immediately after the warm-start, which saves the computing time greatly.

Acknowledgement

Special thanks to Yu (Marco) NIE from Northwest University, Zhong ZHOU from the Citilabs Company and Qi YANG from the Caliper Company for the discussion of traffic assignment algorithms.

References

[1] WARDROP J G. Some theoretical aspects of road traffic research [C]// Proceedings of the Institute of Civil Engineers Part II, London, 1952: 325-378.

[2] BECKMANN M, McGUIRE C B, WINSTEN C B. Studies in the economics of transportation [M]. New Haven, Connecticut: Yale University Press, 1956.

[3] LEBLANCE L J, MORLOK E K, PIERSKALLA W. An efficient approach to solving the road network equilibrium traffic assignment problem [J]. Transportation Research, 1975, 9(5): 309-318.

[4] FLORIAN M. New look at projected gradient method for equilibrium assignment [C]// Transportation Research Board Annual Meeting. Washington D C, 2009.

[5] OLARTE R, HAGHANI A, TOOBAIE S. A comparison between an origin-based method and a nonlinear-complementary method for solving the traffic assignment problem [C]// Transportation Research Board Annual Meeting. Washington D C, 2010.

[6] BAR-GERA H. Origin-based algorithm for the traffic assignment problem [J]. Transportation Science, 2002, 36(4): 398-417.

[7] DIAL R B. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration [J]. Transportation Research Part B, 2006, 40(10): 917-936.

[8] NIE Y. A note on Bar-Gera’s algorithm for the origin-based traffic assignment problem [J/OL]. Transportation Science, 2009.

[9] NIE Y. A class of bush-based algorithms for the traffic assignment problem [J]. Transportation Research Part B, 2010, 44(1): 73-89.

[10] BAR-GERA H. Traffic assignment by paired alternative segments [J]. Transportation Research Part B, 2010, 44(8/9): 1022-1046.

[11] GENTILE G. Linear user cost equilibrium: a new algorithm for traffic assignment [C]// Transportation Research Board Annual Meeting. Washington D C, 2008.

[12] DANEVA M. Improved Frank-Wolfe directions with applications to traffic problems [D]. Sweden: Linkoping University, 2003.

[13] NEWELL G F. Traffic flow on transportation networks [M]. Cambridge, MA: M.I.T. Press, 1980.

[14] BOYCE D, ZHANG Y, LUPA M. Introducing "feedback" into four-step travel forecasting procedure versus equilibrium solution of combined model [J]. Transportation Research Record, 1994, 1443: 65-74.

[15] KUPISZEWSKA D, VAN VLIET D. 101 uses for path-based assignment [C]// Transportation Planning Methods: Proceedings of Seminar C held at the PTRC Transport and Planning Summer Annual Meeting. U.K: University of Sussex, No. 434.

(Edited by YANG Bing)

Foundation item: Projects(70631002, 70701027) supported by the National Natural Science Foundation of China; Project(NCET-08-0406) supported by the Program for New Century Excellent Talents in Chinese University

Received date: 2010-09-06; Accepted date: 2011-02-11

Corresponding author: YANG Chao, Associate Professor, PhD; Tel: +86-21-69583704; E-mail: tongjiyc@163.com