﻿ 基于BFGS公式的改进截断拟牛顿法在随机用户均衡问题上的应用
 文章快速检索 高级检索
 山东大学学报(工学版)  2018, Vol. 48 Issue (1): 36-41  DOI: 10.6040/j.issn.1672-3961.0.2016.408 0

### 引用本文

LIU Jianmei, MA Shuaiqi. A modified truncated quasi-Newton method based on BFGS formula for the stochastic user equilibrium problem[J]. Journal of Shandong University (Engineering Science), 2018, 48(1): 36-41. DOI: 10.6040/j.issn.1672-3961.0.2016.408.

### 文章历史

A modified truncated quasi-Newton method based on BFGS formula for the stochastic user equilibrium problem
LIU Jianmei, MA Shuaiqi
Department of Mathematics, Jining University, Jining 273155, Shandong, China
Abstract: According to the characteristics of stochastic user equilibrium problems, a modified truncated quasi-Newton (MTQN) method was constructed based on the BFGS correction formula and Armijo line search. The construction process of truncated quasi-Newton equation and the concrete steps of the MTQN algorithm were introduced. The convergence and two issues were presented for the characteristics of stochastic user equilibrium model. One numerical example was solved by the MTQN algorithm, and the results were compared with the modified truncated Newton (MTN) method, which showed that the MTQN was superior to the MTN in both iteration number and absolute error. The modified truncated quasi-Newton method could avoid the computation of the Hessian matrix and could be also applied to solve some special problems when the Hessian matrix was not positive definite.
Key words: BFGS formula    stochastic user equilibrium    truncated quasi-Newton method    condition number    Armijo condition
0 引言

1 基于BFGS公式的改进截断拟牛顿法

 $\begin{array}{l} \mathop {\min }\limits_{x \in {{\bf{R}}^n}} \;\;f\left( \mathit{\boldsymbol{x}} \right),\\ {\rm{s}}.\;{\rm{t}}.\;\mathit{\boldsymbol{Ax}} = \mathit{\boldsymbol{b}}, \end{array}$

 $\mathit{\boldsymbol{x}} = {\mathit{\boldsymbol{x}}_0} + {\mathit{\boldsymbol{Z}}_k}\mathit{\boldsymbol{y}},$

Step 0:给定初始点$\boldsymbol{x}_{0}$, 终止误差$ε$, 初始对称正定阵$\boldsymbol{H}_{0}$, 令$k$:=0;

Step 1:若$\boldsymbol{x}_{k}$满足终止误差$ε$, 停止迭代, 输出最优解$\boldsymbol{x}^{*}$$\boldsymbol{x}_{k}, 否则执行Step 2; Step 2:计算\boldsymbol{g}_{k}, 选取基变量并计算\boldsymbol{A}对应的基矩阵\boldsymbol{Z}_{k}, 利用公式(1)(2)计算得到\tilde{\boldsymbol{g}}_{k}$$\tilde{\boldsymbol{H}}_{k}$, 进而得到拟牛顿方程$\tilde{\boldsymbol{H}}_{k}\boldsymbol{l}$=-$\tilde{\boldsymbol{g}}_{k}$, 求得其解为$\boldsymbol{l}_{k}$;

Step 3:利用式(4)计算原变量空间中对应的搜索方向$\boldsymbol{d}_{k}$=$\boldsymbol{Z}_{k}\boldsymbol{l}_{k}$;

Step 4:沿着搜索方向$\boldsymbol{d}_{k}$利用Armijo准则(算法2)进行线搜索得到步长$λ_{k}$;

Step 5:置$\boldsymbol{x}_{k+1}$=$\boldsymbol{x}_{k}$+$λ_{k}\boldsymbol{d}_{k}$, 利用式(5)更新得到$\boldsymbol{H}_{k+1}$, 置$k$:=$k$+1, 转Step 1。

Step 1:给定参数$σ$∈(0, 0.5)及步长调整因子$ω$∈(0, 1), 置$λ$=1;

Step 2:验证以下不等式是否成立:

 $f\left( {{\mathit{\boldsymbol{x}}_k} + \lambda {\mathit{\boldsymbol{d}}_k}} \right) - f\left( {{\mathit{\boldsymbol{x}}_k}} \right) \le \sigma \lambda \mathit{\boldsymbol{g}}_k^{\rm{T}}{\mathit{\boldsymbol{d}}_k};$

Step 3:判断, 若Step 2中不等式成立, 则终止迭代, 输出$λ_{k}$=$λ$, 否则令$λ$=$ωλ$, 转Step 2。

2 SUE模型及算法实现 2.1 SUE模型及等价模型

3 算例分析

 图 1 交通路网图 Figure 1 The road network
 ${t_a}\left( {{x_a}} \right) = {t_{a0}}\left[ {1 + \alpha {{\left( {\frac{{{x_a}}}{{{C_a}}}} \right)}^\beta }} \right],$

 ${\mathit{\boldsymbol{Z}}_0} = \left( {\begin{array}{*{20}{c}} { - 1}&{ - 1}&{ - 1}&{ - 1}&{ - 1}\\ 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1 \end{array}} \right),{{\mathit{\boldsymbol{\tilde H}}}_0} = \mathit{\boldsymbol{Z}}_0^{\rm{T}}{\mathit{\boldsymbol{H}}_0}{\mathit{\boldsymbol{Z}}_0}。$

