不同需求日高铁列车开行方案协同优化方法

龙品秀，史峰，胡心磊，徐光明



不同需求日高铁列车开行方案协同优化方法

龙品秀1, 2，史峰1，胡心磊1，徐光明1

(1. 中南大学 交通运输工程学院，湖南 长沙 410075； 2. 贵阳职业技术学院 轨道学院，贵州 贵阳 550081)

不同需求日的出行需求在结构和总量上都存在差异，不仅需要提供与各需求日相匹配的运输能力，而且不同需求日的列车开行方案应有很大相似性，使高铁运输组织能平稳过渡。为权衡铁路运营成本和运输组织衔接，在考虑高铁运输组织平稳过渡前提下，谋求铁路运输成本和旅客出行费用最小，对不同需求日列车开行方案进行协同优化。由各需求日各OD对需求生成最大包络需求，以最大包络需求列车开行方案为备选列车集，产生各个需求日的列车开行方案。建立不同需求日开行方案协同优化双层规划模型，设计求解模型的遗传算法。算例分析表明，在公共列车集比例限制下，协同优化产生的开行方案具有较好评价指标，算法收敛性较好，体现了模型和算法的有效性。

高速铁路；列车开行方案；协同优化；不同需求日；遗传算法

高速铁路需求在总量上有差异性，在非节假日的一周内，周五和周日客流量需求总量较大，为高峰日；周一到周四及周六的客流需求总量接近且相对较低，为平峰日。同时，客流需求在结构上也存在差异性，即使是高峰日也会存在某些时段和O-D的需求低于平峰日对应时段和O-D的需求。针对需求有差异的情况，一方面，可每日采用相同的开行方案，但将造成运能浪费或不足。另一方面，可根据每日的不同需求特征，相应设计列车开行方案，但高铁列车开行方案的变化影响到列车运行图的动态调整，列车运营调度涉及到工务、电务、机务、车辆以及运输等部门，所以在一段时间内，运输企业不可能频繁对开行方案进行大规模调整，否则会增加运输企业组织工作的复杂性，同时破坏旅客出行习惯。考虑到日间需求差异性特征，在现场工作组织中，通常以工作日列车开行方案为基准，以增加列车的形式编制周末或节假日的列车开行方案。在周末或节假日的列车开行方案中也许会剔除少量工作日开行的一些列车。增开或剔除列车依赖于人工经验，与客流需求吻合程度不一定得到满足，且运行效益不一定好。不同需求日列车开行方案的设计要考虑日间需求总量及结构上的差异性、高铁客流需求时变性及不同需求日开行方案之间的一致性。只考虑单个需求日的列车开行方案优化，史峰等[1]综合考虑企业利益和旅客需求，建立优化列车开行方案的双层规划模型，并设计模拟退火算法求解；Park[2]综合考虑最小化旅客出行不便度和运营者费用模型，其中出行不便度包括等待时间和换乘时间，优化了列车开行方案；付慧伶等[3]通过建立列车备选集来优化列车开行方案；FU等[4]依据列车停站方案设计分层次的列车开行方案；蒲松等[5]综合使用列生成与行生成策略的启发式算法确定列车的运行路径及停站方案,采用改进分支策略的分支定界算法求解。由于上述研究未考虑到高铁需求时变特征，不能较好满足旅客时变需求。针对客流需求时变性，苏焕银等[6]将列车开行方案成本表示为列车运行时间和旅客出行费用的总和，引入列车运行方案图，通过基于时刻表的高铁客流分配方法[7]，建立了面向时变需求的高速铁路列车开行方案优化方法，Kaspi等[8]考虑旅客出行需求时变性，在不考虑列车能力限制的情况下，以列车和旅客旅行时间的加权成本为目标对列车开行方案进行优化，该研究未考虑列车能力与实际情况相差较大。考虑到客流需求的差异性，蒲松等[9]允许客流在一定区间范围内波动，建立基于动态客流的高速列车开行方案的鲁棒优化模型，该研究未需求考虑超出区间范围波动时的情况；Schobel[10]指出针对不确定有差异性的数据，采用鲁棒优化进行处理是一种有效手段。屈明月等[11]指出客流需求是决定实施分号运行图的必要条件，指出京广、京沪高铁客流存在周分布规律，提出分号运行图的开设周期与客流分布规律相吻合时才可以实施分号运行图；张琳奇等[12]通过列车保留、取消、调整等手段在平日列车开行方案上生成节假日列车开行方案。目前对不同需求日列车开行方案研究较为缺乏，均只是对该问题涉及到部分特征有所探讨，尚未有人同时兼顾日间需求变化与日内时变需求进行开行方案设计。针对不同需求日之间的出行需求在结构和总量上差异性，本文从协同优化不同需求日列车开行方案角度出发，以各需求日各OD对需求生成的最大包络需求为基础，利用已有模型优化列车开行方案，得到最大包络需求方案，将最大包络需求开行方案为作为备选列车集，优选产生各个需求日的开行方案。以不同需求日列车运行总成本、旅客出行费用总成本为目标，构建不同需求日开行方案之间的协同优化双层规划模型，将原模型转为罚函数模型利用遗传算法求解。算例分析表明，在规定的公共列车集比例限制下，协同优化产生的开行方案具有较好的评价指标，算法收敛性较好。

