Welcome to the National Transport Library Catalogue

Normal view MARC view

Changing Assignment Algorithms : Price of Better Convergence Florian, Michael ; He, Shuguang

By: Contributor(s): Series: Transportation Research Record: Journal of the Transportation Research Board ; 2176Publication details: Washington DC Transportation Research Board, 2010Description: s. 67-75ISBN:
  • 9780309160452
Subject(s): Bibl.nr: VTI P8167:2176Location: TRBAbstract: The mainstay method of equilibrium assignment methods is based on adaptation of the linear approximation algorithm. Practically all commercial software packages for transportation planning offer a version of this algorithm. In the early days of personal computing, when random-access memory (RAM) was limited, this method was the most appropriate one to use because it requires little intermediate storage. As personal computers became more powerful and RAM became plentiful, the drawbacks of the linear approximation method became evident to practitioners. A measure of convergence is the relative gap, which measures the relative difference between total travel time and total travel time on the shortest paths. Relative gaps of less than 10 to the -4 power are difficult to reach with this method. Alternative assignment methods, based on algorithms that have better convergence rates, are known and can obtain finer solutions. Changing to new algorithms would appear to be a trivial task; however, it is not the case. The issues related to changing assignment algorithms pertain to the uniqueness of equilibrium paths, flows, and times. Examples of the expected changes in results for both standard multiclass assignments and for one complex model, which is equilibrated with feedback procedures, are presented. An adaptation of the projected gradient with path flows is used to represent the modern algorithms, which can reach relative gaps of 10 to the -6 power or better. Differences in relevant results are relatively small. Nevertheless, practitioners are careful to reproduce results and may face a challenge to accept slightly different results with a faster converging algorithm.
Item type: Reports, conferences, monographs
Holdings
Current library Status
Statens väg- och transportforskningsinstitut Available

The mainstay method of equilibrium assignment methods is based on adaptation of the linear approximation algorithm. Practically all commercial software packages for transportation planning offer a version of this algorithm. In the early days of personal computing, when random-access memory (RAM) was limited, this method was the most appropriate one to use because it requires little intermediate storage. As personal computers became more powerful and RAM became plentiful, the drawbacks of the linear approximation method became evident to practitioners. A measure of convergence is the relative gap, which measures the relative difference between total travel time and total travel time on the shortest paths. Relative gaps of less than 10 to the -4 power are difficult to reach with this method. Alternative assignment methods, based on algorithms that have better convergence rates, are known and can obtain finer solutions. Changing to new algorithms would appear to be a trivial task; however, it is not the case. The issues related to changing assignment algorithms pertain to the uniqueness of equilibrium paths, flows, and times. Examples of the expected changes in results for both standard multiclass assignments and for one complex model, which is equilibrated with feedback procedures, are presented. An adaptation of the projected gradient with path flows is used to represent the modern algorithms, which can reach relative gaps of 10 to the -6 power or better. Differences in relevant results are relatively small. Nevertheless, practitioners are careful to reproduce results and may face a challenge to accept slightly different results with a faster converging algorithm.