In this work, we present an algorithm for the traffic assignment problem formulated as convex minimization problem whose variables are the path flows. The algorithm is a path equilibration algorithm, i.e. an algorithm where at each iteration only two variables are updated by means of an inexact line search along a feasible and descent direction having only two nonzero elements. The main features of the algorithm are the adoption of an initial tentative stepsize based on second-order information and of a suitable strategy (using an adaptive column generation technique) to select the variables to be updated. The algorithm is an inexact Gauss–Seidel decomposition method whose convergence follows from results recently stated by the authors requiring that the column generation procedure is applied within a prefixed number of iterations. The results of an extensive computational experience performed on small, medium and large networks show the effectiveness of the method compared with state-of-the-art algorithms.

A convergent and fast path equilibration algorithm for the traffic assignment problem / Galligari, A.; Sciandrone, M.. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - 33:2(2018), pp. 354-371. [10.1080/10556788.2017.1332621]

A convergent and fast path equilibration algorithm for the traffic assignment problem

Sciandrone M.
2018

Abstract

In this work, we present an algorithm for the traffic assignment problem formulated as convex minimization problem whose variables are the path flows. The algorithm is a path equilibration algorithm, i.e. an algorithm where at each iteration only two variables are updated by means of an inexact line search along a feasible and descent direction having only two nonzero elements. The main features of the algorithm are the adoption of an initial tentative stepsize based on second-order information and of a suitable strategy (using an adaptive column generation technique) to select the variables to be updated. The algorithm is an inexact Gauss–Seidel decomposition method whose convergence follows from results recently stated by the authors requiring that the column generation procedure is applied within a prefixed number of iterations. The results of an extensive computational experience performed on small, medium and large networks show the effectiveness of the method compared with state-of-the-art algorithms.
2018
column generation; decomposition methods; traffic assignment; user equilibrium
01 Pubblicazione su rivista::01a Articolo in rivista
A convergent and fast path equilibration algorithm for the traffic assignment problem / Galligari, A.; Sciandrone, M.. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - 33:2(2018), pp. 354-371. [10.1080/10556788.2017.1332621]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/1625731
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 14
social impact