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

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

运筹学学报 ›› 2023, Vol. 27 ›› Issue (2): 63-78.doi: 10.15960/j.cnki.issn.1007-6093.2023.02.004

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

王茂然¹, 蔡邢菊¹, 吴中明², 韩德仁³^,*()

1. 南京师范大学数学科学学院, 江苏南京 210023
2. 南京信息工程大学管理工程学院, 江苏南京 210044
3. 北京航空航天大学数学科学学院, 北京 100191

收稿日期:2022-05-13 出版日期:2023-06-15 发布日期:2023-06-13
通讯作者: 韩德仁 E-mail:handr@buaa.edu.cn
作者简介:韩德仁, E-mail: handr@buaa.edu.cn
基金资助:
国家自然科学基金(11871279);国家自然科学基金(12131004);国家自然科学基金(12126603);国家自然科学基金(12001286);江苏省研究生科研与实践创新计划项目(SJCX22_0532)

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

Maoran WANG¹, Xingju CAI¹, Zhongming WU², Deren HAN³^,*()

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:2022-05-13 Online:2023-06-15 Published:2023-06-13
Contact: Deren HAN E-mail:handr@buaa.edu.cn

摘要/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

中图分类号:

O221.2

王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.

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.

图/表 6

图1

图2

图3

图4

图5

表1

参考文献 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 [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

[1]	叶明露, 邓欢. 一种新的求解拟单调变分不等式的压缩投影算法[J]. 运筹学学报, 2023, 27(1): 127-137.
[2]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[3]	谢文蕙, 凌晨, 潘晨健. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用[J]. 运筹学学报, 2022, 26(3): 31-43.
[4]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[5]	张慧玲, 赛·闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.
[6]	单锡泉, 李梅霞, 刘瑾瑜. 求解张量随机互补问题的光滑牛顿算法[J]. 运筹学学报, 2022, 26(2): 128-136.
[7]	崔丽媛, 杜守强. 随机R₀张量互补问题的投影Levenberg-Marquardt方法[J]. 运筹学学报, 2021, 25(4): 69-79.
[8]	王双月, 罗自炎. 一类基于L_0/1软间隔损失函数的低秩支持张量机[J]. 运筹学学报, 2021, 25(3): 160-172.
[9]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[10]	王秀玲, 龚循华. 对称向量拟均衡问题有效解的存在性[J]. 运筹学学报, 2021, 25(1): 73-80.
[11]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[12]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[13]	陈彩华. 多块交替方向乘子法不收敛反例的几点注记[J]. 运筹学学报, 2019, 23(3): 135-140.
[14]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[15]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价