基于差分进化算法的动车组周转接续优化研究

高 杨，郭红戈

GAO Yang，GUO Hongge

（太原科技大学 电子信息工程学院，山西 太原 030024)

(College of Electronic and Information Engineering， Taiyuan University of Science and Technology， Taiyuan 030024，Shanxi， China)

0 引言

动车组周转接续方案是指在给定高速铁路全线列车运行图的背景下，基于车站行车组织原则，具体安排动车组在2条或2条以上运行线路之间的列车运行线接续关系[1]。因此，为提高动车组使用效率[2]，需要合理安排动车组在站的接续，缩短动车组在站的非生产作业时间。

目前，我国很多国内专家以高速铁路为背景，针对动车组周转接续优化问题进行研究，研究提出适合我国国情的动车组运用方式——不固定区段使用方式[3-4]。赵鹏等[5]首次针对动车组不固定区段使用方式进行研究，提出利用匈牙利算法求解动车组周转接续优化问题。赵鹏等[6]还针对动车组运用优化问题，考虑检修约束条件，提出基于概率局域搜索的贪婪算法。王莹等[7]考虑运行线可调的动车组周转优化问题，探讨基于改进广义标号法的分枝定价算法。王文宪等[8]运用蚁群算法求解动车组周转接续优化模型，验证了智能优化算法针对求解大规模动车组运用优化问题的有效性。陈然等[9]考虑车站行车组织人员的意图，设计基于专家系统的改进型蚁群算法求解动车组运用优化模型，提高了动车组的使用效率。

动车组周转接续优化问题是具有离散决策变量性质的组合优化问题，合理安排列车运行图任务间的接续关系，使所有动车组列车在车站周转接续时间总和最小。动车组周转接续优化问题，其复杂性随着动车组数量的增加而不断地变大，经过对智能优化算法进行大量研究后发现，尽管动车组列车周转接续优化运算规模很大，却能得到一个最接近可以被接受的优化解，为这类优化问题的求解提供较好的方法。而差分进化算法(Differential Evolution，DE)作为一种群体智能优化方法，采用浮点数编码，具有实现简单、控制参数少和优化性能好等优点[10]。在组合优化领域，研究者较多地采用离散编码的离散DE算法(Discrete DE，DDE)[11-12]，取得了较好的效果。因此，根据标准DE算法的进化机制，利用其简单高效的优点，提出一种置换策略差分进化算法(Differential Evolution for the Permutations space，DEP)来求解动车组周转优化问题，得到动车组的优化周转方式。

1 动车组周转接续优化问题的数学模型

1.1 模型假设及参数定义

以高速铁路全线、成对列车运行图为前提条件，假设全线上有始发、终到动车组列车能力的枢纽站M个，动车组周转接续在站停留时间包括设置天窗的夜间驻留时间[4]。为了更好地描述问题，首先定义以下变量：N为全线上的车站集合；Nh为全线上的枢纽车站集合，其中h为任意枢纽车站，h=1，2，…，M；C为全线上的列车运行线集合；i，j为全线上的列车运行线，i，j∈C；，别为列车运行图周期内上行和下行终到车站h的列车运行线数目；，分别为列车运行图周期内从车站h上行始发和下行始发的列车运行线数目分别为列车运行图周期内终到车站h和从车站h始发的列车运行线数目mhjxd分别为车站h的上行列车运行线i和下行列车运行线j的终到时刻，其中分别为车站h上行列车运行线i和下行列车运行线j的始发时刻，其中分别为上、下行列车运行线i到达车站h的终到时刻和上、下行列车运行线j从车站h的始发时刻分别为运行线i的终到站和始发站，为在站动车组列车运行线之间的接续关系集合；Xij为决策变量，定义如下。

令为动车组列车在车站h的周转接续时间，可表示为

1.2 数学模型

针对枢纽站动车组周转接续优化问题，可以通过动车组担当列车运行图运输任务的顺序来刻画，即通过运行图任务间的接续关系进行优化，实质是要寻找一个最短的路径，按照列车运行图的要求走完运行图任务中的各个车站。

式中：h∈N；(i，j) ∈CL。

