Home > Research > Publications & Outputs > Numerical stability of path-based algorithms fo...

Research

Associated organisational units

Electronic data

  • FixingPG

    Rights statement: This is an Accepted Manuscript of an article published by Taylor & Francis Group in Optimization Methods and Software on 03/06/2015, available online: http://www.tandfonline.com/10.1080/10556788.2015.1047018

    Accepted author manuscript, 490 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Numerical stability of path-based algorithms for traffic assignment

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Numerical stability of path-based algorithms for traffic assignment. / Perederieieva, Olga; Ehrgott, Matthias; Raith, Andrea et al.
In: Optimization Methods and Software, Vol. 31, No. 1, 01.2016, p. 53-67.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Perederieieva, O, Ehrgott, M, Raith, A & Wang, JYT 2016, 'Numerical stability of path-based algorithms for traffic assignment', Optimization Methods and Software, vol. 31, no. 1, pp. 53-67. https://doi.org/10.1080/10556788.2015.1047018

APA

Perederieieva, O., Ehrgott, M., Raith, A., & Wang, J. Y. T. (2016). Numerical stability of path-based algorithms for traffic assignment. Optimization Methods and Software, 31(1), 53-67. https://doi.org/10.1080/10556788.2015.1047018

Vancouver

Perederieieva O, Ehrgott M, Raith A, Wang JYT. Numerical stability of path-based algorithms for traffic assignment. Optimization Methods and Software. 2016 Jan;31(1):53-67. Epub 2015 Jun 3. doi: 10.1080/10556788.2015.1047018

Author

Perederieieva, Olga ; Ehrgott, Matthias ; Raith, Andrea et al. / Numerical stability of path-based algorithms for traffic assignment. In: Optimization Methods and Software. 2016 ; Vol. 31, No. 1. pp. 53-67.

Bibtex

@article{a7deca81bb044f0795435cf868ae1e89,
title = "Numerical stability of path-based algorithms for traffic assignment",
abstract = "In this paper we study numerical stability of path-based algorithms for the traffic assignment problem. This type of methods are based on decomposition of the original problem into smaller sub-problems which are optimised sequentially. Previously, path-based algorithms were numerically tested only in the setting of moderate requirements to the level of solution precision. In this study we analyse convergence of these methods when convergence measureapproaches machine epsilon of IEEE double precision format. In particular, we demonstrate that the straightforward implementation of one of the algorithms of this group (projected gradient) suffers from loss of precision and is not able to converge to highly precise solution. We propose a way to solve this problem and test the proposed fixed version of the algorithm on various benchmark instances.",
keywords = "traffic assignment, path-based algorithms, convergence, numerical stability, floating point arithmetic",
author = "Olga Perederieieva and Matthias Ehrgott and Andrea Raith and Wang, {Judith Y. T.}",
note = "This is an Accepted Manuscript of an article published by Taylor & Francis Group in Optimization Methods and Software on 03/06/2015, available online: http://www.tandfonline.com/10.1080/10556788.2015.1047018",
year = "2016",
month = jan,
doi = "10.1080/10556788.2015.1047018",
language = "English",
volume = "31",
pages = "53--67",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",
number = "1",

}

RIS

TY - JOUR

T1 - Numerical stability of path-based algorithms for traffic assignment

AU - Perederieieva, Olga

AU - Ehrgott, Matthias

AU - Raith, Andrea

AU - Wang, Judith Y. T.

N1 - This is an Accepted Manuscript of an article published by Taylor & Francis Group in Optimization Methods and Software on 03/06/2015, available online: http://www.tandfonline.com/10.1080/10556788.2015.1047018

PY - 2016/1

Y1 - 2016/1

N2 - In this paper we study numerical stability of path-based algorithms for the traffic assignment problem. This type of methods are based on decomposition of the original problem into smaller sub-problems which are optimised sequentially. Previously, path-based algorithms were numerically tested only in the setting of moderate requirements to the level of solution precision. In this study we analyse convergence of these methods when convergence measureapproaches machine epsilon of IEEE double precision format. In particular, we demonstrate that the straightforward implementation of one of the algorithms of this group (projected gradient) suffers from loss of precision and is not able to converge to highly precise solution. We propose a way to solve this problem and test the proposed fixed version of the algorithm on various benchmark instances.

AB - In this paper we study numerical stability of path-based algorithms for the traffic assignment problem. This type of methods are based on decomposition of the original problem into smaller sub-problems which are optimised sequentially. Previously, path-based algorithms were numerically tested only in the setting of moderate requirements to the level of solution precision. In this study we analyse convergence of these methods when convergence measureapproaches machine epsilon of IEEE double precision format. In particular, we demonstrate that the straightforward implementation of one of the algorithms of this group (projected gradient) suffers from loss of precision and is not able to converge to highly precise solution. We propose a way to solve this problem and test the proposed fixed version of the algorithm on various benchmark instances.

KW - traffic assignment

KW - path-based algorithms

KW - convergence

KW - numerical stability

KW - floating point arithmetic

U2 - 10.1080/10556788.2015.1047018

DO - 10.1080/10556788.2015.1047018

M3 - Journal article

VL - 31

SP - 53

EP - 67

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 1

ER -