Cost Scaling Based Successive Approximation Algorithm for the Traffic Assignment Problem

This paper presents a cost scaling based successive approximation based successive approximation algorithm to solve the user equilibrium traffic assignment problem (TAP) by solving successively refining for e-optimal flows by successively refining e-optimality. As e reduces to zero, the optimal user equilibrium solution is reached. The proposed method is a variation of the bush-based algorithm, and also a variation of the min-mean cycle algorithm solving the min-cost flow (MCF) by successive approximation. In the context of TAP, the restricted master problem (traffic equilibrium restricted on a bush) in a successive approximation is solved to e-optimality before the reconstruction of bushes. It is shown that the proposed successive approximation method can reduce the number of flow operations substantially in contrast to a generic bush algorithm, as the former operates flows on a set of selected cycles with relatively high quality. Further, the bushes can be reconstructed effectively provided that the restricted master problem is not solved perfectly, by leveraging the e-optimality condition. As a result, the algorithm can obtain a highly precise solution with faster convergence on a large-scale network compared to a generic bush algorithm.

• Supplemental Notes:
  • This paper was sponsored by TRB committee ADB30(2) Network Equilibrium Modeling. Alternate title: Cost Scaling-Based Successive Approximation Algorithm for Traffic Assignment Problem.
• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Zheng, Hong
  • Peeta, Srinivas
• Conference:
  • Transportation Research Board 93rd Annual Meeting
  • Location: Washington DC
  • Date: 2014-1-12 to 2014-1-16
• Date: 2014

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: 20p
• Monograph Title: TRB 93rd Annual Meeting Compendium of Papers

Subject/Index Terms

• TRT Terms: Algorithms; Costs; Highway operations; Traffic assignment; Traffic equilibrium; Traffic flow
• Uncontrolled Terms: User equilibrium
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01514997
• Record Type: Publication
• Report/Paper Numbers: 14-1773
• Files: TRIS, TRB, ATRI
• Created Date: Feb 21 2014 3:16PM