公式⑶是以所有动车组列车在站周转停留时间总和最小为目标函数。公式⑷是列车开行条件，前行列车运行线的终到车站必须与后续列车运行线的始发站一致，并且动车组列车最早可开行时刻应小于接续列车运行线的始发时刻。公式⑸是接续条件，挂线运行的动车组列车之间的接续时间应不小于动车组列车接续时间标准，取CT hij=15 min。公式⑹和公式⑺是惟一性条件，公式⑹表示在站同一时刻，对于终到的动车组列车只能担任一条列车运行线任务；公式⑺表示在站同一时刻，一条列车运行线任务只能由一列动车组列车担任。公式⑻是根据动车组列车运行线之间的接续在时间及地点上的约束，确定列车运行线i与j之间的接续时间是否可以满足接续作业时长。

1.3 置换策略差分进化算法

标准DE算法是种群个体进化的随机计算模型，通过设计优化问题的适应度函数，使对环境适应能力较强的个体存活下来，对环境适应能力较低的个体淘汰，符合适者生存的规律[13]。由于标准DE算法采用浮点数编码，使变异算子的运算对于离散域上正整数编码不封闭。因此，为了使差分变异算子保留原来的计算方式与特点，针对正整数编码的种群初始个体，DEP算法依据抽象代数置换群理论，重新定义变异算子的运算，包括加法、减法和乘法运算。

定义 1 ：设σ1，σ2∈Sx(n)，则置换σ1与σ2的离散加法定义如下。

定义 2 ：设σ1，σ2∈Sx(n)，由σ1σ2* (σ2-1*σ1)，则置换σ1与σ2的离散减法定义如下。

定 义 3 ： 设F∈[0，1]，σ∈Sx(n)，H⊆Sx(n)，由Sx(n)=，则标量F与置换σ的离散乘法定义如下。

式中：k=「F·L⏋，其中数学符号「w⏋表示不超过w的最小整数。

在公式⑾中，F·σ称为置换的截断操作。而置换群σ的生成子集不惟一，则置换σ由简单换位序列的最少表示方式不惟一，因而F·σ通常也不惟一。因此，为了设计一个切实可行的变异策略，根据文献[13]生成集的产生方法，采用一个随机的冒泡排序(Randomizes Bubble Sort algorithm，RandBS)算法，这样可以得到置换σ的最短简单换位序列，具体执行步骤如下。

步骤1：初始化集合CC，用来保存置换的交换位置序列。

步骤 2 ：INV={z |σ(z) ＞σ(z+ 1)}，即集合INV包含置换σ到单位元的一种简单交换排序。

步骤3：如果集合INV≠Ø，则执行步骤4；否则执行步骤9。

步骤4：从集合INV中，随机取一个元素z并删除。

步骤5：交换置换σ的第z个元素和第(z+ 1)个元素，得到一个新的置换σ。

步骤6：把置换的交换序列τ z,z+1保存到集合CC中。

步 骤 7： 如 果z＞ 1 并 且z- 1 ∉INV， 并 且σ(z- 1) ＞σ(z)，则将 (z- 1)保存到集合INV中；否则执行步骤8。

步骤 8：如果z＞n- 1 并且z+ 1 ∉INV，并且σ(z+ 1) ＞σ(z+ 2)，则把 (z+ 1)保存到集合INV中；否则返回步骤4。

步骤9：将集合CC中的元素按逆序排列并输出。

定义1、定义2给出非空集合A上的2种二元运算⊕和Θ，定义3给出A上的一元运算⊗，且假定运算⊗的优先级高于⊕和Θ，则标准差分变异算子重新定义为

2 基于DEP算法的动车组周转接续优化

2.1 解的表示与初始化

由于枢纽车站Nh的到达列车与始发列车数目相同，即，因而枢纽车站Nh的动车组周转接续关系可以表示为D×D的矩阵；又根据公式⑹和公式⑺惟一性条件，定义动车组周转接续关系矩阵的横向表示车站终到动车组列车数量，纵向表示车站始发动车组列车数量；如果在车站Nh，将挂线运行第i条到达的动车组列车运行线接续第j条始发列车运行线，则=1，否则

采用正整数排列的编码方法，建立车站Nh终到车次—始发车次接续对，作为DEP算法的初始个体，正整数在排列中的位置表示终到列车，整数值表示始发列车。因此，建立正整数1 ～n的随机排列σl(l=1，2，…，NP)，将其作为初始种群的个体。

