English

运筹学学报 >

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

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

 

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

展开
  • 1. 南京师范大学数学科学学院, 江苏南京 210023
    2. 南京信息工程大学管理工程学院, 江苏南京 210044
    3. 北京航空航天大学数学科学学院, 北京 100191
韩德仁, E-mail: handr@buaa.edu.cn

收稿日期: 2022-05-13

  网络出版日期: 2023-06-13

基金资助

国家自然科学基金(11871279);国家自然科学基金(12131004);国家自然科学基金(12126603);国家自然科学基金(12001286);江苏省研究生科研与实践创新计划项目(SJCX22_0532)

收起

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

摘要

本文研究包含私人交通和公共交通工具的多模式交通均衡问题，将其建模成带线性不等式约束的可分单调变分不等式问题，并提出一种修正的交替方向乘子法进行求解。通过适当地修改子问题并加上一个简单的校正步，提出一种针对线性不等式约束问题的并行求解算法。在一般的假设条件下，证明了这个新算法的全局收敛性和次线性收敛速度，并把算法应用到交通模型中。

关键词： 交通均衡问题; 变分不等式; 交替方向乘子法; 全局收敛; 次线性收敛

本文引用格式

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

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

参考文献

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
文章导航

/

〈 〉