The Practical Benefits of the SATURN Origin-based Assignment Algorithm and Network Aggregation Techniques

This paper will describe how the Origin-Based Assignment (OBA) algorithm was developed at the University of Illinois at Chicago in the late 1990’s. This algorithm revolutionized traffic assignment in that it solved Wardrop Equilibrium to an accuracy limited only by the numerical accuracy of the computer and within comparable central processing unit (CPU) time to existing algorithms such as Frank-Wolfe (FW). The single-user class (SUC) algorithm, known as SATURN-OBA, was released in 2005 at the University of Chicago. Further research and development work extended the OBA theoretical framework for use in the multiple user class (MUC) assignments. The OBA-MUC algorithm was made available to SATURN users in 2008. The development of the MUC algorithm and its performance on ‘real-life’ networks was described in the 2009 European Transport Conference (ETC) Paper: "A New Implementation of Origin-Based Assignment Algorithm in SATURN’’. The paper also described a new Hybrid algorithm that combined the speed of Frank-Wolfe with the accuracy of OBA, which enabled very highly converged highway assignment solutions to be achieved without a significant increase in CPU overhead. The first part of this follow-up paper builds upon the work previously undertaken and examines the practical benefits of the OBA algorithm when embedded within fully WebTAG-compliant, Variable Demand Models. Comparisons are made between the relative performances of the OBA against the existing FW algorithm in terms of: (1) improvements in convergence in both the highway assignment and also supply-demand equilibrium; (2) the efficiency of ‘Warm Starting’ a new OBA assignment using stored flows and costs from an existing, converged solution rather than starting from free-flow conditions; and (3) faster secondary analysis using the path information retained by OBA. This paper will describe how the inherent advantages of OBA not only enable Supply-Demand %GAP convergence to be much lower than currently specified in WebTAG when compared to FW but also within substantially less CPU requirements. The impact of OBA on the TUBA-based economic appraisal will also be explored. The second part of the paper describes a new Network Aggregation Technique that was undertaken within the initial network building that analyzes the network structure to identify ‘chains of links’ that can be aggregated to provide a much more compact network definition.

Language

  • English

Media Info

  • Media Type: Digital/other
  • Features: Figures; References; Tables;
  • Pagination: 19p
  • Monograph Title: European Transport Conference, 2010 Proceedings

Subject/Index Terms

Filing Info

  • Accession Number: 01353915
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Oct 19 2011 12:52PM