多模式交通均衡问题的一阶分裂算法

doi:10.15960/j.cnki.issn.1007-6093.2023.02.004

Abstract

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

CLC Number:

O221.2

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.

Figures/Tables 6

路段	私人交通流量	公共交通流量	路段	私人交通流量	公共交通流量
$1 [1, 2]$	960	1 920	$15 [5, 6]$	5 050	10 100
$2 [1, 4]$	1 900	3 800	$16 [5, 8]$	4 170	8 340
$3 [1, 5]$	2 360	4 720	$17 [6, 3]$	1 030	2 060
$4 [2, 1]$	1 830	3 660	$18 [6, 5]$	2 220	4 440
$5 [2, 3]$	3 070	6 140	$19 [6, 9]$	4 650	9 300
$6 [2, 5]$	1 120	2 240	$20 [7, 4]$	560	1 120
$7 [3, 2]$	700	1 400	$21 [7, 5]$	1 600	3 200
$8 [3, 5]$	2 120	4 240	$22 [7, 8]$	1 540	3 080
$9 [3, 6]$	2 580	5 160	$23 [8, 5]$	2 220	4 440
$10 [4, 1]$	790	1 580	$24 [8, 7]$	1 030	2 620
$11 [4, 5]$	2 480	4 960	$25 [8, 9]$	1 630	3 260
$12 [4, 7]$	3 690	7 380	$26 [9, 5]$	1 360	2 720
$13 [5, 2]$	2 410	4 820	$27 [9, 6]$	920	1 840
$14$ [5, 4]	3 850	7 700	$28 [9, 8]$	1 400	2 800

References 25

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. doi: 10.1016/j.trb.2013.11.007
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. doi: 10.1007/s11066-008-9018-x
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. doi: 10.1016/j.trb.2008.03.004
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. doi: 10.1016/j.ejor.2018.07.041
6	Rockafellar R T . Lagrange multipliers and optimality[J]. SIAM Review, 1993, 35 (2): 183- 238. doi: 10.1137/1035044
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. doi: 10.1007/s11425-013-4683-0
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. doi: 10.1007/s40305-021-00368-3
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. doi: 10.1561/2200000016
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. doi: 10.1007/s40305-021-00352-x
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. doi: 10.1016/0898-1221(76)90003-1
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. doi: 10.1023/A:1004603514434
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. doi: 10.1137/110836936
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. doi: 10.1007/s10589-016-9860-y
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. doi: 10.1007/s10589-012-9510-y
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. doi: 10.1137/130922793
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. doi: 10.1137/110822347
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. doi: 10.1137/100814494
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. doi: 10.1016/S0377-2217(03)00423-5

[1]	Minglu YE, Huan DENG. A new projection and contraction algorithm for solving quasimonotone variational inequalities [J]. Operations Research Transactions, 2023, 27(1): 127-137.
[2]	LIU Pengjie, JIANG Xianzhen, SONG Dan. A class of spectral conjugate gradient method with sufficient descent property [J]. Operations Research Transactions, 2022, 26(4): 87-97.
[3]	Wenhui XIE, Chen LING, Chenjian PAN. A tensor completion method based on tensor train decomposition and its application in image restoration [J]. Operations Research Transactions, 2022, 26(3): 31-43.
[4]	Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization [J]. Operations Research Transactions, 2022, 26(2): 64-72.
[5]	Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem [J]. Operations Research Transactions, 2022, 26(2): 128-136.
[6]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[7]	WANG Shuangyue, LUO Ziyan. Low rank support tensor machine based on L_0/1 soft-margin loss function [J]. Operations Research Transactions, 2021, 25(3): 160-172.
[8]	LI Chaoqiong, LI Feng. A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities [J]. Operations Research Transactions, 2020, 24(1): 101-114.
[9]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[10]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[11]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[12]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[13]	FENG Junkai, ZHANG Haibin, QIN Yuan, ZHANG Kaili. An inexact parallel alternating direction method for structured variational inequalities [J]. Operations Research Transactions, 2018, 22(2): 18-30.
[14]	YANG Junfeng. An algorithmic review for total variation regularized data fitting problems in image processing [J]. Operations Research Transactions, 2017, 21(4): 69-83.
[15]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 25

Related Articles 15

Recommended Articles 0

Metrics

Comments