A path-based algorithm is developed for the static traffic assignment problem (TAP). In each iteration, it decomposes the problem into origin-destination (OD) pairs and solves each subproblem separately using the Wolfe reduced gradient (RG) method. This method reduces the dimensions of each single-OD subproblem by selecting a basic path between the OD pair and reformulating the subproblem in terms of the nonbasic paths. A column generation technique is included to avoid path enumeration in large scale networks. Also, some speed-up techniques are designed to improve the computational efficiency. The algorithm shifts flows from costlier paths to cheaper paths; however, the amount of flow shifted from a costlier path is proportional to not only the travel time but also the flow on the path. It is applied to the Philadelphia and Chicago test problems, while different strategies for choosing the basic paths are examined. The RG algorithm shows an excellent convergence to relative gaps of the order of 1.0E-14 when compared against several reference TAP algorithms.

Reduced gradient algorithm for user equilibrium traffic assignment problem / Babazadeh, Abbas; Javani, Babak; Gentile, Guido; Florian, Michael. - In: TRANSPORTMETRICA. A, TRANSPORT SCIENCE. - ISSN 2324-9935. - 16:3(2020), pp. 1111-1135. [10.1080/23249935.2020.1722279]

Reduced gradient algorithm for user equilibrium traffic assignment problem

Gentile, Guido;
2020

Abstract

A path-based algorithm is developed for the static traffic assignment problem (TAP). In each iteration, it decomposes the problem into origin-destination (OD) pairs and solves each subproblem separately using the Wolfe reduced gradient (RG) method. This method reduces the dimensions of each single-OD subproblem by selecting a basic path between the OD pair and reformulating the subproblem in terms of the nonbasic paths. A column generation technique is included to avoid path enumeration in large scale networks. Also, some speed-up techniques are designed to improve the computational efficiency. The algorithm shifts flows from costlier paths to cheaper paths; however, the amount of flow shifted from a costlier path is proportional to not only the travel time but also the flow on the path. It is applied to the Philadelphia and Chicago test problems, while different strategies for choosing the basic paths are examined. The RG algorithm shows an excellent convergence to relative gaps of the order of 1.0E-14 when compared against several reference TAP algorithms.
2020
large scale network; path-based algorithm; reduced gradient method; traffic assignment problem
01 Pubblicazione su rivista::01a Articolo in rivista
Reduced gradient algorithm for user equilibrium traffic assignment problem / Babazadeh, Abbas; Javani, Babak; Gentile, Guido; Florian, Michael. - In: TRANSPORTMETRICA. A, TRANSPORT SCIENCE. - ISSN 2324-9935. - 16:3(2020), pp. 1111-1135. [10.1080/23249935.2020.1722279]
File allegati a questo prodotto
File Dimensione Formato  
Babazadeh_Reduced-gradient-algorithm_2020.pdf

solo gestori archivio

Note: articolo
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.71 MB
Formato Adobe PDF
1.71 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1482386
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 20
social impact