Modified origin-based algorithm for traffic equilibrium assignment problems

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.

Keywords

traffic assignment / origin-based user equilibrium algorithm / acyclic network

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] BeckmannM., McGuireC. B., WinstenC. B.Studies in the economics of transportation [M], 1956, New Haven, Connecticut, Yale University Press

[3] LeblanceL. J., MorlokE. K., PierskallaW.. 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-GeraH.. Origin-based algorithm for the traffic assignment problem [J]. Transportation Science, 2002, 36(4): 398-417

[7] DialR. 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] NieY.. A class of bush-based algorithms for the traffic assignment problem [J]. Transportation Research Part B, 2010, 44(1): 73-89

[10] Bar-GeraH.. 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] DanevaM.Improved Frank-Wolfe directions with applications to traffic problems [D], 2003, Sweden, Linkoping University

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

[14] BoyceD., ZhangY., LupaM.. 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.