基于BFGS公式的改进截断拟牛顿法在随机用户均衡问题上的应用
|
摘要
根据随机用户均衡问题的特点构造一种基于BFGS校正公式和Armijo线搜索的截断拟牛顿法。介绍截断拟牛顿方程的构造过程及其算法的具体步骤;针对随机用户均衡模型的特点给出算法的收敛性和两个需注意的问题,并将此算法应用于一个路网。数值算例分析表明:所构造算法在迭代次数和误差方面均优于截断牛顿法,改进截断拟牛顿法可以避免二阶Hessian矩阵的计算,还可以用于某些Hessian矩阵不正定问题的求解。
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 quasiNewton 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.
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 quasiNewton 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.
引文
[1]SHEFFI Y,POWELL WB.An algorithm for the equilibrium assignment problem with random link times[J].Networks,1982,12(2):191-207.
[2]MAHER M.Algorithms for logit-based stochastic user equilibrium assignment[J].Transportation Research Part B,1998,32(8):539-549.
[3]DIAL R B.A probabilistic multipath traffic assignment model which obviates path enumeration[J].Transportation Research,1971,5(2):83-111.
[4]BELL MG.Alternatives to Dial's logit assignment algorithm[J].Transportation Research Part B,1995,29(4):287-295.
[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.
[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.
[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.
[8]ZHOU B,BLIEMER MC 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.
[9]CEYLAN H,BELL MG H.Genetic algorithm solution for the stochastic equilibrium transportation networks under congestion[J].Transportation Research Part B,2005,39(2):169-185.
[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.
[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.
[12]HBAR GERA.Origin-based algorithm for the traffic assignment problem[J].Transportation Science,2002,36(4):398-417.
[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.
[15]MENG Q,LAMWH K,YANG L.General stochastic user equilibrium traffic assignment problem with link capacity constraints[J].Journal of Advanced Transportation,2008,42(4):429-465.
[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.
[17]FISK C.Some developments in equilibrium traffic assignment[J].Transportation Research Part B,1980,14(3):243-255.
[18]LEBLANC L J,MORLOK E K,PIERSKALLA WP.An efficient approach to solving the road network equilibrium traffic assignment problem[J].Transportation Research,1975,9(5):309-318.
[19]HAN S.A route-based solution algorithm for dynamic user equilibrium assignments[J].Transportation Research Part B,2007,41(10):1094-1113.
[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.
[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.
[2]MAHER M.Algorithms for logit-based stochastic user equilibrium assignment[J].Transportation Research Part B,1998,32(8):539-549.
[3]DIAL R B.A probabilistic multipath traffic assignment model which obviates path enumeration[J].Transportation Research,1971,5(2):83-111.
[4]BELL MG.Alternatives to Dial's logit assignment algorithm[J].Transportation Research Part B,1995,29(4):287-295.
[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.
[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.
[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.
[8]ZHOU B,BLIEMER MC 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.
[9]CEYLAN H,BELL MG H.Genetic algorithm solution for the stochastic equilibrium transportation networks under congestion[J].Transportation Research Part B,2005,39(2):169-185.
[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.
[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.
[12]HBAR GERA.Origin-based algorithm for the traffic assignment problem[J].Transportation Science,2002,36(4):398-417.
[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.
[15]MENG Q,LAMWH K,YANG L.General stochastic user equilibrium traffic assignment problem with link capacity constraints[J].Journal of Advanced Transportation,2008,42(4):429-465.
[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.
[17]FISK C.Some developments in equilibrium traffic assignment[J].Transportation Research Part B,1980,14(3):243-255.
[18]LEBLANC L J,MORLOK E K,PIERSKALLA WP.An efficient approach to solving the road network equilibrium traffic assignment problem[J].Transportation Research,1975,9(5):309-318.
[19]HAN S.A route-based solution algorithm for dynamic user equilibrium assignments[J].Transportation Research Part B,2007,41(10):1094-1113.
[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.
[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.