1 问题描述

综上所述，可将不同需求日高铁列车开行方案协同优化问题描述如下：

2 问题分析

2.1 平稳过渡的量化描述

2.2 先总后分的求解思路

具有很相近品质的列车开行方案可以有多种列车组合形式，若分别优化每一个需求日的开行方案，则难保证各个需求日开行方案具有足够大的公共列车集。为解决这个问题，不同需求日的现行开行方案，主要是在工作日开行方案的基础上增加开行列车，获得周末列车开行方案。在此基础上进行扩展，采用先总后分的思路协同求解：首先，构建一个不小于任意需求的总需求，基于总需求优化产生一个开行方案；然后对于每一个需求日，以总需求开行方案的子集构造其列车开行方案，使得公共列车集的规模必须满足规定标准；最后，可对于每一个需求日的开行方案进行适当调整，获得各个需求日的最终开行方案。

2.3 总需求的生成方法

2.4 最大包络需求开行方案的求解

对于给定的最大包络需求，可以参照文献[6]的方法优化求解最大包络需求开行方案。文献[6]为传统开行方案引入列车始发时刻的预估值，以便评价列车开行方案的时变需求的吻合程度。将开行方案的优化问题描述为主从博弈，其中铁路运输企业为主体方，出行旅客为从属方。铁路运输企业考虑全天运营时间约束、每个线路区间上每天和每个时段的列车通过能力约束、每趟列车在车站的到达和出发时刻的相互关系、每个车站始发(或终到)列车总数约束、动车组周转约束，以旅客出行费用和折算动车组小时数为目标优化开行方案，旅客出行费用由基于列车时刻表的客流分配确定(见文 献[7])。

3 不同需求日列车开行方案协同优化模型

根据上述分析，构建不同需求日列车开行方案的协同优化模型如下。

3.1 约束条件

1) 公共列车集比例下限约束

其中：||为列车的公里数。

2) Ω为Ω的子方案约束

3) 全天区间通过能力约束

记列车开行方案Ω全天进入区间的列车数为T，T受通过能力C()的限制，即

4) 车站始发和终到的列车总数约束

车站的始发和终到列车数不能超过车站始发终到能力C的限制，即

3.2 协同优化模型

协同优化目标是每一个开行方案的旅客出行费用和铁路运输成本达到最小，这是一个多目标优化问题。由于各个需求日的重要程度由这些需求日的天数比例确定，只要以天数比例为权值，便可获得旅客出行费用加权总量和铁路运输成本的加权总量。进而，引入旅客出行费用和铁路运输成本的权重系数，对二者加权汇总，将这个多目标优化问题转化为单目标优化问题。

其中：，τ，τ由开行方案Ω对应列车网络上的客流分配确定。

4 协同优化的遗传算法

4.1 罚函数模型的转化

为了方便求解协同优化的双层规划模型，由式(4)，(6)~(9)构建罚函数

将原模型转化为罚函数双层规划模型如下：

4.2 遗传算法设计

鉴于模型的求解复杂度高，选择常规遗传算法求解。

1) 基因编码

2) 初始种群

一般而言，初始种群多采用随机方法生成。虽然基因编码方法使约束条件(5)得到满足，使罚函数双层规划模型变成无约束优化问题，但事实上的约束是存在的，应该在尽可能满足约束条件、考虑目标函数最优性的条件下随机生成初始种群。

针对约束条件(6)~(8)，生成初始种群时只要求在一定精度上得到满足。一方面不严格满足约束条件能扩大解的提高搜索能力；另一方面也难于寻找严格满足各项约束的可行解；

针对目标函数最优性，在给定平均客座率标准的基础上，将不同需求日的人公里数换算成动车组公里数，为不同需求日配备相应的运输能力。