4 结语

 [1] SHEFFI Y, POWELL W B. An algorithm for the equilibrium assignment problem with random link times[J]. Networks, 1982, 12(2): 191-207 DOI:10.1002/(ISSN)1097-0037 [2] MAHER M. Algorithms for logit-based stochastic user equilibrium assignment[J]. Transportation Research Part B, 1998, 32(8): 539-549 DOI:10.1016/S0191-2615(98)00015-0 [3] DIAL R B. A probabilistic multipath traffic assignment model which obviates path enumeration[J]. Transportation Research, 1971, 5(2): 83-111 DOI:10.1016/0041-1647(71)90012-8 [4] BELL M G. Alternatives to Dial′s logit assignment algorithm[J]. Transportation Research Part B, 1995, 29(4): 287-295 DOI:10.1016/0191-2615(95)00005-X [5] CHEN M, ALFA A S. Algorithms for solving Fisk′s stochastic traffic assignment model[J]. Transportation Research Part B, 1991, 25(6): 405-412 DOI:10.1016/0191-2615(91)90033-F [6] BEKHOR S, TOLEDO T. Investigating path-based solution algorithms to the stochastic user equilibrium problem[J]. Transportation Research Part B, 2005, 39(3): 279-295 DOI:10.1016/S0191-2615(04)00049-9 [7] ZHOU B, LI X, HE J. Exploring trust region method for the solution of logit-based stochastic user equilibrium problem[J]. European Journal of Operational Research, 2014, 239(1): 46-57 DOI:10.1016/j.ejor.2014.05.002 [8] ZHOU B, BLIEMER M C J, LI X, et al. A modified truncated Newton algorithm for the logit-based stochastic user equilibrium problem[J]. Applied Mathematical Modelling, 2015, 39(18): 5415-5435 DOI:10.1016/j.apm.2015.01.010 [9] CEYLAN H, BELL M G H. Genetic algorithm solution for the stochastic equilibrium transportation networks under congestion[J]. Transportation Research Part B, 2005, 39(2): 169-185 DOI:10.1016/j.trb.2004.04.001 [10] LIU J, MA S, HUANG C, et al. A dimension-reduced method of sensitivity analysis for stochastic user equilibrium assignment model[J]. Applied Mathematical Modelling, 2010, 34(2): 325-333 DOI:10.1016/j.apm.2009.04.012 [11] CONNORS R D, SUMALEE A, WATLING D P. Sensitivity analysis of the variable demand probit stochastic user equilibrium with multiple user-classes[J]. Transportation Research Part B, 2007, 41(6): 593-615 DOI:10.1016/j.trb.2006.11.003 [12] HBAR GERA. Origin-based algorithm for the traffic assignment problem[J]. Transportation Science, 2002, 36(4): 398-417 DOI:10.1287/trsc.36.4.398.549 [13] WEI C, ASAKURA Y. A Bayesian approach to traffic estimation in stochastic user equilibrium networks[J]. Procedia-Social and Behavioral Sciences, 2013, 80(11): 591-607 [14] YU Q, FANG D, DU W. Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model[J]. European Journal of Operational Research, 2014, 239(1): 112-118 DOI:10.1016/j.ejor.2014.04.009 [15] MENG Q, LAM W H K, YANG L. General stochastic user equilibrium traffic assignment problem with link capacity constraints[J]. Journal of Advanced Transportation, 2008, 42(4): 429-465 DOI:10.1002/(ISSN)2042-3195 [16] MENG Q, LIU Z. Mathematical models and computational algorithms for probit-based asymmetric stochastic user equilibrium problem with elastic demand[J]. Transportmetrica, 2012, 8(4): 261-290 DOI:10.1080/18128601003736026 [17] FISK C. Some developments in equilibrium traffic assignment[J]. Transportation Research Part B, 1980, 14(3): 243-255 DOI:10.1016/0191-2615(80)90004-1 [18] LEBLANC L J, MORLOK E K, PIERSKALLA W P. An efficient approach to solving the road network equilibrium traffic assignment problem[J]. Transportation Research, 1975, 9(5): 309-318 DOI:10.1016/0041-1647(75)90030-1 [19] HAN S. A route-based solution algorithm for dynamic user equilibrium assignments[J]. Transportation Research Part B, 2007, 41(10): 1094-1113 DOI:10.1016/j.trb.2007.05.001 [20] DAMBERG O, LUNDGREN J T, PATRIKSSON M. An algorithm for the stochastic user equilibrium problem[J]. Transportation Research Part B, 1996, 30(2): 115-131 DOI:10.1016/0191-2615(95)00026-7 [21] YUAN G, WEI Z. Convergence analysis of a modified BFGS method on convex minimizations[J]. Computational Optimization and Applications, 2010, 47(2): 237-255 DOI:10.1007/s10589-008-9219-0