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



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

Authors

Y Xiang, I Wright, Atkins, UK; D Van Vliet, H Bar-Gera, Ben-Gurion University of the Negev, IL; D Boyce, North Western University, US

Description

The paper describes the practical benefits of using the SATURN OBA algorithm in WebTAG-based Variable Demand Models and a new Network Aggregation Technique in SATURN that significantly reduces the computational time without any loss in accuracy.

Abstract

The Origin-Based Assignment (OBA) algorithm was developed by Prof. Hillel Bar-Gera, while a PhD student at the University of Illinois at Chicago in the late 1990?s. This algorithm revolutionised traffic assignment in that it solved Wardrop Equilibrium to an accuracy limited only by the numerical accuracy of the computer and within comparable CPU time to existing algorithms such as Frank-Wolfe (FW). The single-user class (SUC) algorithm, known as SATURN-OBA, was released in 2005 in collaboration with Hillel and the University of Chicago. Further research and development work - undertaken by Atkins and Dirck Van Vliet - 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 ETC Paper: ?A New Implementation of Origin-Based Assignment Algorithm in SATURN??. The paper also described a new Hybrid algorithm - combining the speed of Frank-Wolfe with the accuracy of OBA ? that 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:
? improvements in convergence in both the highway assignment and also supply-demand equilibrium;
? 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;
? faster secondary analysis using the path information retained by OBA.
The 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 - undertaken within the initial network building ? that analyses the network structure to identify ?chains of links? that can be aggregated to provide a much more compact network definition.
For example, the process combines intermediate links and nodes that have been coded by the user but are not needed at the same level of detail for the assignment(e.g. network shaping nodes, centroid connector stubs and separate bus lanes). Less obviously a node with 3 arms may be removed entirely and its input and output links replaced by pairs of links such that the total number of links is not increased. Once the assignment has been run on the aggregate network, the results are mapped on to the original network structure. In recent testing on a series of networks, the technique reduced the number of nodes by factors of up to 5 and the number of links by up to 50%. Assignment run times were typically reduced 4-fold, equivalent to performance gains offered by SATURN Multi-Core.
Further development work is underway to extend the technique to the multi-threaded version (SATURN Multi-Core) as well as OBA-MUC. The paper will describe the performance benefits of the network aggregation technique using the same case studies as outlined above.

Publisher

Association for European Transport