上述初始种群的生成方法既适当考虑了约束条件和目标函数的最优性，又避免了下层规划客流分配的大计算量。

3) 适应度函数

以目标函数()的倒数设计基因编码的适应度函数()，即

若目标函数值()越小，则适应度函数()值越大。

4) 遗传策略

选择策略：采用轮盘赌法则进行选择，选中个体的概率

交叉策略：对于2个父代采用单点交叉法，以给定概率p对遗传基因进行交叉操作。

变异策略：对于个体上的每个基因以给定概率p对其进行变异操作。

5 算例分析

5.1 算例数据

在不同需求日列车开行方案协同优化模型中，设置目标函数的参数=1 000，=1，旅客出行单位时间价值w=1元/min，w=2元/min，w=3元/min，16辆编组列车运行时间成本系数=1.5。首先求得列车的最大包络需求开行方案，下行方向的列车方案图如图2所示。

图1 京沪高铁线路

图2 最大包络需求列车运行方案图(下行方向)

5.2 算例计算与分析

设置遗传算法的种群个数为50，交叉概率p=0.618，变异概率p=0.03，1=2=0.5，分别针对公共列车集比例下限=0.9，0.8求解2套列车开行方案，并相应记为优化方案1和优化方案2。优化方案1中周一、周五的下行方向开行方案分别如图4和图5所示，图中实心点表示列车的始发终到站，空心点表示列车停靠站。

算法采用C#编程实现，运用主频为3.20 GHz，内存为4 GB，CPU为双核的计算机，优化方案1迭代500次，程序运行时间大约为10 h，收敛过程如图3所示(优化方案2收敛过程类似)，算法有较好收敛效果。

图3 搜索方案收敛图

图4 周一列车运行方案图(下行方向)

图5 周五列车方案图(下行方向)

优化方案1、优化方案2及评价指标分别展示在表1及表2中。最大包络需求开行方案的各项费用比周一、周五开行方案更高。在优化方案1中，周五比周一多开行6列列车，公共列车集比例为0.91；在优化方案2中，公共列车集比例为0.81，周五比周一多开行8列列车。开行方案的旅客出发时间偏差均在30 min以内，平均客座率均在70%以上，说明2 d开行方案与旅客出行需求的时变性吻合较好。优化方案1与优化方案2相比，公共列车集比例下限从0.9降到0.8，但周一方案的总费用由6.32×107降到5.69×107，动车组小时数由678.1组∙h下降到597.1组∙h，列车总数由121列减少到115列，旅客平均出发时间偏差由18.39 min增加到22.56 min，旅客出行总费用由2.24×103万元减少到2.11×103万元，客座率由72.44%增加到73.07%。周五方案也具有类似性质。因此，通过提高公共列车集比例下限，可以获得开行方案间的更大列车公共交集，但是会增加各方案的总费用。可根据实际需要，调整的值，获得满意的方案。

表1 优化方案1评价指标

表2 优化方案2评价指标

6 结论

1) 为保证不同需求日之间运输组织平稳过渡，提出由各需求日各O-D对需求生成最大包络需求，以最大包络需求列车开行方案为备选列车集，优选产生各个需求日的列车开行方案的协同优化思想。

2) 以各需求日运输成本、旅客出行成本为目标，建立了不同需求日列车开行方案协同优化双层规划模型，并设计了协同优化的遗传算法，在公共列车集达到规定比例的限制下，从最大包络需求列车开行方案中优化生成各需求日的列车开行方案。

3) 以京沪高铁线路为例验证了模型的正确性和算法的有效性。算例分析表明，协同设计不同需求日的列车开行方案能较好吻合客流的时变需求，且互相之间能保持较好一致性。

[1] 史峰, 邓连波, 霍亮, 等. 旅客列车开行方案的双层规划模型和算法[J]. 中国铁道科学, 2007, 28(3): 110−116. SHI Feng, DENG Lianbo, HUO Liang, et al. Bi-level programming model and algorithm of passenger train operation plan[J]. China Railway Science, 2007, 28(3): 110−116.

[2] Park B H, Seo Y I, Hong S P, et al. Column generation approach to line planning with various halting patterns—application to the Korean high speed railway[J]. Asia-Pacific Journal of Operational Research, 2013, 30(4): 1−19.

