A New Implementation of Origin-based Assignment Algorithm in SATURN

A New Implementation of Origin-based Assignment Algorithm in SATURN


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



The path-based OBA 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). In other words, the algorithm enabled the traffic assignment to converge perfectly and, consequently, greatly improved the convergence between the SATURN?s internal assignment and simulation loops.
The single-user class (SUC) algorithm, known as SATURN-OBA, was released in 2005 as part of SATURN Version 10.5 in collaboration with Hillel and the University of Chicago. Since then, development work has continued to extend the OBA theoretical framework for use in the multiple user class (MUC) assignments.
The development of MUC OBA in SATURN is a natural extension of Hillel?s original ground-breaking work, and builds upon the multi-copy nature of Hillel?s SUC OBA implementation that considers origin-based link flows independently of all other origins. The principal extension to the framework involves a re-programming of the existing data structures to include UC specific components of the route choice costs.
This latest SATURN-OBA MUC implementation was released (in Beta form) as part of SATURN v10.8 during 2008 and has enabled the algorithm to be used by practitioners on real-life applications.
More recently a new hybrid algorithm - combining the speed of Frank-Wolfe with the accuracy of SATURN-OBA ? has been made available to enable very highly converged highway assignment solutions to be achieved without a significant increase in CPU overheads.
SATURN is based on two modules ? a pure assignment module based on ?separable? link cost-flow functions which uses either FW or OBA and a simulation stage which accounts for non-separable interactions between traffic streams at junctions and produces an updated set of separable cost-flow functions for the next assignment via ?diagonalisation.? These two modules are run in an iterative loop until (a) both modules have converged internally and (b) the cost-flow functions are stationary. Global convergence is restricted by the ?weakest link? of the three which, when using FW, is most generally the assignment; OBA removes this restriction.
The hybrid implementation selects the more efficient process for the assignment ? FW or OBA. Thus on early loops where the cost-flow functions are still changing rapidly there is no real need for a highly converged assignment so, at this point, it is more efficient to use FW which is faster than OBA over early iterations. However, once the loop has begun to stabilise it becomes advantageous to have a highly convergent assignment and OBA is superior. The hybrid algorithm sets an appropriate switch-over rule.
This hybrid approach brings together the advantages of both algorithms and leads to major improvements in computer runtimes and assignment accuracy. The switch to OBA guarantees greater accuracy in the final equilibrium assignment such that the impact of assignment noise is significantly reduced (compared to existing FW-based processes) and high levels of convergence may also be achieved in conjunction with external models such as demand models, economic evaluation models, etc. etc. OBA also ensures that any post-assignment analysis such as select link analysis is fully consistent with the assignment and these analyses are carried out much more efficiently using OBA solutions than FW
Comparisons between the SATURN assignment using FW, SATURN-OBA and the hybrid method will be presented to demonstrate the advantages of the new algorithms including the considerable benefits in convergence and post assignment analysis accuracy achieved within reasonable runtimes. The benefits of the improved accuracy in the assignment will be shown for real-life applications. The information on the SATURN-OBA system setup will be given as well as reporting on the memory requirement for running large SATURN models.


Association for European Transport