Comparison of Convergence Speed among Conjugate Directions Traffic Assignment Algorithms

Document Type : Research Article

Authors

1 School of Civil Engineering, University of Tehran , Tehran, Iran

2 School of Civil Engineering, University of Tehran, Tehran, Iran

Abstract

The Traffic assignment problem in the transport networks is formulated as a convex optimization problem using simplifier assumptions. Link-based, path-based and bush-based algorithms have been presented to solve this problem, among which the link-based algorithm has found more applications thanks to its low memory requirements. The link-based algorithm of Frank-Wolf (FW) is yet amongst the most popular assignment algorithms, because of its simplicity as well as high convergence speed during the initial iterations. However, the low convergence rate of this algorithm near the optimal solution has driven many studies that focus on modifying the FW search direction, resulted in newer link-based algorithms. Among them are conjugate direction algorithms which are more effective and simply implementable. These algorithms include PARTAN, conjugate FW (CFW) and bi-conjugate FW (BFW). This paper uses the Chicago Regional and Sioux-Falls test networks to make direct comparisons among these algorithms with respect to the CPU time and iteration number needed to reach various accurate solutions. The results for Chicago show that, compared with the FW algorithm, the three algorithms CFW, PARTAN increase the convergence speed to the relative error of 10-5 (i.e. a stable solution) by about 89, 72 and 63%, respectively, while only the BFW can reach to a 10-6 relative error. Comparing the results from Sioux-Fall with those of Chicago demonstrates that the performance of the conjugate directions Algorithms improves as network size decreases.

Keywords

Main Subjects

References

[1] Y. Sheffi, Urban transportation networks, Prentice-Hall, Englewood Cliffs, NJ (1985).
[2] M.J. Beckmann, C.B. McGuire, C.B. Winsten, Studies in the economics of transportation,  (1955).
[3] M. Frank, P. Wolfe, An algorithm for quadratic programming, Naval research logistics quarterly, 3(1-2) (1956) 95-110.
[4] L.J. LeBlanc, E.K. Morlok, W.P. Pierskalla, An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation research, 9(5) (1975) 309-318.
[5] M. Patriksson, The traffic assignment problem—models and methods. VSP, Utrecht, Definition: where with the projection operator given by,  (1994).
[6] D.G. Luenberger, Y. Ye, Linear and nonlinear programming, 3rd edition, Springer (2008).
[7] L.J. LeBlanc, R.V. Helgason, D.E. Boyce, Improved efficiency of the Frank-Wolfe algorithm for convex network programs, Transportation Science, 19(4) (1985) 445-462.
[8] M. Florian, J. Guálat, H. Spiess, An efficient implementation of the “Partan” variant of the linear approximation method for the network equilibrium problem, Networks, 17(3) (1987) 319-339.
[9] Y. Arezki, D. Van Vliet, A full analytical implementation of the PARTAN/Frank–Wolfe algorithm for equilibrium assignment, Transportation Science, 24(1) (1990) 58-62.
[10] M. Fukushima, A modified Frank-Wolfe algorithm for solving the traffic assignment problem, Transportation Research Part B: Methodological, 18(2) (1984) 169-177.
[11] D. Hearn, S. Lawphongpanich, J.A. Ventura, Finiteness in restricted simplicial decomposition, Operations Research Letters, 4(3) (1985) 125-130.
[12] D.-H. Lee, Y. Nie, Accelerating strategies and computational studies of the Frank–Wolfe algorithm for the traffic assignment problem, Transportation Research Record, 1771(1) (2001) 97-105.
[13] M. Mitradjieva, P.O. Lindberg, The stiff is moving - conjugate direction Frank-Wolfe Methods with applications to traffic assignment, Transportation Science, 47(2) (2013) 280-293.
[14] J. Holmgren, P.O. Lindberg, Upright stiff: subproblem updating in the FW method for traffic assignment, EURO Journal on Transportation and Logistics, 3(3-4) (2014) 205-225.
[15] W.B. Powell, Y. Sheffi, The convergence of equilibrium algorithms with predetermined step sizes, Transportation Science, 16(1) (1982) 45-55.
[16] A. Weintraub, C. Ortiz, J. González, Accelerating convergence of the Frank-Wolfe algorithm, Transportation Research Part B: Methodological, 19(2) (1985) 113-122.
[17] A. Chen, Effects of Flow Update Strategies on Implementation of the Frank–Wolfe Algorithm for the Traffic Assignment Problem, Transportation research record, 1771(1) (2001) 132-139.
[18] M. Florian, I. Constantin, D. Florian, A new look at projected gradient method for equilibrium assignment, Transportation Research Record, 2090(1) (2009) 10-16.
[19] A. Kumar and S. Peeta, Slope-based path shift propensity algorithm for the static traffic assignment problem, International Journal for Traffic and Transport Engineering, 4(3) (2014) 297-319.
[20] D. Di Lorenzo, A. Galligari, and M. Sciandrone, A convergent and efficient decomposition method for the traffic assignment problem, Computational optimization and applications, 60(1) (2015) 151-170.
[21] J. Xie, Y. Nie, and X. Liu, A Greedy Path-Based Algorithm for Traffic Assignment, Transportation Research Record, 2672(48) (2018) 36-44.
[22] G. Gentile, Linear User Cost Equilibrium: a new algorithm for traffic assignment, Transportmetrica A, (2012) 15-54.
[23] A. Babazadeh, B. Javani, Comparison Between Path-based Algorithms for Traffic Assignment Problem, in:  Transportation Research Board 91st Annual Meeting, (2012)
[24] H. Bar-Gera, Origin-based algorithm for the traffic assignment problem, Transportation Science, 36(4) (2002) 398-417.
[25] R.B. Dial, A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration, Transportation Research Part B: Methodological, 40(10) (2006) 917-936.
[26] H. Bar-Gera, Traffic assignment by paired alternative segments, Transportation Research Part B: Methodological, 44(8-9) (2010) 1022-1046.
[27] J. Xie, and C. Xie, New insights and improvements of using paired alternative segments for traffic assignment. Transportation Research Part B: Methodological, 93 (2016) 406-424.
[28] D. Boyce, B. Ralevic-Dekic, H. Bar-Gera, Convergence of traffic assignments: how much is enough?, Journal of Transportation Engineering, 130(1) (2004) 49-55.
[29] Transportation networks for research. https://github.com/bstabler/TransportationNetworks. Accessed July, 20, 2019.
[30] LJ. LeBlanc, EK. Morlok, WP. Pierskalla, An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research, 9(5) (1975) 309–318.
[31] M. Florian, C. D. Morosan, on uniqueness and proportionality in multi-class equilibrium assignment, Transportation Research Part B: Methodological, 70 (2014) 173-185.‏
Amirkabir Journal of Civil Engineering
Volume 54, Issue 6
September 2022
Pages 2219-2236

Files

Share

How to cite

Statistics