微分进化算法在高铁票价双层规划模型求解中的应用

来源:用户上传      作者:

　　摘 要：微分进化算法（DE）是一种快速高效的智能进化算法，本文对其算法做了简单的介绍，并针对高速铁路票价问题，引入并构建了双层规划模型。模型中高铁企业是领导者角色，出行乘客是跟随者角色，二者相互作用。上层模型从高铁企业收益最大化的角度出发，下层模型以各类出行方式的乘客广义出行费用相同为基础。针对该模型设定了一些参数，并介绍了如何应用微分进化算法对该模型进行求解，并对乘客福利及算法本身的优化工作做出了进一步设想。
　　关键词：微分进化算法；高速铁路票价；双层规划模型
　　中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）04-0020-03
　　Application of Differential Evolution Algorithms in Bi-level Programming Model of
　　High-speed Railway Ticket Price
　　CUI Wei
　　（School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou 730070，China）
　　Abstract：Differential evolution （DE） is a fast and efficient intelligent evolutionary algorithm，and its algorithm is briefly introduced. Aiming at the problem of high-speed railway fare，a bi-level programming model is introduced and constructed. In the model，the high-speed railway enterprise is the leader role，and the traveling passenger is the follower role，which interact with each other. The upper model is based on maximizing the revenue of high-speed railway enterprises，and the lower model is based on the same generalized travel cost of passengers in different modes of travel. Some parameters are set for the model，and how to use differential evolution algorithm to solve the model is introduced. Further assumptions are made on passenger welfare and optimization of the algorithm itself.
　　Keywords：differential evolution algorithms；high-speed railway ticket price；bi-level programming model
　　0 引 言
　　高速铁路是未来铁路旅客运输的发展方向，票价在运输问题中至关，铁路部门作为企业要考虑收益最大化，同时作为国企还要承担相应的社会责任，保证票价能让乘客接受，这是一个复杂的问题。低票价会使企业入不敷出，导致亏损，高票价既浪费社会资源，又会引发乘客不满，导致低上座率。企业在盈利和社会福利间实现最优票价是非常重要的问题，在制定高速铁路的票价过程中引入双层规划模型是非常合适的。微分进化算法（Differential Evolution Algorithm，简称DE）是一种启发式算法，原理简单、易实现、效率高，非常适合用于双层规划模型的求解[1]。
　　1 微分进化算法
　　DE算法在求解连续变量的函数优化问题时能快速、稳定地收敛到全局最优解[2]，迭代到预设次数，或者目标函数到达一定要求时结束运算。影响微分进化算法性能的主要控制参数有种群规模、缩放因子和交叉常量。
　　（1）种群规模：种群规模较大时，算法的搜索范围也会大，但是计算的时间会变长，问题的维数较高时，算法的效率低。种群小则种群会变得单一，易落入局部最优的困局，从而错失最优解。根据经验，种群数量可以取在问题维数的5～10倍；
　　（2）缩放因子：向量之间差值的系数用F表示，F越小，计算的收敛速度越快，每次搜索的距离就越近，越易陷入局部最优。F越大，收敛的速度会慢，向量探索的距离就越远，更容易取到全局最优解，它的初值可以在[0.5，0.6]；
　　（3）交叉常量：它的取值区间为[0，1]，取值小，子代从父代继承的部分就少，变異较小，收敛速度低。实际计算中取值范围为[0.6，0.9]，它初值可以为0.8，具体应用时根据不同的需要可以略微作调节[1，2]。
　　2 双层规划模型
　　2.1 双层规划形式
　　双层规划的形式如下所示：
　　s.t. G（x，y）≤0
　　其中y=y（x）由下述规划求得：
　　s.t. g（x，y）≤0
　　双层规划模型由上层模型（p1）和下层模型（p2）组成，上下层问题分别由相应的公式组成。居于上层的领导者通过对x值的决策影响下层跟随者，下层跟随者通过它的目标函数对上层领导者产生反馈。下层跟随者的变量x是上层领导者变量y的函数，就是y=y（x），反应函数[3，4]。
　　2.2 模型的建立 　　本模型中把高速铁路客运部门的收益多少与旅客的广义出行费用看成上下层领导者与跟随者的关系问题，其中高铁客运部门是领导者，旅客的出行需求是跟随者。领导者通过调整票价、安排车次、安排到发时间、提供不同等级的列车和坐席等政策来调整某种交通方式的特征，跟随者面对各种出行方式，根据自身需要做出决策。由此，用以下模型来描述[5]：
　　其中U为上层规划，L为下层规划，F为上层规划的目标函数，x为上层规划的决策变量，G为对变量x的约束条件，f为下层规划的目标函数，y为下层规划的决策变量，g为对变量的约束条件，y=f（x）为反应函数[6]。
　　上层规划U：高铁客运部门通过决策票价水平、制定列车开行速度、开行时长等方式最大化企业收益；下层规划L：出行者面对多种运输方式，根据自身的收入水平、实际出行需要或换乘方案等，选择广义出行费用最小的。
　　模型中的上层规划和下层规划是相互制约的，客运企业期望经济效益最大化，以此作为出发点来制定票价，同时旅客期望出行的广义费用最小。一般情况下，在其他影响因素（如旅行时长、服务水平）不变的情况下，若高铁票价价格上升，则必会影响客流分担率，由部分高铁客流转向其他运输方式（普速列车、公路或航空）；反之，高铁票价价格下降则会导致部分其他运输方式的客流需求转移而来。因此，铁路客运部门要对高铁票价的制定做出全面的考虑[7]。
　　2.3 上层规划构建
　　对于高铁运输线路中的不同出发到达点，本文将其定义为单个OD组，为了简化模型，定义在OD组ω之间铁路运输的客票价格为 ，那么在整个客运网络中，总收益为：
　　其中，为在OD组ω之间高铁客运的流量，是高铁部门在OD组ω之间乘客的人均运输成本，也能用列车运行速度及服务水平等因素的函数来表示[8]。
　　对于下层规划来说，由于每个乘客都会尽力选择广义出行费用最小的出行方式，经过简化得到每一个运输方式的广义出行费用都相等，这样得到如下公式：
　　Qw为OD组ω的客运总需求量，设OD组ω之间存在n种运输方式，则n1，n2=1，2，K，n分别代表其中一种。函数f是一个广义费用函数，式（2）表示状态平衡时，多种运输方式的广义费用相等，式（3）表示多种运输方式的客流量之和等于总客流量[9]。此处采用对数形式表示广义费用函数f[8]：
　　（4）
　　a、b是系数，表示OD组ω中第n（n∈N）种交通方式的效用值，它的值越高，则乘客乘坐这种运输方式所获得的益处越大，即广义出行费用低，表示如下[8]：
　　（5）
　　为出行时长参数，为客运票价参数，为安全及服务等其他相关系数；ai（i=1，2，3）为待定参数[8]。
　　3 基于微分进化算法求解双层规划模型
　　求解过程如下：
　　第一步，初始化参数：种群规模Np取20，缩放因子F初始化为0.6，交叉常量CR初始化为0.8。
　　在企业的运营过程中，首要考虑的因素应该是利润，在与其它运输方式竞争的过程中，企业要追求利益的最大化，其次由于企业的所有制形式，还要承担一部分社会责任。因此，上述模型的目标分为两个部分，第一个部分实现利润的最大化，第二部分考虑社会的需求和公共福利。因此，第一阶段的上层模型中Np=20，F=0.6，CR=0.9，满足下层规划函数的初始解 随机产生，是不同交通方式i的票价[10]。
　　第二步，把上层规划中的初始解，即票价代入下层函数：
　　（1）利用Frank-Wolfe算法求得最优解y*，即各种类列车的客流量；
　　（2）把X和y*代入上层函数，计算出种群中各个分量对应的F；
　　（3）根据评价函数，将各个分量的F值进行比较，优选出新的优势种群；
　　（4）如果达到预设迭代次数，或F值已经不再明显变化，则计算结束，得到最优解u，否则转入（1），继续计算。
　　4 结 论
　　微分进化算法是一种较为年轻的算法，它的优点很明显，但是目前来看，在单目标计算方面使用较多，多目标计算方面有待进一步深入研究。本文通过引入微分进化算法，通过求解相应的双层规划函数，可以解决高速铁路票价的优化问题。进一步的工作也可以改变优化策略，不仅可以实现高铁部门收益最大化的目标，还可以从企业收益与乘客公共福利的角度对票价优化问题进行研究，兼顾双方的目标。针对微分进化算法在搜索过程前期对搜索速度要求较高，以及后期对搜索范围有一定要求的特点，可以在两个阶段对缩放因子和交叉系数进行优化，必定会大大提高算法的效率与准确度。
　　参考文献：
　　[1] 崔伟.高速铁路客运定价理论与方法研究 [D].兰州：兰州交通大学，2013.
　　[2] 刘科.改进微分进化算法在LZ-AVC6000系统中的研究与应用 [D].保定：华北电力大学，2017.
　　[3] 韦凌翔，陈红，蒋金亮，等.基于广义费用函数的高铁票价双层规划模型研究 [J].铁道科学与工程学报，2015，12（2）：250-256.
　　[4] 徐冰.基于铁路客运票价的定价模型及求解方法研究 [D].沈阳：沈阳工业大学，2007.
　　[5] 陈建华，高自友.基于双层规划模型的铁路票价制定优化策略 [J].北方交通大学学报（社会科学版），2003（3）：38-41.
　　[6] 程谦.双层规划模型在沪宁城際铁路客票价格优化中的应用 [J].现代交通技术，2015，12（2）：77-80.
　　[7] 四兵锋，高自友.市场竞争条件下的客运价格优化策略模型及算法 [J].交通运输系统工程与信息，2007（1）：73-79.
　　[8] 高自友，四兵锋.市场竞争条件下铁路旅客票价制定的模型与算法 [J].交通运输系统工程与信息，2001（1）：50-55.
　　[9] 陈建华.铁路旅客票价优化问题的相关模型及算法 [D].北京：北京交通大学，2007.
　　[10] 郝鹏海，程晓荣.粒子群算法在铁路双层规划模型求解中的应用 [J].电脑知识与技术，2017，13（26）：238-239+242.
　　作者简介：崔伟（1982-），男，汉族，新疆奎屯人，工程师，硕士，研究方向：交通运输规划与管理。
转载注明来源:https://www.xzbu.com/1/view-14771246.htm