高速车辆停站优化算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇高速车辆停站优化算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
高速列车停站问题关系到高速铁路服务质量和经济效益，列车停站设置是否合理直接影响旅客对列车的选择行为、列车的客座利用率及诱增客流量的大小．列车停站方案优化是在列车径路、类别、编组辆数、开行频率确定后，根据客流需求和列车协调配合情况确定各列车的停站序列［1］．目前，高速列车停站优化的相关文献相对较少，多数结合列车开行方案一并进行研究．文献［2-10］结合列车开行方案对列车停站进行了优化或定性分析．文献［1，11］对列车停站优化问题进行了专门研究，分别利用模拟退火算法和遗传算法对列车停站进行了优化．文献［12］建立了城市轨道交通跨站停列车的停站方案0-1整数模型并提出了相关算法．列车停站方案优化问题的复杂度取决于需要优化停站的列车数目以及各列车途经车站的数目，将列车是否停站视为0-1变量，则列车停站优化问题的解空间大小为2∑(Nk－2)，其中，Nk表示列车k途经车站数目，包括始发终到车站．因此，求解列车停站优化问题的全局最优解需要用具有指数级复杂度的搜索，属于典型的NP-C(non-deterministicpolynomical-complete)问题，有必要对列车停站优化问题进行进一步的研究，探索适合列车停站优化问题的优化算法．本文结合高速列车停站设置的特点，提出高速列车停站优化问题的两阶段求解算法，采用基于先验知识的确定性计算和智能优化相结合的方法优化列车停站，通过实例对算法的有效性进行了验证．
1高速列车停站设置原则列车停站主要是为了满足中途旅客乘降需要．
客流量较少的中间站，主要靠通过列车停站的方式输送旅客，列车停站数目越多，越有利于旅客的乘降，方便旅客出行．但高速列车途中停站过多会降低旅行速度，失去了高速的意义．因此，列车停站的设置既要考虑到旅客出行的方便性，又不能过多地降低列车的旅行速度，从而造成旅客增加旅行时间．此外，列车停站不同，吸引的客流量也会不同，进而影响列车上旅客的拥挤程度，对旅客旅行舒适度产生影响．列车停站设置原则可概括为如下3个主要方面．(1)减少旅客旅行时间在客流量充足的条件下，尽量组织大站直达高速列车，减少列车中途停站，最大程度上缩短旅客由于列车停站而引起的时间消耗．一般情况下，为了保证高速列车的旅行速度，高速列车的停站比不宜过高．(2)方便旅客出行提高车站的服务频率，可以缩短旅客的候车时间，方便旅客出行，特别是对于客流量较大的车站．另外，提高车站的服务频率，还有利于旅客换乘，降低换乘风险．(3)提高旅客旅行舒适度列车停站设置直接影响列车吸引客流情况，停站不合理，会造成列车吸引客流的不均衡，部分列车出现拥挤现象，降低了旅客出行舒适度．因此，在确定列车停站时，应尽量避免或降低列车上客流的拥挤程度，提高旅客的旅行舒适性．
2高速列车停站方案优化模型在高速铁路车站数目一定的条件下，列车停站优化问题的复杂程度主要取决于需优化停站的列车数目，因此，在优化列车停站时，可将一个研究周期(一般为24h)划分为若干个时间段，并根据旅客的出行需求确定每个时间段内需开行的列车对数，分别优化每个时间段内开行列车的停站方案，最后通过叠加获得研究周期内所有列车的停站方案．根据高速列车停站设置原则，在客流满足要求的条件下，组织开行直达列车有利于减少旅客的出行时间，也可以降低铁路部门的运输成本．因此，在研究高速列车停站方案时，首先扣除需开行的直达列车数，并更新剩余客流量后，再利用本文提出的方法优化剩余列车的停站方案．
2．1列车停站优化目标优化列车停站的目的主要是为了方便旅客出行、减少旅客出行成本(包括时间成本和费用成本)，降低列车上旅客拥挤程度，提高旅客出行满意度．旅客出行的方便度可利用车站及区间服务频率来衡量，旅客旅行时间消耗及列车拥挤程度等可利用旅客出行广义费用来衡量．对于含N个车站的高速铁路，车站集合记为S，S={sii=1，2，…，N}，列车开行对数为K，开行方案中的列车集合记为R={Rkk=1，2，…，K}，车站si～sj的客流记为aij．引入列车的停站变量xki，定义为λ0为旅客出行方便度的调整参数，具体取值可通过对旅客的调查获得．由此可见，旅客出行方便度随着区间服务频率的增大，逐渐趋近于1;当区间服务频率为0时，旅L(p，q，k)为旅客乘车方案中的最大不换乘区间，由列车的相邻运行区间组成;Pijm为列车运行网络［13］中车站si～sj区间的第m条路径;Th(p，k)为旅客在车站p选乘或换乘列车Rk的平均时间消耗;nki为列车Rk从si～si+1站运行区间的载客量;cki为列车Rk第i区间的广义费用，包括旅客旅行时间折算费用、列车拥挤程度折算费用和客票支出，
2．2列车停站约束列车的停站需要考虑车站接发车能力、车站等级、列车等级、客流情况等综合确定．主要包括以下几个方面．(1)车站接发车能力［1］根据车站si的技术设备条件确定其接发列车能力为L(i)，则车站的接发列车数量应满足能力限制，即(2)列车最大停站数量列车停站数量与列车的等级有关．高速列车的停站数量较少，低等级列车的停站数目可适当增加．列车Rk的最大停站数量记为h－(k)，则列车的停站数量应满足此外，由于技术、经济等原因，需要列车必须停靠或无法停靠的车站，列车停站决策变量设置为常数，在优化过程中不再考虑．式(1)～(5)构成了列车停站方案的0-1整数规划模型，该模型解空间为2∑(Nk－2)，可见问题复杂度随规模呈指数级增长，属于典型的NP-C问题．
3高速列车停站优化算法考虑列车停站优化模型的复杂性，单纯利用启发式算法如遗传算法、蚁群算法、模拟退火算法等，较难快速而有效地获得满意的优化结果．本文在分析列车停站原则的基础上，提出列车停站优化的两阶段求解算法．算法的基本思路是将列车停站方案的优化过程分为2个阶段．第1阶段为初步优化，根据列车停站方案优化问题的特点，采用局部搜索和确定性计算相结合的方法，利用既有知识，快速有效地获得问题的较优解;第2阶段为综合优化，在第1阶段搜索结果的基础上，利用启发式算法进行二次优化．根据不同启发式算法的特点，采用禁忌搜索算法(tabusearch，TS)［15］，同时，利用第1阶段的优化结果作为TS的初始解，可以在较大程度上克服TS算法对初始解依赖性的不足．引入车站停靠权重的概念．车站停靠权重指为了方便旅客乘降，车站需要列车停靠的迫切程度．显然车站停靠权重与车站的既有服务频率和车站的上下车客流量有关，可表示为ξ为列车停靠权重的调整参数，用来衡量车站服务频率对停靠权重影响的程度，ξ越大，车站既有服务频率对停靠权重的影响也就越大;Ai为车站Si的上下车客流量总和．
3．1初步优化列车停站方案初步优化的目的是快速而有效地获得问题的较优解．在初步优化时，列车优先选择停靠权重较大的车站停靠．车站的停靠权重越大，说明车站的客流量越大、服务频率越小，列车优先选择客流量大、服务频率小的车站停靠是符合实际情况的．初步优化算法具体步骤如下:步骤1初始化参数初始化各站间客流aij，输入各列车的最大停站数目和等级;计算各车站的上下客流量Ai;对于任意k＜K，令列车Rk的停站数目φ(k)等于其最大停站数目．步骤2生成列车停站方案①令列车编号k=1，服务频率γij=0，计算各车站初始停靠权重wi;②对于列车k，选择停靠权重较大的φ(k)个车站作为列车k的停站，并更新这φ(k)个车站的停靠权重;③若k＜K，令k=k+1，转②．步骤3列车停站方案评价①根据列车停站构造列车运行网络，并按照均衡配流［14］的方法求解各列车在不同运行区间的客流量;②结合目标函数，利用下式对列车停站方案进行评价，取值根据目标的相对重要性和量纲确定．步骤4列车停站方案的局部优化局部优化步骤如下:①令列车编号k=1，F=0(方案更新标识);②在满足列车停站数目约束的条件下，将列车k的停站数目增加或减少1，其他列车停站数目保持不变，按照步骤2重新确定列车停站方案;③按照步骤3，对列车停站方案进行评价;④若新产生的列车停站方案优于当前最优解，则更新列车最优停站方案，并令F=1，否则还原列车k的停站数目;⑤若k＜K，令k=k+1，转②;⑥若F=1，重复步骤4，否则初步优化算法结束．
3．2综合优化列车停站优化算法的第2阶段为综合优化，该优化采用禁忌搜索算法，以初步优化的结果作为其初始解．禁忌搜索算法的关键是邻域函数的构造、解的评价以及禁忌表的设计．(1)邻域解的构造停站方案{xkik≤K，i∈Sk}(Sk为列车Rk的途经车站集合)是由0-1决策变量xki所构成的二维数组，因此，利用0-1变量取反的方法构造停站方案的邻域，即改变停站方案中任一决策变量的值(0-1决策变量取反)，产生当前停站方案的一个邻域解．列车停站方案邻域解的总数目为∑(Nk－2)个．(2)解的评价利用禁忌搜索算法对模型进行评价时，不仅要考虑目标函数的影响，还要考虑列车最大停站数目的限制．列车停站方案邻域解是通过改变列车在某一车站的停靠情况产生的，这样会引起列车停站数目的增加或减少，有可能产生不可行解．为了使禁忌搜索算法的搜索过程能分别从可行和不可行的解空间接近最优解，对超出最大停站数目的列车进行惩罚，因此，构造适配值函数为(3)禁忌表的设计列车停站方案用二维数组表达，禁忌表也用二维数组表达:{bkik≤K，i∈Sk}，其中:bki为列车停站位被禁忌的步数，bki＞0时，表示该停站位被禁忌．禁忌表的关键参数为禁忌长度．为了增大算法初期搜索解空间的范围，禁忌长度采用动态参数，即算法初期采用较大的禁忌长度，算法末期采用较小的禁忌长度．禁忌长度为①初始化最小禁忌长度，最大禁忌长度，迭代次数Zd=1，初始化当前停站方案为停站方案初步优化结果;②生成当前停站方案的邻域解，并利用适配值函数对邻域解进行评价;③判断邻域解中对象的禁忌属性及禁忌对象是否满足藐视准则，选择邻域解中未被禁忌的对象以及满足藐视准则的禁忌对象为候选解;④选择候选解中的最优停站方案作为当前停站方案，计算当前禁忌长度，并根据最新禁忌长度更新禁忌表;⑤若迭代次数Zd≤ZT，Zd=Zd+1，转②，否则，综合优化算法结束．
4算例以某高速铁路为例对算法的有效性进行验证．线路共有16个车站，分别记为s1～s16．本线客流分2个运行区段，分别为s1s4和s1s16，高峰小时除开行1对直达列车外，还需开行本线停站列车10对，其中，s1s4开行3对，s1s16开行7对．根据远期高峰小时客流，利用本文提出的两阶段算法对各列车的停站进行优化，当s1s4和s1s16运行区段开行列车的最大停站数目分别取2和9时，优化算法求得的列车停站方案详见表1，适配值随迭代次数的变化见图1，算法共执行了40代，耗时79s，根据计算结果，客流直达率达96．4%，绝大多数旅客都得到了良好的服务．该算例仅利用禁忌搜索算法求解时，获得与两阶段算法相当的优化结果，平均耗时113s，可见，利用两阶段优化算法比单纯利用禁忌搜索算法求解效率提高约30%．此外，两阶段算法的鲁棒性明显优于禁忌搜索算法．随着问题规模的扩大，两阶段算法的优势将越加明显．5结论利用两阶段优化算法对高速铁路高峰小时列车停站方案进行优化，可以快速获得列车停站方案的满意解，提高了算法的求解效率．通过对列车停站问题的研究，得出如下结论:(1)列车停站优化问题属于NP-C问题，不能利用全搜索算法进行求解，可充分利用列车停站设置的相关原则，缩小算法的搜索解空间，以提高算法的求解效率．(2)列车是否停站主要取决于车站的上下车客流量及列车的停站数目．在客流满足要求的条件下，应尽量减少列车的停站数目，提高列车旅行速度;另一方面，对于上下客流量较大的车站应尽量提高车站的服务频率，方便旅客出行．旅客对乘车方案的选择，不仅与乘车方案的广义费用有关，还与乘车方案中列车的发到时刻密切相关．同时，考虑到旅客选择乘车方案的随机因素，旅客对列车的选择很难满足均衡配流的要求，因此有必要进一步研究适合列车的配流方法．