运筹学学报 ›› 2023, Vol. 27 ›› Issue (2): 63-78.doi: 10.15960/j.cnki.issn.1007-6093.2023.02.004
收稿日期:
2022-05-13
出版日期:
2023-06-15
发布日期:
2023-06-13
通讯作者:
韩德仁
E-mail:handr@buaa.edu.cn
作者简介:
韩德仁, E-mail: handr@buaa.edu.cn基金资助:
Maoran WANG1, Xingju CAI1, Zhongming WU2, Deren HAN3,*()
Received:
2022-05-13
Online:
2023-06-15
Published:
2023-06-13
Contact:
Deren HAN
E-mail:handr@buaa.edu.cn
摘要:
本文研究包含私人交通和公共交通工具的多模式交通均衡问题,将其建模成带线性不等式约束的可分单调变分不等式问题,并提出一种修正的交替方向乘子法进行求解。通过适当地修改子问题并加上一个简单的校正步,提出一种针对线性不等式约束问题的并行求解算法。在一般的假设条件下,证明了这个新算法的全局收敛性和次线性收敛速度,并把算法应用到交通模型中。
中图分类号:
王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[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.
表1
MADM ($ q=w=0.38 $) 计算得到的各路段交通流量(四舍五入取整数部分)"
路段 | 私人交通流量 | 公共交通流量 | 路段 | 私人交通流量 | 公共交通流量 | |
960 | 1 920 | 5 050 | 10 100 | |||
1 900 | 3 800 | 4 170 | 8 340 | |||
2 360 | 4 720 | 1 030 | 2 060 | |||
1 830 | 3 660 | 2 220 | 4 440 | |||
3 070 | 6 140 | 4 650 | 9 300 | |||
1 120 | 2 240 | 560 | 1 120 | |||
700 | 1 400 | 1 600 | 3 200 | |||
2 120 | 4 240 | 1 540 | 3 080 | |||
2 580 | 5 160 | 2 220 | 4 440 | |||
790 | 1 580 | 1 030 | 2 620 | |||
2 480 | 4 960 | 1 630 | 3 260 | |||
3 690 | 7 380 | 1 360 | 2 720 | |||
2 410 | 4 820 | 920 | 1 840 | |||
3 850 | 7 700 | 1 400 | 2 800 |
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] | 叶明露, 邓欢. 一种新的求解拟单调变分不等式的压缩投影算法[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] | 崔丽媛, 杜守强. 随机R0张量互补问题的投影Levenberg-Marquardt方法[J]. 运筹学学报, 2021, 25(4): 69-79. |
[8] | 王双月, 罗自炎. 一类基于L0/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. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||