Changing Assignment Algorithms: Price of Better Convergence

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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01152922
  • Record Type: Publication
  • ISBN: 9780309160452
  • Report/Paper Numbers: 10-0525
  • Files: TRIS, TRB, ATRI
  • Created Date: Jan 25 2010 10:16AM