1. Computing Dynamic User Equilibrium on Large-Scale Networks Without Knowing Global Parameters
- Author
-
Duong Viet Thong, Phan Tu Vuong, Aviv Gibali, Mathias Staudigl, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
Mathematical optimization ,Computer Networks and Communications ,Computer science ,Computation ,WAVES ,0211 other engineering and technologies ,Scale (descriptive set theory) ,Systems and Control (eess.SY) ,02 engineering and technology ,Electrical Engineering and Systems Science - Systems and Control ,TRAFFIC ASSIGNMENT ,Operator (computer programming) ,Dynamic Traffic Assignment ,Artificial Intelligence ,Fixed-point iteration ,CONVERGENCE ,0502 economics and business ,Convergence (routing) ,FOS: Electrical engineering, electronic engineering, information engineering ,FOS: Mathematics ,Mathematics - Optimization and Control ,FORMULATION ,Strong Convergence ,050210 logistics & transportation ,021103 operations research ,ALGORITHMS ,05 social sciences ,Fixed Point Iteration ,SIMULTANEOUS ROUTE ,OPERATOR ,EXISTENCE ,MODEL ,Optimization and Control (math.OC) ,Path (graph theory) ,A priori and a posteriori ,Solution concept ,Software - Abstract
Dynamic user equilibrium (DUE) is a Nash-like solution concept describing an equilibrium in dynamic traffic systems over a fixed planning period. DUE is a challenging class of equilibrium problems, connecting network loading models and notions of system equilibrium in one concise mathematical framework. Recently, Friesz and Han introduced an integrated framework for DUE computation on large-scale networks, featuring a basic fixed-point algorithm for the effective computation of DUE. In the same work, they present an open-source MATLAB toolbox which allows researchers to test and validate new numerical solvers. This paper builds on this seminal contribution, and extends it in several important ways. At a conceptual level, we provide new strongly convergent algorithms designed to compute a DUE directly in the infinite-dimensional space of path flows. An important feature of our algorithms is that they give provable convergence guarantees without knowledge of global parameters. In fact, the algorithms we propose are adaptive, in the sense that they do not need a priori knowledge of global parameters of the delay operator, and which are provable convergent even for delay operators which are non-monotone. We implement our numerical schemes on standard test instances, and compare them with the numerical solution strategy employed by Friesz and Han., This paper replaces and extends the previous work arXiv:1810.00777. The paper is accepted for publication at Networks and Spatial Economics
- Published
- 2021