2.2 差分进化操作

DEP算法的差分进化操作包括变异、交叉和选择操作。设第l个目标个体、变异个体和试验个体分别为，和。

2.2.1 变异

DE算法在个体进化过程中，选择合适的控制参数F对算法的优化性能具有重要的影响作用，借鉴文献[14]提到的方式对F的调节策略计算如下。

式中：fr0，fr1，fr2分别是 3 个随机个体σr0，σr1，σr2的适应度函数值，Fmin=0.1；Fmax=0.9。

对于目标个体，变异个体产生方式具体步骤如下。

步骤3：采用RandBS算法，执行置换δ的截断操作，即S=RandBS (δ)。

步骤4：计算k=「F·L⏋。

步骤5：把置换赋值给。

步骤6：从l=1，……，k，对置换按位置序列Sl进行交换排序。

步骤7：结束，得到变异个体。

2.2.2 交叉

在变异操作之后，对目标个体和变异个体进行交叉操作。为保留个体优良信息及避免最优解遭到破坏，在二项式交叉策略基础上，在个体编码中随机设置交叉点并进行部分基因交换，具体操作步骤如下。

步骤1：随机设置交叉点p，1 ＜p＜n。

步骤3：产生区间(0，1)内的随机数rand (0，1)，如果与中的元素不重复，rand (0，1) ＜ CR，则

步骤4：将变异个体向量中不同于中剩余的元素按照随机排列的顺序依次放到中空缺的位置。

2.2.3 选择

为了评估每个个体对于式中目标函数值的优劣，采用“贪婪”选择策略，根据目标个体和试验个体u gl的目标函数值f(·)来选择最优个体。为了避免DEP算法搜索停滞，引入一定选择概率的贪婪选择策略来更新种群，具体操作方式为

式中：r是区间[0，1]随机产生的数；tg=max{0，Q－△1，Q－△2}，其中Q为选择参数，是[0，1]区间的常数，△1，△2为相对适应度值的偏差量，即

3 仿真实验与结果分析

仿真实验分为2个部分。第一部分仿真实验分为4组，每组包括车站Nh到达动车组列车数目D取值不同的3个算例，确定DEP算法的控制参数。第二部分仿真实验以武广客运专线的长沙站为例，验证DEP算法在求解动车组周转接续优化问题方面的有效性。仿真实验在Matlab环境下编程，在2.50 GHz 的 Intel 双核 CPU 及 Win10 操作系统的电脑上运行。

3.1 DEP算法参数设置

DEP算法参数初步设置：NP取值为5D，10D；F取值为0.5；交叉率CR取值为0.9，选择参数Q取值为0.01，0.02[15]，这样构成12种组合。选择车站到达列车数目(或从车站始发的列车数目)D为20，50，100共3个算例，每个算例运行20次，运算迭代次数的最大数目为1 000，将车站Nh动车组周转接续时间的平均相对偏差率(the Average Relative Percentage Deviation，ARPD)和最优解(Best)指标值作为响应值，得到4×3×2=24个数据点，数值实验结果如表1所示。在表1中，ARPD和Best指标值中的最优解用粗体表示；指标值ARPD按照以下公式计算

式中：Algi为算法独立运算求解第i次得到的最好结果；Best为算法独立运算求解20次得到的结果中的最短动车组周转接续时间。

表1 数值实验结果Tab.1 Numerical experimental results

表1给出了DEP算法在车站到达列车数目的3个规模算例下获得的Best值和ARPD值。根据指标值ARPD的定义：该计算结果值越小，表明算法找到的最优解在收敛性和多样性上越趋向参考解。可见，对车站到达列车数目的3个规模算例，算法在NP取值为10D所得Best值比NP取值为5D时具有明显的优势，相应地ARPD值也较好，因而NP取值为10D较合适。同时，算法在选择参数Q取值为0.02的情况下所得的Best值比Q取值为0.01时较好；对20组动车的较小规模，Q取值为0.02所得ARPD值较小。而对于50，100组动车组列车的较大规模算例，Q取值为0.02情况下所得的ARPD值明显差于Q取值为0.01。

