中文

Operations Research Transactions >

2023 , Vol. 27 >Issue 2: 63 - 78

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.02.004

First-order splitting algorithm for multi-model traffic equilibrium problems

Expand
  • 1. School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, Jiangsu, China
    2. School of Management Science and Engineering, Nanjing University of Information Science& Technology, Nanjing 210044, Jiangsu, China
    3. School of Mathematical Sciences, Beihang University, Beijing 100191, China

Received date: 2022-05-13

  Online published: 2023-06-13

Fold

Abstract

In this paper, we study the multi-model traffic equilibrium problem of private transportation and public transportation, which is modeled as a separable monotonous variational inequality problem with linear inequality constraints. We propose a modified alternating direction method of multipliers in a parallel way for the linear inequality constraint problem by modifying the subproblem appropriately and adding a simple correction step. Under general hypothetical conditions, the global convergence and sublinear convergence rate of this new algorithm are proved. Applying the algorithm to the traffic equilibrium shows its effectiveness.

Key words： traffic equilibrium problems; variational inequalities; alternating direction method of multipliers; global convergence; sublinear convergence

Cite this article

Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN . First-order splitting algorithm for multi-model traffic equilibrium problems[J]. Operations Research Transactions, 2023 , 27(2) : 63 -78 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.004

References

1 Wardorp J . Some theoretical aspects of road traffic research[J]. Proceedings of the Institute of Civil Engineers, 1952, 1 (5): 325- 378.
2 Yao J , Chen A , Ryu S , et al. A general unconstrained optimization formulation for the combined distribution and assignment problem[J]. Transportation Research Part B: Methodological, 2014, 59, 137- 160.
3 Liu Y , Guo X , Yang H . Pareto-improving and revenue-neutral congestion pricing schemes in two-mode traffic networks[J]. NETNOMICS: Economic Research and Electronic Networking, 2009, 10 (1): 123- 140.
4 Wong K I , Wong S C , Yang H , et al. Modeling urban taxi services with multiple user classes and vehicle modes[J]. Transportation Research Part B: Methodological, 2008, 42 (10): 985- 1007.
5 Gu Y , Cai X J , Han D R , et al. A tri-level optimization model for a private road competition problem with traffic equilibrium constraints[J]. European Journal of Operational Research, 2019, 273 (1): 190- 197.
6 Rockafellar R T . Lagrange multipliers and optimality[J]. SIAM Review, 1993, 35 (2): 183- 238.
7 Cai X J , Gu G Y , He B S , et al. A proximal point algorithm revisit on the alternating direction method of multipliers[J]. Science China Mathematics, 2013, 56 (10): 2179- 2186.
8 Han D R . A survey on some recent developments of alternating direction method of multipliers[J]. Journal of the Operations Research Society of China, 2022, 10 (1): 1- 52.
9 Boyd S , Parikh N , Chu E , et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2010, 3 (1): 1- 122.
10 Cai X J , Guo K , Jiang F , et al. The developments of proximal point algorithms[J]. Journal of the Operations Research Society of China, 2022, 10 (2): 197- 239.
11 Eckstein J , Bertsekas D P . On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operator[J]. Mathematical Programming, 1992, 55 (1): 293- 318.
12 Gabay D , Mercier B . A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and Mathematics with Applications, 1976, 2 (1): 17- 40.
13 He B S , Yang H , Wang S L . Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities[J]. Journal of Optimization Theory and Applications, 2000, 106 (2): 337- 355.
14 He B S , Yuan X M . On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method[J]. SIAM Journal on Numerical Analysis, 2012, 50 (2): 700- 709.
15 Chen C H , He B S , Ye Y Y , et al. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[J]. Mathematical Programming, 2016, 155 (A): 57- 59.
16 Cai X J , Han D R , Yuan X M . On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function[J]. Computational Optimization and Applications, 2017, 66 (1): 39- 73.
17 Jia Z H , Guo K , Cai X J . Convergence analysis of alternating direction method of multipliers for a class of separable convex programming[J]. Abstract and Applied Analysis, 2013, 2013 (2): 205- 215.
18 Han D R , Yuan X M , Zhang W X , et al. An ADM-based splitting method for separable convex programming[J]. Computational Optimization and Applications, 2013, 54 (2): 343- 369.
19 He B S , Hou L S , Yuan X M . On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming[J]. SIAM Journal on Optimization, 2015, 25 (4): 2274- 2312.
20 He B S , Tao M , Yuan X M . Alternating direction method with Gaussian back substitution for separable convex programming[J]. SIAM Journal on Optimization, 2012, 22 (2): 313- 340.
21 Bauschke H H , Combettes P L . Convex Analysis and Monotone Operator Theory in Hilbert Spaces[M]. New York: Springer, 2017: 52- 53.
22 Facchinei F , Pang J S . Finite-Dimensional Variational Inequalities and Complementarity Problems-Volume I[M]. New York: Springer, 2003: 9- 10.
23 He B S , Xu M H . A general framework of contraction methods for monotone variational inequalities[J]. Pacific Journal of Optimization, 2008, 4 (2): 195- 212.
24 He B S , Yuan X M . Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective[J]. SIAM Journal on Imaging Sciences, 2012, 5 (1): 119- 149.
25 Han D R , Hong K L . Solving non-additive traffic assignment problems: A descent method for co-coercive variational inequalities[J]. European Journal of Operational Research, 2004, 159 (3): 529- 544.
Options
Outlines

/

〈 〉