Perturbed Utility Stochastic Traffic Assignment
- 1 July 2024
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 58 (4) , 876-895
Abstract
This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We formulate the PURC equilibrium assignment problem as a convex minimization problem and find a closed-form stochastic network loading expression that allows us to formulate the Lagrangian dual of the assignment problem as an unconstrained optimization problem. To solve this dual problem, we formulate a quasi-Newton accelerated gradient descent algorithm (qN-AGD*). Our numerical evidence shows that qN-AGD* clearly outperforms a conventional primal algorithm and a plain accelerated gradient descent algorithm. qN-AGD* is fast with a runtime that scales about linearly with the problem size, indicating that solving the perturbed utility assignment problem is feasible also with very large networks. Funding: This work has been financed by the European Union—NextGenerationEU.Keywords
All Related Versions
This publication has 53 references indexed in Scilit:
- A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium modelsEuropean Journal of Operational Research, 2021
- Evaluating a data-driven approach for choice set identification using GPS bicycle route choice data from AmsterdamTravel Behaviour and Society, 2018
- A Three-Operator Splitting Scheme and its Optimization ApplicationsSet-Valued and Variational Analysis, 2017
- On the Convergence of the Iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”Journal of Optimization Theory and Applications, 2015
- Method of Successive Weighted Averages (MSWA) and Self-Regulated Averaging Schemes for Solving Stochastic User Equilibrium ProblemNetworks and Spatial Economics, 2007
- Cyclic flows, Markov process and stochastic traffic assignmentTransportation Research Part B: Methodological, 1996
- An algorithm for the equilibrium assignment problem with random link timesNetworks, 1982
- Some developments in equilibrium traffic assignmentTransportation Research Part B: Methodological, 1980
- A probabilistic multipath traffic assignment model which obviates path enumerationTransportation Research, 1971
- Some methods of speeding up the convergence of iteration methodsUSSR Computational Mathematics and Mathematical Physics, 1964