2020, Vol. 41
2. 天津工业大学 电工电能新技术天津重点实验室, 天津 300387;
3. 天津工业大学 经济与管理学院, 天津 300387
2. Tianjin Key Laboratory of Advanced Electrical Engineering and Energy Technology, Tiangong University, Tianjin 300387, China;
3. School of Economics and Management, Tiangong University, Tianjin 300387, China
随着我国经济不断发展，人们越来越注重出行的便捷性.高密度、高频率成为我国高速列车的基本特点.因此研究基于动态客流分配的高速铁路列车开行方案的优化，对高速铁路客运效率的提高和旅客满意度的提升具有十分重要的意义.
在停站方面，国内外学者进行了深入的研究.Yang等[1]提出了一种新的列车停靠方案和列车运行时刻表的组合优化方法.Chen等[2]将列车运行与铁路收益和旅客出行结合起来建立多目标模型.文献[3]将收益管理与列车运行规划相结合建立模型.在高速铁路的实际运营过程中，旅客对于乘车的需求不同，会产生误车以及退票、改签等情况，表现为旅客客流的不确定性.文献[4]考虑出行目的地(original destination，OD)旅客的需求，来进行列车调度优化分析.文献[5]基于旅客出行时变的需求，建立了双层规划模型.文献[6]提出了一种基于时间表的乘客分配方法.虽然国外对动态客流的研究较为成熟，但是我国铁路具有客流量多、停靠站点多、路线复杂等特点，旅客的动态需求较国外更加明显.同时我国高速铁路运营时间较短，国内学者多只单一关注高速铁路的开行方案，没有很好地与动态OD客流相结合，降低了停靠方案优化的灵活性，无法满足旅客出行的多样化.
本文在上述研究成果基础上，面向最大化经济收益和最小化出行费用来研究高速铁路列车开行方案的优化问题.以高速铁路停站表及列车编组数量为研究对象，综合考虑不同旅客出行的需求、高速列车运行成本、列车运行时间和服务水平，将列车开行方案与OD客流量相结合，并依据旅客的购票过程建立了一种基于动态客流的列车开行方案的多目标优化模型.对此设计了一种基于个体信息和改进变异算子的多目标差分(SG-MOSaDE)算法，力求满足旅客多样化的出行需求.
1 高速列车开行方案优化模型 1.1 问题分析高速铁路网络可以表示为G(V, E)，其中车站集合V=(v1, v2, …, vn)，区间集合E=(eij|i=1, 2, …，n-1;j=2, 3, …, n).各区间里程集合D=(deij|i=1, 2, …, n-1;j=2, 3, …, n).图 1为高速铁路线路示意图，共有10个站点，假定车站1为始发站，车站10为终点站，其余站点为途经站点.T为开行方案下运行在该线路上列车的编号，|T|表示该线路上运行列车的数量.根据OD客流对现行列车开行方案进行优化，包括列车编组数量、列车开行数量以及停站方案等.
|
图 1 高速铁路线路示意图 Fig.1 Schematic diagram of high-speed railway line |
具体来说，列车的开行方案为Ω，对于列车T, 其对应的列车停站方案为lT, 则lT=(v1T, v2T, …，vnT)，也记为VT=(v1T, v2T, …, vnT)；mT和|T|分别表示列车的编组数量和开行数量，不同编组数量对应列车的定员人数为ρ(m).因此，列车开行方案的优化可以表示为对Ω={VT, mT, |T|}的优化制定.
1.3 模型建立思路本文的主要目的是将高速列车开行方案与动态客流相结合，通过OD客流量等数据建立模型，再进行动态客流的分配，建立列车编组数量和列车停站方案的优化模型，模型综合考虑了铁路集团的经济效益和旅客的出行费用.
1.4 模型假设本文模型的建立与求解基于以下四点假设:
1) 封闭性假设.假设本文研究的高速铁路运营区段是封闭、独立的.
2) 相似性假设.假设本文涉及的旅客具有相同的时间价值.
3) 确定性假设.在潜在出行OD客流确定的情况下，具有出行需求的旅客数量是变化的.
4) 滞留性假设.若旅客超出定员数量，则产生滞留.
1.5 动态客流分配在列车开行方案的制定中，潜在的OD客流通常是其制定的标准.但是随着列车开行方案的变化，旅客对于列车的选择往往会产生不同的变化.为了能够满足旅客的购票心理，以及不同区间售票时间的不同和各列车出发时间的不同，设计了一种动态客流分配模型.
首先对各列车乘车区间售票时间和各列车出发时间进行不同的设计.同时由于旅客对不同列车的心理期望不同，因此将OD客流按一定概率分配给各列车，用来模拟旅客的购票情况.之后按照列车出发时间对各列车车次中的不同区间的OD客流进行再分配和转换.若该列车某个区间的选择人数过多，则滞留旅客自动分配到之后时间的列车同区间上.如果之后时间的列车在该区间均不停车或者余量为0时，则剩余旅客产生滞留.其中，通过基于列车在各区间运行时长的广义Logit概率模型，来模拟旅客在出行时对列车的初始选择概率，具体公式为
|
(1) |
式中:tlT0为列车区间运行时间; KL(vi, vj)表示在区间段vi到vj旅客可以选择列在的集合.
为了更好地说明OD再分配和转换的过程，假定该线路共有两辆列车，两车定员均为600人.T=1的列车停站为1，5，10；T=2的列车停站为1，5，7，10.假定站点1→10的乘客人数为750人，站点5→10的乘客人数为600人.为了更清楚说明再分配过程，区间运行时长不再另外计算，假定各区间的乘客在初始选择列车时有2/3的概率选择列车1.则列车1中站点1→10的人数为500人、站点5→10的人数为400人.假设旅客抢到票的概率相同，则列车1会导致站点1→10的滞留旅客为167人，站点5→10的滞留旅客为133人.此时列车2的剩余票量为150张，由于区间1→10的售票截止时间较早，故首先分配站点1→10的滞留旅客.最终列车2中站点1→10的人数为400人、站点5→10的人数为200人.滞留旅客为站点1→10的乘客17人，站点5→10的乘客133人.
1.6 模型决策变量为了满足动态客流的需求，本文关注于生成列车开行方案中的开行列车数量、列车编组数量、以及列车停站方案.因此，本文涉及的三类决策变量为
1) 停站方案:
|
(2) |
式(2)中，i, j分别表示列车与车站的编号，且i∈T.
2) 编组数量:
|
(3) |
3) 开行数量(单方向)：|T|，正整数变量，表示研究区段上行方向高速列车开行数量.
1.7 模型目标函数高速铁路停站方案的首要目标是最大化满足不同旅客的需求，节省乘客出行成本的同时能够为铁路系统带来更大的经济效益.因此，高速铁路开行方案的制定应综合考虑经济效益和出行费用两个方面.
1) 运营部门经济效益最大.本文以高速列车的运行费用和停站服务费用作为运营成本，建立目标函数:
高速列车总票价收入为
|
(4) |
式中:lTm表示编组数量为m的列车T的停靠方案; flTm (vi, vj)表示该停靠方案的列车T上vi站到vj站的人数; φ表示高速列车单位票价.
高速列车停站服务费用为
|
(5) |
式中，C1j表示站点j的停靠服务费用.
高速列车单位运营成本费用为
|
(6) |
式中:C2表示高速列车单位里程的运营成本; Di表示列车i的运营距离.
综上所述，运营高速列车的经济效益可以表示为Z=Y1-Y2-Y3:
|
(7) |
2) 旅客出行成本最小.本文以旅客出行的时间花费作为旅客的出行成本，建立目标函数如下:
出行的时间消耗为
|
(8) |
式中:A表示列车的平均行驶速度; tk表示停靠时间; td表示列车启停时间.
在优化过程中，由于新生成的列车开行方案可能会产生滞留旅客.为了使滞留旅客最少，故使滞留旅客所带来的时间损耗具有一个较大的惩罚因子.因此，旅客出行成本最小的目标函数为
|
(9) |
式中:ω为旅客的时间价值; M为惩罚因子; fk表示滞留的旅客数量.
1.8 模型约束条件1) “0-1”变量约束.
用“0-1”变量表示列车在车站是否停靠和列车的编组数量.
|
(10) |
|
(11) |
2) 列车编组数量对应定员人数约束.
|
(12) |
3) 各区间载客量不超过定员人数.
|
(13) |
4) 满足一定的上座率.
|
(14) |
式中:θd为上座率的下限; θu为上座率的上限.
5) 终到站约束.所有列车在终点站停车，由于本文的研究区段是多起点，所以没有严格的始发站停车约束.
|
(15) |
综上所述，得到高速列车开行方案优化模型，其中目标函数为式(7)和式(9)，约束为式(10)~式(15).
为了能够更好地说明公式所表达的意思，本文在此说明部分变量的表达含义.假定问题中的线路仅有一辆列车，编组为8辆编组.且设计该列车的停站点为1，5，10.故lTm可以表示为l10=(1, 0, 0, 0, 1, 0, 0, 0, 0, 1)，同时v11=v71=v101=1.假定站点1到站点5的乘客数量为800人，其余站点无人乘坐，由于列车定员数为600人，则该区间旅客数flTm(vi, vj)=fl10(v1, v5)=600，滞留旅客数fk=200.若站台1, 5, 10的停靠费用均为500元，则该列车考虑的站台停车费用C11=C15=C110=500.假定站台1到站台10为1000km，站台1到站台5为500km，则列车运行距离D1=1000，de15=500.其余变量均为预设值，与决策变量无关.
2 改进差分进化算法设计差分进化(differential evolution, DE)算法能够很好地适应多目标优化模型的求解.但是传统DE算法中也存在很多不足，如对于复杂模型求解速度慢、精度较低等.而且通常来说，传统DE算法不用于求解二进制变量，并不适用于本文模型.因此本文对传统DE算法作了改进.
2.1 编码设计由于传统DE算法一般用于实数的优化，但在本文中，编码方式均为0-1方式.因此，在进行本文模型求解之前，需要对差分进化中的变异操作进行改变，使其适用于0-1变量的求解.
对缩放因子F进行设计，将F转化为0-1变量:
|
(16) |
此时，关于变异操作中基向量、缩放因子F、差分向量均为0-1变量，为了使变异方法适应0-1变量的操作，本文使用一种异或方式进行变异操作.公式为
|
(17) |
式中:“∧”为异或运算；“ & ”为与运算.
2.2 算法改进首先，传统DE算法中的种群大小一般是固定的，这意味着每个解决方案的演化过程所携带的有用信息不能被保持和用来指导其演化，而这一信息在粒子群优化中被证明是非常有用的[7].其次，传统DE算法的自适应策略已经投入了大量的工作，但没有考虑目标解的质量.此外，DE算法的核心是变异操作，通常情况下变异操作中的父代个体是随机选取的，因此，对于当前种群中的较优秀个体会有一定概率没有被选上参与变异，从而使进化没有向最优方向进行.基于上述不足，本文在文献[8-9]的基础上提出了一种改进差分进化算法，即带有个体信息和改进变异操作的改进差分进化(SG-MOSaDE)算法，其主要特点如下.
1) 本文采用一组最大具体NP个解的个体信息，而不是传统算法中固定的NP个解集.每次随机选择个体信息中某一个解进行变异和交叉操作，若新生成的子代个体能够不被此解支配，则移除子代个体所有支配的解，并将此子代个体加入个体信息中，生成新的个体信息，并在此个体信息上重新进行选择，循环NP次，当达到最大数量后，利用NSGA-Ⅱ进行选择前NP个解.
2) 控制变异参数F随着生成量的增加而减小，从而使每个解的搜索行为能够向最优化靠近.交叉参数Cr的选择则设计一个参数列表，此列表个数最多具有lk个.它的前lk个确定方法与MOSaDE算法[10]中使用的方法相同.为了保证Cr参数更加有效，采用先进先出的原则，只选择更新成功时进行Cr列表的更新.
3) 变异操作在父代的选择上，综合考虑利用不同个体适应度和搜索空间的信息.对于所处不同空间的个体具有不同的能力.对较优适应度的解希望增强它跳出局部最优区域的能力；相反适应度较差的解希望提高它的收敛速度，这样它就可以更快地向最优解进化.变异操作的公式为
|
(18) |
首先，依照个体适应度将种群中的个体进行从优到劣的排序，并分为三组.若选择个体不处于适应度最优解的组别，即R(Xi)>1，则依照排名越靠前越容易被选中的方法，来选择适应度最优组别中的解Xrbest作为差分向量终点，差分向量的起点Xr2，则在适应度最差的第三组中随机选择.否则若R(Xi) < 1，则在适应度较优的第二组内依照排名来选择差分向量的终点Xr1.
SG-MOSaDE算法为
1) 初始化种群X1, g, X2, g, …, XNP, g，令g=0, Fmean=1.0, and Cr, mean=0.5.
2) 令Pi, g={Xi, g}, i=1, 2, …, NP.
3) While迭代次数未达到：
4) 参数调整:设g < L时，所有突变算子的Fmean=Fmean-0.95/gmax, Cr=N(Cr, mean, 0.1);否则，从列表lk, Cr中选择Cr的中值.
5) 利用NSGA-Ⅱ的快速非支配排序方法对所有Pi, g进行解排序，并进行个体信息的截断.
6) for i:= 1 to NP do
7) 目标解选择:从个体信息Pi, g中随机选择一个解作为目标解，记为Xi, g=(xi, 1, g, …, xi, D, g).
8) 变异操作：根据Xi, g从其他个体信息中选择解，生成F=N(Fmean, 0.1)，根据式(15)生成扰动向量V i, g=(v1, g, …, vD, g).
9) 交叉操作：取所选突变算子的Cr均值，设Cr=N(Cr，mean，0.1)，最终生成子代Ui, g=(u1, g, …, uD, g)，其中，
|
(19) |
10) 选择操作:如果Ui, g不受Xi, g支配，则使用Ui, g更新Pi, g，并将Cr的值添加到列表lk, Cr中(如果lk, Cr超过其最大值，则删除其中第一项).
11) end for
12) 令g=g+1
13) end while
14) 输出个体信息.
2.3 优化设计为了能够使算法更早地寻找到最优解，需要使初始种群具有较高的质量.故本文采用一种启发式来生成初始种群，使其能够依据客流量来确定停站次数.
1) 站点权重系数.根据每日各站点客流量与所有站点的客流量的比值当作各个站点的权重系数ω.
2) 停靠次数衰减比率.不同的停站次数产生不同的衰减比例λ.
3) 各站点已有停靠次数.记录各个站点已有列车停站次数η，来调整各个站点的停站的概率.
综上所述，对于列车i各站点j停靠的概率Pij可以表示为
|
(20) |
其中: 
为了验证本文提出的SG-MOSaDE算法的性能，本文采用4个双目标标准测试函数ZDT1，ZDT2，ZDT3和ZDT6对算法的性能进行测试.同时采用反向世代距离(inverted general distance, IGD)指标从收敛性、多样性2个角度对算法进行评价.
|
(21) |
式中:P表示真实Pareto前沿上均匀分布的点的集合；P*为计算得到的一个近似Pareto前沿的解集；min(dis(x, P))表示x与P的最小欧氏距离；|P*|表示优化得到的非劣解的个数.IGD指标体现的是经过算法计算获得的近似Pareto最优解与真实Pareto最优解之间的距离指标.且该指标数值越小，表明计算得到的Pareto前沿的解集与真实解越相似，算法也具有更好的收敛性和多样性.
为了评价所提出的SG-MOSaDE算法的有效性，本文将所提出的SG-MOSaDE算法与NSGA-Ⅱ算法[11]在相同的种群数量和迭代次数下进行比较.将各测试函数的20次独立实验的平均值和标准差作为最终结果进行评价.种群规模NP设为300，最大迭代次数Tmax设为250.比较结果如表 1所示，实验结果表明，所提出的SG-MOSaDE算法在IGD指标均明显优于NSGA-Ⅱ算法，具有较好的收敛性和多样性.最后，SG-MOSaDE算法Pareto前沿对比结果如图 2~图 5所示，可以看出，SG-MOSaDE算法能够找到Pareto最优解.
|
表 1 不同优化算法的IGD对比 Table 1 IGD comparison of different optimization algorithms |
|
图 2 ZDT1比较结果 Fig.2 ZDT1 comparison results |
|
图 3 ZDT2比较结果 Fig.3 ZDT2 comparison results |
|
图 4 ZDT3比较结果 Fig.4 ZDT3 comparison results |
|
图 5 ZDT6比较结果 Fig.5 ZDT6 comparison results |
本文选择广州市某线路2018年1月1日OD客流量为例，通过本文模型确定高速列车最佳开行方案，包括高速列车编组数量和停站方案，以此验证本文模型的正确性和可行性.此线路共有15个站点，其中站点1与站点2均能够当作列车开行的起点.其中站点3, 10, 12, 13, 共4个站点无客流，不具备高速列车停站资格.故其运营线路如图 6所示，“●”表示列车停靠点，“〇”表示列车不停靠点.本线路该日客流总数是56660人，各列车站点的当天客流量可见图 7，由图可得，站点2, 5, 8, 15的客流量较高.
|
图 6 列车运营区段和线路 Fig.6 Train operation section and line |
|
图 7 各站点日客流量 Fig.7 Daily traffic at each station |
当日各区段OD客流量如表 2所示.客票率、列车运营成本以及车站服务费用等数据可见文献[12].另外，令列车的停车时间和起、停附加时间均为5min.设置高铁站点的停靠衰减比率λ为0.7.乘客对于时间花费的价值设置为0.1元/min.
|
|
表 2 各区段OD客流量 Table 2 OD passenger flow of each section |
根据本文已经建立的列车开行方案优化模型和改进设计算法，将表 2的OD客流数据代入，同时，利用初始化种群的启发式算法来进行初始解的生成，样本总数为30，迭代次数为1000.经优化求解后的停站方案如图 8所示，其中左侧0-1变量代表列车编组数量.
|
图 8 开行方案优化结果 Fig.8 Operation plan optimization results |
将本文建立的高速列车开行方案与实际列车开行方案进行对比分析，结果如下所示:
1) 车站服务频率.车站服务频率对比如图 9所示.现行高速列车运行方案中，停站方案与客流没有很好地结合起来，导致列车运能过剩同时不能完全满足旅客出行需求.因此根据客流特点制定停站方案，将有效提升列车的上座率同时使旅客出行需求得到充分满足.由图 9可得，本文方案中高客流站点的服务频率会有大幅下降，而低客流节点的服务频率有了小幅上升.因此采用优化后的高速列车停站方案能够有效降低运营成本，同时更好地满足旅客的出行需求.
|
图 9 服务频率对比 Fig.9 Comparison of service frequency |
2) 其余指标统计.铁路部门经济收益和旅客出行花费等指标统计见表 3.由表 3可知，本文的开行方案在不同指标上均优于实际方案.其中高速列车经济收益增加了1.74×105元，旅客出行总花费降低了6.111×105元, 在提高经济效益的同时，降低了旅客出行的花费.列车总停站次数减少了16次，平均停站次数减少了0.57站，同时滞留旅客减少了421人，不仅节约了停站成本而且更大程度上满足了旅客的出行需求.综上本文提供了一种基于客流的不同指标都优于现行方案的列车停站方案.
|
|
表 3 列车开行方案评价指标 Table 3 Evaluation indexes of train operation plan |
本文在已有研究成果的基础上，建立了一种基于动态客流的列车开行方案的多目标优化模型.并提出了一种改进差分进化算法来进行模型的求解.研究结果表明，优化后的开行方案不仅最大化满足了旅客出行需求，而且在提高铁路部门经济收益的同时降低了旅客的出行花费, 并且优化后的列车总停站次数较原来有所下降，停站方案更加均衡.
| [1] |
Yang L, Qi J, Li S, et al. Collaborative optimization for train scheduling and train stop planning on high-speed railways[J]. Omega, 2016, 64: 57-76. DOI:10.1016/j.omega.2015.11.003 |
| [2] |
Chen D J, Ni S Q, Xu C A, et al.High-speed train stop-schedule optimization based on passenger travel convenience[J/OL].Mathematical Problems in Engineering, [2019-05-30].https://doi.org/10.1155/2016/8763589.
|
| [3] |
Zhang X Q, Li L, Afzal M. An optimal operation planning model for high-speed rail transportation[J]. International Journal of Civil Engineering A, 2019, 17(9): 1397-1407. DOI:10.1007/s40999-019-00401-w |
| [4] |
Qi J, Li S, Gao Y, et al. Joint optimization model for train scheduling and train stop planning with passengers distribution on railway corridors[J]. Journal of the Operational Research Society, 2017. |
| [5] |
苏焕银, 史峰, 邓连波, 等. 面向时变需求的高速铁路列车开行方案优化方法[J]. 交通运输系统工程与信息, 2016, 16(5): 110-116. (Su Huan-yin, Shi Feng, Deng Lian-bo, 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.) |
| [6] |
Huan Y S, Feng S, Guang M X, et al.Schedule-based passenger assignment for high-speed rail networks considering the ticket-booking process[J/OL].Mathematical Problems in Engineering, [2019-05-30].https://doi.org/10.1155/2016/1650839.
|
| [7] |
Yuan W, Liu Y, Wang H, et al. A geometric structure-based particle swarm optimization algorithm for multiobjective problems[J]. IEEE Transactions on Systems Man and Cybernetics:Systems, 2017, 47(9): 2516-2537. |
| [8] |
Wang X, Dong Z, Tang L.Multiobjective differential evolution with personal archive and biased self-adaptive mutation selection[J/OL].IEEE Transactions on Systems, Man, and Cybernetics: Systems, [2019-05-30].https://doi.org/10.1109/TSMC.2018.2875043.
|
| [9] |
张庆磊.基于种群排序策略的差分进化算法变异算子研究[D].泉州: 华侨大学, 2016. (Zhang Qing-lei.Research on differential operators based on evolution algorithm mutation population sorting strategy[D].Quanzhou: Huaqiao University, 2016. ) |
| [10] |
Huang V L, Qin A K, Suganthan P N, et al.Multi-objective optimization based on self-adaptive differential evolution algorithm[C]//IEEE Congress on Evolutionary Computation.Singapore, 2007: 3601-3608.
|
| [11] |
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017 |
| [12] |
苏彦升.基于动态客流的城际客运专线列车开行方案调整优化研究[D].成都: 西南交通大学, 2017. (Su Yan-sheng.Study on adjustment and optimization of intercity passenger dedicated line 's train operation plan based on dynamic passenger flow[D].Chengdu: Southwest Jiaotong University, 2017. ) |