Research Article

Free to Read

An augmented Lagrangian origin-based algorithm for link-capacitated traffic assignment problem

Corresponding Author

Feng Shi

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Correspondence to: Feng Shi, School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China. E-mail: [email protected]Search for more papers by this author

Guang-ming Xu,

Guang-ming Xu

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Search for more papers by this author

Helai Huang,

Helai Huang

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Search for more papers by this author

Feng Shi,

Corresponding Author

Feng Shi

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Correspondence to: Feng Shi, School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China. E-mail: [email protected]Search for more papers by this author

Guang-ming Xu,

Guang-ming Xu

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Search for more papers by this author

Helai Huang,

Helai Huang

School of Traffic and Transportation Engineering, Central South University, Changsha, 410075 China

Search for more papers by this author

First published: 16 October 2014

https://doi.org/10.1002/atr.1287

Citations: 7

Share a link

Email
Wechat
Bluesky

Summary

The origin-based algorithm is embedded into the augmented Lagrangian method for the link-capacitated traffic assignment problem. In order to solve the “nonexistence” problem due to the second partial derivatives of the augmented Lagrangian function at some specific points, the approximate expressions of the second partial derivatives are amended in the origin-based algorithm. The graph of last common nodes is developed on the basis of the restricted single-origin network. A method is proposed for finding n–1 last common nodes of the restricted single-origin network, resulting in computational complexity of O(n²) in finding last common nodes. Numerical analysis on the Sioux Falls network and Chicago Sketch network demonstrated the effectiveness and characteristics of the proposed algorithm. Copyright © 2014 John Wiley & Sons, Ltd.

References

1 Larsson T, Patriksson M. Side constrained traffic equilibrium models–analysis, computation and applications. Transportation Research Part B 1999; 33: 233–264.
10.1016/S0191-2615(98)00024-1
Web of Science® Google Scholar
2 Daganzo CF. On the traffic assignment problem with flow dependent costs––I. Transportation Research 1977; 11(6): 433–437.
10.1016/0041-1647(77)90009-0
Web of Science® Google Scholar
3 Daganzo CF. On the traffic assignment problem with flow dependent costs––II. Transportation Research 1977; 11(6): 439–441.
10.1016/0041-1647(77)90010-7
Web of Science® Google Scholar
4 Boyce D, Janson BN, Eash RW. The effect on equilibrium trip assignment of different link congestion functions. Transportation Research 1981; 15A: 223–232.
10.1016/0191-2607(81)90003-0
Web of Science® Google Scholar
5 Hearn DW. Bounding flows in traffic assignment models. Research Report 80–4, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 1980.
Google Scholar
6 Inouye H. Traffic equilibrium and its solution in congested road networks. In Proceedings of IFAC Conference on Control in Transportation Systems, R Genser (eds). Elsevier: Amsterdam, 1987; 267–272.
Google Scholar
7 Prashker JN, Toledo T. Adaptation of the gradient projection algorithm for the traffic assignment problem with side constraints. Paper presented at the 80th Annual Meeting of the Transportation Record Board, Washington, 2001.
Google Scholar
8 Yang H, Yagar S. Traffic assignment and traffic control in general freeway-arterial corridor system. Transportation Research Part B 1994; 28: 463–486.
10.1016/0191-2615(94)90015-9
Web of Science® Google Scholar
9 Yang H, Yagar S. Traffic assignment and signal control in saturated road networks. Transportation Research Part A 1995; 29: 125–139.
CAS Web of Science® Google Scholar
10 Hearn DW, Ribera J. Bounded flow equilibrium problems by penalty methods. In Proceedings of IEEE International Conference on Circuits and Computers. Institute of Electrical and Electronics Engineers: New York, 1980; 162–166.
Google Scholar
11 Nie Y, Zhang HM, Lee DH. Models and algorithms for the traffic assignment problem with link capacity constraints. Transportation Research Part B 2004; 38: 285–312.
10.1016/S0191-2615(03)00010-9
Web of Science® Google Scholar
12 Patriksson M. The Traffic Assignment Problem–Models and Methods. VSP: Utrecht, Netherlands, 1994.
Google Scholar
13 Bar-Gera H. Origin-based algorithm for the traffic assignment problem. Transportation Science 2002; 36(4): 398–417.
10.1287/trsc.36.4.398.549
Web of Science® Google Scholar
14 Dial RB. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and numeration. Transportation Research Part B 2006; 40(10): 917–936.
10.1016/j.trb.2006.02.008
Web of Science® Google Scholar
15 Nie Y. A class of bush-based algorithms for the traffic assignment problem. Transportation Research Part B 2010; 44(1): 73–89.
10.1016/j.trb.2009.06.005
Web of Science® Google Scholar
16 Bar-Gera H. Traffic assignment by paired alternative segments. Transportation Research Part B 2010; 44(8–9): 1022–1046.
10.1016/j.trb.2009.11.004
Web of Science® Google Scholar
17 Nie Y. A note on Bar-Gera's algorithm for the origin-based traffic assignment problem. Transportation Science 2012; 46(1): 27–38.
10.1287/trsc.1110.0371
Web of Science® Google Scholar
18 Inoue S, Maruyama T. Computational experience on advanced algorithms for user equilibrium traffic assignment problem and its convergence error. In 8th International Conference on Traffic and Transportation Studies 2012. Changsha, China, vol. 43, August 1–3: 445–456.
Google Scholar
19 Boyles SD. Bush-based sensitivity analysis for approximating subnetwork diversion. Transportation Research Part B 2012; 46(1): 139–155.
10.1016/j.trb.2011.09.004
Web of Science® Google Scholar
20 Xie J, Nie YM, Yang X. Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem. Transportation Research Part B 2013; 56: 15–30.
10.1016/j.trb.2013.06.015
Web of Science® Google Scholar
21 Gentile G. Local user cost equilibrium: a bush-based algorithm for traffic assignment. Transportmetrica 2014; 10(1): 15–54.
Web of Science® Google Scholar
22 Gao L, Si B, Yang X, Sun H, Gao Z. A matrix method for finding last common nodes in an origin-based traffic assignment problem. Physica A 2012; 391(1–2): 285–290.
10.1016/j.physa.2011.07.048
Web of Science® Google Scholar
23 Wardrop JG. Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers 1952; Part II(1): 325–378.
Google Scholar
24 Bertsekas DP. Constrained optimization and Lagrange multiplier methods. Academic Press: San Diego, CA, 1982.
Google Scholar

Citing Literature

All articles

An augmented Lagrangian origin-based algorithm for link-capacitated traffic assignment problem

Summary

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

An augmented Lagrangian origin-based algorithm for link-capacitated traffic assignment problem

Summary

References

Citing Literature

References

Related

Information