[3] 付慧伶, 聂磊, 杨浩, 等. 基于备选集的高速铁路列车开行方案优化方法研究[J]. 铁道学报, 2010, 32(6): 1−8. FU Huiling, NIE Lei, YANG Hao, et al. Research on the method for optimization of candidate-train-set based train operation plans for high-speed railways[J]. Journal of the China Railway Society, 2010, 32(6): 1−8.

[4] FU H, NIE L, MENG L, et al. A hierarchical line planning approach for a large-scale high speed rail network: The China case[J]. Transportation Research Part A, 2015, 5(75): 61−83.

[5] 蒲松, 吕红霞, 陈钉均, 等. 基于改进列生成算法的高速列车开行方案优化研究[J]. 铁道学报, 2015, 37(9): 1−7. PU Song, LÜ Hongxia, CHEN Dingjun, et al. Highspeed railway passenger train line planning optimization based on improved column generation algorithm[J]. Journal of the China Railway Society, 2015, 37(9): 1−7.

[6] 苏焕银, 史峰, 邓连波, 等. 面向时变需求的高速铁路列车开行方案优化方法[J]. 交通运输系统工程与信息, 2016, 16(5): 110−116. SU Huanyin, SHI Feng, DENG Lianbo, et al. Time-dependent demand oriented line planning optimization for the high-speed railway[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(5): 110−116.

[7] SU H Y, SHI F, XU G M, et al. Schedule-based passenger assignment for high-speed rail networks considering the ticket-booking process[J]. Mathematical Problems in Engineering, 2016, 1(1): 1−15

[8] Kaspi M, Raviv T. Service-oriented line planning and timetabling for passenger trains[J]. Transportation Science, 2013, 47(3): 295−311.

[9] 蒲松, 王文宪, 陈钉均, 等. 高速旅客列车开行方案的鲁棒优化模型[J]. 交通运输系统工程与信息, 2015, 15(6): 101−106. PU Song, WANG Wenxian, CHEN Dingjun, et al. The Robust model for line planning problems of high speed passenger train[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(6): 101−106.

[10] Schöbel A, Scholl S. Line planning with minimal traveling time[C]// ATMOS 2005-5th Workshop on Algorithmic Methods and Models for Optimization of Railways, 2006.

[11] 屈明月, 黄树明. 基于周期天窗的高速铁路分号运行图研究[J]. 铁道运输与经济, 2013, 35(12): 10−13. QU Mingyue, HUANG Shuming. Study on variant train working diagram of high-speed railway based on periodical maintenance window[J]. Railway Transport and Economy, 2013, 35(12): 10−13.

[12] 张琳奇, 聂磊, 付慧伶, 等. 高速铁路节假日列车开行方案优化研究[J]. 铁道运输与经济, 2017, 39(11): 57−62.ZHANG Linqi, NIE Lei, FU Huiling, et al. Optimization model for high-speed railway line planning during holidays[J]. Railway Transport and Economy, 2017, 39(11): 57−62.

The collaborative optimization of multi-day line plannings for high-speed railway

LONG Pinxiu1, 2, SHI Feng1, HU Xinlei1, XU Guangming1

(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China; 2. Rail Transportation Branch, Guiyang Vocational and Technical College, Guiyang 550081, China)

The differences of passenger demand among multi-day in passenger flow volume and time-varying structure requires that line plannings among multi-day can provide the corresponding capacity. Meanwhile, line plannings among multi-day need to have a lot of similarities to ensure the transport organizations can transit smoothly. In order to coordinate the railway operating costs and transport organizations cohesion, the railway operation costs and travel expenses of passengers are minimized on the premise of a smooth transition of high-speed rail transport organizations of multi-day. The collaborative optimization method of multi-day line plannings is carried out. In this method, each OD needs to generate the maximum demand for each day and solve the maximum demand line planning as a candidate train set, then the line planning for each day is preferably generated. The collaborative optimization bi-level programming model was established based on the multi-day and design the genetic algorithm to solve the model. The numerical example shows that under the constraint of the proportion of public train set, the line plannings which are produced by collaborative optimization method have good evaluation indexes, and the convergence of the algorithm shows the validity of the model and the algorithm.

high-speed railway; line planning; collaborative optimization; multi-day; genetic algorithm

10.19713/j.cnki.43−1423/u.2019.02.005

U293.32

A

1672 − 7029(2019)02 − 0310 − 09

2018−03−05

国家自然科学基金资助项目(U1334207，71701216)

史峰(1956−)，男，湖南芷江人，教授，博士，从事交通流理论，运输网络优化研究；E−mail：shifeng@csu.edu.cn

(编辑 蒋学东)