针对选择参数Q的取值，选择上述3个算例，比较DEP算法在NP取值为10D，Q取值为0.01，0.02情况下的收敛性能及求解质量，独立运行求解20次平均最短接续时间的收敛曲线，分别如图1—图3所示。

图1 车站到达列车数目D =20时的收敛曲线Fig.1 Convergence curve of the number of trains arriving at the station, D=20

图2 车站到达列车数目D =50时的收敛曲线Fig.2 Convergence curve of the number of trains arriving at the station, D=50

图1、图2、图3的结果表明，对车站到达列车数目D取值为20，100的算例，选择参数Q取值为0.01的情况下，DEP算法仅需较少迭代次数即可达到收敛，然而不能求得最优的动车组周转方案，仅是一个局部最优解；Q取值为0.02情况下，DEP算法虽说需要更多的迭代次数才能达到收敛，但却可以获得全局最优解。而对50组动车组列车的规模，Q取值0.01比Q取值0.02对DEP算法的收敛速度更快，但都能取得相同的最优值。综上所述，在动车组周转优化问题中，DEP算法的选择参数Q取值为0.02更为合适，具有更好地平衡算法快速收敛特性和全局最优解2个特点。

图3 车站到达列车数目D =100时的收敛曲线Fig.3 Convergence curve of the number of trains arriving at the station, D=100

3.2 DEP算法求解动车组周转接续优化问题

3.2.1 数值及收敛性

选取武广客运专线的长沙站为实例，2018年春运期间长沙南站(CS)—广州南站(GZ)区间开行36对/d动车组列车(全部为运营列车)，各列车的到发时刻如表2所示[16]。

运用DEP优化算法求解动车组周转优化问题。通过上述初步实验分析，NP取值为10D较为合适；在小规模动车组周转优化问题中，选择参数Q取值应为0.02较为合适，DEP算法参数设置如表3所示。DEP算法在实例中运行20次得到在站所有动车组列车接续时间的最大值、最小值和均值±方差，DEP数值结果如表4所示，DEP收敛性能如图4所示。

从表4看出， DEP算法取得较好的最大值、最小值及均值，由此可说明DEP算法的可行性。

从图4可以看出，DEP算法尽管需要更多的迭代次数才能收敛，但获得了更好的全局最优解。因此， DEP算法不仅能寻得车站动车组列车周转接续最短接续时间，而且具有较好的收敛性能。

表2 长沙站(CS)动车组列车的到发情况Tab.2 Arrival and departure of Changsha Station EMUs

表3 DEP算法参数设置Tab.3 DEP algorithm parameter settings

3.2.2 CS站动车组列车的接续

根据表2中CS站动车组列车的终到、始发时刻，针对CS站的36对/d动车组列车，运用DEP算法进行计算，得到所有动车组列车在站最短周转接续时间总和为14 379 min，平均动车组列车接续时间为399.42 min，CS站动车组周转接续关系如表5所示。

由表5可知，CS站的始发列车和终到列车之间的折返接续状况较理想， CS站始发列车和终到列车均在同一周期发生折返接续，而且接续时间相对均衡。由此证明，用DEP算法求解动车组周转优化问题可行，而且DEP算法能够较好地平衡算法快速收敛性和全局最优解2个特点。

表4 DEP数值结果Tab.4 Numerical result of DEP

图4 DEP的收敛性能Fig.4 Convergence performance of DEP

表5 CS站动车组周转接续关系Tab.5 Relation between train turnover and continuity of Changsha Station EMUs

4 结束语

为了使所有动车组在站停留时间总和最小，构建高速铁路动车组列车周转接续优化数学模型，并且运用DEP算法进行求解。该DEP算法采用正整数排列编码，借鉴连续空间DE算法的基本特征，通过产生相邻交换次数最佳的随机冒泡排序算法策略来定义差分变异算子，使其能直接作用在正整数排列搜索空间，同时修正交叉策略，采用具有一定选择概率的贪婪选择策略来更新种群，避免个体在进化过程基因块的破坏，提高算法寻找动车组最优周转方案的有效性。最后，以武广客运专线的长沙站为例进行仿真实验，针对长沙站动车组周转接续优化问题，DEP算法具有较强的寻优能力和鲁棒性，体现收敛速度和全局最优解的折中优势，得到很好的效果。