离所时间限制下动车组交路计划优化研究

郭倩倩，王振宇，林柏梁

(1.石家庄铁道大学 河北省交通安全与控制重点实验室，河北 石家庄 050043；2.石家庄铁道大学 交通运输学院， 河北 石家庄 050043；3.北京交通大学 交通运输学院，北京 100044)

动车组交路计划是编制动车运用计划与检修计划的基础,是列车运行图车次合理接续的依据。在运输实践中,一般先根据列车运行图勾画出动车组交路,然后以动车组交路为基础编制运用与检修计划。故优化动车组交路,可以有效地减少动车组运用数量,科学地配置动车组资源。此外,对于提高动车组的运用与检修管理水平亦具有重要的意义。科学地安排动车组交路是完成图定运输任务的前提,也是保障动车组列车安全运行和提高动车组运用效率的关键。截至2021年底,我国高速铁路(以下简称“高铁”)营业里程超过4万km,动车组保有量达4 153标准组。为保证动车组安全高效运行,其交路与检修计划优化问题得到业内研究人员的广泛重视。

目前,国内外学者对动车组交路计划优化问题进行了大量深入的研究。国内外学者分别考虑动车组的检修[1-10]、多车型[1,5]、多基地[1,4-5]、可改编(重联)[6,12-15]、空车回送[6]、动车所的库存能力[6,10]、列车路径[5,11]等条件建立数学模型,并设计不同的优化算法进行求解。耿敬春等[1]构造了在考虑综合维修条件下多基地、不同型号的动车组周期性运用计划编制的数学模型,并运用计算机模拟方法研究给定运行图条件下合理配置动车组套数、存车线数量及动车段设备规模等问题。王忠凯等[2]以减少动车组使用数量、降低检修成本为优化目标,建立动车组运用计划和检修计划一体化编制的整数规划模型,并设计了求解模型的模拟退火算法。李华等[3]设计接续的里程累计变量和时间累计变量为检修约束,建立动车组交路计划的整数规划模型,运用粒子群算法思想,设计求解算法。江政杰等[4]建立考虑动车段/所一级检修能力约束的多目标整数规划模型,采用基于重要性分级的分层序列法求解模型。钟庆伟等[5]以降低综合运营成本和总空驶里程等为优化目标,建立基于列车车次的可改编动车组运用优化混合整数线性规划模型,并设计了一个基于路径生成的迭代逼近算法,能够快速得到满足日常维修限制的动车组运用计划。郑亚晶等[6]在考虑动车组的检修、空车回送、重联编组等约束条件的基础上,以最少动车组运用数目为目标,提出动车组流量模型,用Cplex软件求解得到全局最优解。Giacco等[7]研究短期维修条件下全网铁路的动车组运用计划。Marti等[8]通过引入动车组维修的约束条件,调整动车组交路计划。Borndörfer等[9]考虑动车组运用的时间和距离检修等约束,以复合网络为基础描述动车组运用问题。Chung等[10]针对韩国铁路列车运行计划问题,考虑车辆段存放能力和检修能力等约束条件,以交路运行里程均衡性为目标,建立了一个混合整数规划模型,设计基于改进精英策略的混合遗传算法求解,并用韩国铁路实际数据验证了算法的有效性。Cadarso等[11]建立列车路径与动车组分配的综合优化模型,并提出基于benders分解的启发式算法求解,最后利用西班牙铁路的数据验证了该算法的稳定性和可行性。Abbink等[12]以早高峰期座位短缺最少化为目标,研究动车组的分配问题。Alfieri等[13]在单线铁路上建立整数规划模型,优化动车组周转计划。Peeters等[14]考虑旅客运输服务、计划的鲁棒性以及动车组周转费用等因素,建立动车组周转日计划的数学模型,并设计分支定价法进行求解。Fioole等[15]在引入动车组改编作业的基础上,结合列车运行图和旅客实际数量,研究动车组运用计划的编制问题。

以上对动车组交路优化方面的研究,大多数仅从检修约束,如动车所检修能力、动车组检修时间、检修里程以及检修成本等方面考虑,几乎没有在离所时间约束下动车组交路计划编制的文献。但在实际运营中动车组如果离所时间过晚,则会造成动车组运行时间较短,无法承担长距离交路任务。举个比较极端的例子,动车组22:00离所,24:00回所理论上也是交路方案的备选之一,但是从动车所管理人员角度考虑,他们认为这是显然不合理方案,不予考虑。

本文基于列车接续网络图,建立离所时间约束下动车组交路优化模型,以满足动车组日常运用需求为基础,以缩短动车组接续总时间与降低动车组交路总损失里程为双重目标,提高动车组的运用效率。

1 离所时间限制下动车组交路问题的背景

动车组交路计划[16]是基于给定列车运行图,规定列车任务间动车组接续关系及一级检修地点,将列车运行图中列车任务组合成若干运用交路的计划,是编制日常动车组运用计划的基础性计划。动车组的交路计划主要与动车组的一级检修关联,根据动车组交路的定义可以将其理解为动车组在两次一级检修之间所担当的列车车次有序接续集合。而动车组的二级修则与动车组的上线计划相关联,动车组上线运用计划就是安排动车组去担当列车车次或交路的问题,同时,要考虑动车组二级修各个检修项目的检修周期。相对于一级检修和二级检修,动车组的高级检修的检修周期和扣修周期都比较长,对动车组的交路计划和运用计划影响相对较小,其往往与春、暑运相关联。因此,本文在研究动车组交路计划时,仅考虑动车组的一级检修。

根据动车组管理的实际情况,动车组担当完一条交路后,需要进行一级检修。以包含4个车站,1个动车所,12个列车的实例来说明,研究离所时间约束下动车组交路计划优化问题的必要性。A站列车车次的相关信息见表1,其中A站为动车所相连接的车站,B、C、D站为折返站。

表1 A站列车车次相关信息

基于上述车次数据分别给出2种交路方案,见图1、图2。图1由3个交路构成,交路1为:1—2—9—10,交路2为11—12—5—6,交路3为7—8—3—4。需要注意的是,交路3的开始车次为7,即其开始时刻为17:19,这也意味着担当该交路任务的动车组在17:19离所开始执行该任务。图1中的交路计划没有考虑动车组最晚离开动车所的时刻要求,因此会存在17:19开始的交路,但是这在铁路运营组织中显然是不符合实际的。在实际运营中,动车所一般对动车组最晚离所时间有要求。图2有两个交路,车次1—2—3—4构成交路1(红色线条),该交路的开始时刻为第一天的10:05,即车次1的始发时刻,担当完车次1和2后回到动车所过夜,第二天分别担当车次3和4的任务,最终回到动车所进行一级检修。车次5—6—7—8—9—10—11—12(蓝色线条)构成交路2,该交路的开始时刻为第一天8:05,担当完车次5、6、7、8后回到动车所过夜,第二天担当车次9、10、11、12的任务,最终回到动车所进行一级检修。不同于图1,图2的交路方案中,交路的开始时刻均在14:00之前,满足实际运营条件。在实际的运营组织中,各个动车所离所时刻要求有所不同,例如,某铁路局要求的动车组最晚离所时刻为14:00。

图1 不考虑离所时间限制的动车组交路

图2 最晚离所时刻为14:00的动车组交路

图1和图2分别表示不考虑离所时刻约束的动车组交路图和最晚离所时刻为14:00的动车组交路图。对比两种方案可以看出,图1中交路3的发车时刻过晚,即,同一列车运行图,不同的车次组合方案构成的交路计划也不尽相同,使得交路开始的时刻存在差异。如果对动车组的最晚发车时刻加以限制,从优化理论看,增加该约束可以减少寻优的搜索范围。因此,在研究动车组交路计划优化问题时,有必要考虑离所时刻这一约束条件,这在动车组运营组织中是真实存在且具有实际意义的。离所时刻约束下动车组交路计划就是对于给定列车运行图一个周期内的所有列车,在满足动车组最晚离开动车所时刻、一级检修的时间和里程等约束条件下,实现一定优化目标时,合理确定列车车次之间的接续关系。

2 数学模型构建

2.1 列车接续网络图

通过引入网络理论,以列车车次为网络的节点,以列车车次接续关系和一级检修作为网络的弧,构建动车组列车接续网络[16]。因为交路的起点和终点都是动车所,每一条交路实际上是由列车车次节点、列车车次接续弧和一级检修弧构成的闭合回路。动车组列车接续网络示意图见图3,根据图2中的动车组交路,可以构建两条列车车次接续回路,见图3(a)。为了便于后续数学模型的建立,将列车接续网络中的各条闭合回路通过一级检修弧连接起来,形成一条由所有列车车次节点、列车车次接续弧和一级检修弧构成的闭合回路,见图3(b)。

本文所研究的动车组交路优化问题,基于图3(b)中列车接续网络构建思想,先构造一个包含所有列车车次接续的闭合回路,然后在回路中通过确定哪些列车车次之间安排一级检修,在一级检修弧处进行“切割”,得到的每一条由列车车次构成的接续片段,即是所求的各个动车组交路。

2.2 构建模型的假设

为进一步把问题抽象和简化,建模前作如下假设:

1)不考虑动车所对一级检修能力的限制,对于动车组集中到达动车所的情况,通过人工干预进行调整。

2)每天开行列车的数量及信息是相同的,所有列车的基本属性、一级检修周期等基础数据均已知,且在交路计划编制中保持不变。

3)只考虑动车组的单车种、单基地问题,对于多车种、多基地问题,可以采用本文研究的思路将其转化为多个子问题求解。

2.3 符号定义

模型涉及的相关符号,包括集合、参数、变量的定义见表2。

2.4 数学模型

为表述动车组交路计划中列车车次接续关系、一级检修作业安排及修程标准约束,需要给出以下变量的表达式。

若车次i的到达车站等于车次j的始发车站,并且车次j的始发时刻与i的到达时刻相差时间间隔大于列车之间接续的最小时间标准,则tij等于车次j的始发时刻减去车次i的到达时刻;同理,若车次i的到达车站等于车次j的始发车站,但是车次j的始发时刻与i的到达时刻相差时间间隔小于列车之间接续的最小时间标准,那么可以考虑接续第二天的相同列车车次,此时接续时间增加1 440 min;若两个列车车次不满足接续地点的要求,规定车次的接续时间为无穷大。tij为

( 1 )

( 2 )

( 3 )

动车组交路优化问题的目标函数一般为动车组使用数量最少、接续时间最少、检修次数最少和动车组交路损失里程最少等。在列车运行图确定的情况下,所有列车的运行时间和运行里程是不变的,动车组接续时间最少和动车组使用数量最少是等价的,动车组交路损失里程最少和检修次数最少是等价的,可任选其一作为目标函数[17]。本文选择动车组交路中列车车次接续时间Z1与动车组交路总损失里程Z2作为优化目标函数,即

( 4 )

( 5 )

为将两个目标的量纲统一,将目标式( 4 )和式( 5 )进行加权(权重系数为w1和w2),取最小值作为目标函数,即

minZ=w1Z1+w2Z2

( 6 )

1)列车车次接续唯一性约束

对于每一个列车车次,只能有一个紧前车次和一个紧后车次,这种关系在逻辑上表现为唯一性约束,即

( 7 )

( 8 )

2)动车组一级检修逻辑约束

若在车次i与j之间安排一级检修,则车次i与j既要前后接续,又要满足一级检修条件,即

yij≤xijθiji,j=1,2,…,ni≠j

( 9 )

3)动车组一级检修里程周期和时间周期约束

在实际运营组织中,动车组的运行里程一般允许存在超期检修,但是不同级别的检修作业有着不同的超期检修比例,一级检修作业的超期检修比例λ一般为10%,即

lj≤(1+λ)Lcyclej=1,2,…,n

(10)

与里程周期约束不同,时间周期不存在超期的情况,即要严格满足检修时间周期约束,因此不存在超期检修百分比,即

tj≤Tcyclej=1,2,…,n

(11)

4)动车组最晚离所时间约束

动车组的离所时刻要早于要求的最晚离所时刻,即交路的开始时刻要早于要求的最晚开始时刻,即

(12)

5)避免子回路逻辑约束

本文的建模思路是先构造一个包含所有列车车次的回路,这种接续关系通过变量xij体现,然后在回路中通过确定哪些列车车次之间安排一级检修,通过变量yij体现,最后得到各个交路。则需要注意的是,在寻求包含所有车次的回路时要避免出现子回路。在这个层面上,可以通过引入TSP问题中避免出现子回路的经典约束,即

ui-uj+nxij≤n-1i,j=1,2,…,n

(13)

0≤ui≤n-1i=1,2,…,n

(14)

式中:ui和uj分别为车次i和j在回路中的位置编号。

式(14)表示位置编号的取值范围,考虑0到第n-1个位置。若i和j在回路中前后接续,那么ui-uj必然等于-1,此时式(13)成立;若二者不接续,则式(13)恒成立。式(13)和式(14)确保得到的回路中避免出现子回路。

6)0-1变量约束

xij,yij∈{0,1}i,j=1,2,…,ni≠j

(15)

综上所述,考虑离所时间约束下的动车组交路计划优化模型为

minZ=w1Z1+w2Z2

s.t. 式( 7 )～式(15)

3 模拟退火算法

2.4节模型中的lj和tj存在累乘的非线性高次项,使得所建模型为非线性0-1整数规划模型,不易用数学规划求解器精确求解,因此本文选用模拟退火算法对模型进行求解。模拟退火算法是一种基于Metropolis Monte Carlo迭代求解策略的启发式随机搜索算法,其思想是通过对模型中的复杂约束进行预处理,将其作为惩罚项添加到目标函数中,与目标函数共同构成能量函数,然后通过模拟物理界中的退火过程实现对模型的启发式求解,主要包括以下几个部分。

3.1 能量函数

为了降低模型的求解复杂程度,需要将模型中的复杂约束条件作为惩罚项加入到目标函数中。这里的复杂约束主要是约束式(10)～式(12),将其乘以惩罚系数作为惩罚项添加到目标函数中。3个约束对应的3个惩罚项分别为

(16)

(17)

(18)

式中:β1、β2、β3分别为相应的惩罚系数;H1、H2、H3分别为3个复杂约束对应的惩罚项。

原模型的目标函数为

(19)

将其与上述惩罚项结合,所得能量函数为

G(X)=Z+H1+H2+H3

(20)

3.2 初始温度的确定

在确定初始温度T0时,利用Aarts等[18]提出的方法,先随机地产生m个解,则有

(21)

(22)

式中:ρ0为给定的初始接受率,一般取0.9～0.99;m+、m-分别为能量函数G(Xn)值增加、减少的解数;Δavg为m+个能量函数增加值的平均值。

3.3 初始解的生成

首先定义两个集合Ω1、Ω2,其中Ω1用来存放始发站为检修站(运用所连接站)的车次,Ω2用来存放终到站为检修站的车次,然后为每个车次生成一个集合,该集合内存放可以与该车次相接续的其他车次,最后额外定义一个集合Ω3用来存放已经得到的可行解。

从Ω1集合中随机选取一个车次作为整体回路的首位,然后根据约束式( 7 )～式( 9 )在首位车次确定的基础上,依照上述逻辑约束随机确定一条回路。即在首位车次确定的基础上,从该车次对应的集合中随机选取一个车次进行接续,同时确保该车次在该回路中没有出现过,按照该种思路,依次选取车次接续,若选中车次已经存在于当前回路中,则重新随机选取直至所有车次均被包含在回路中。在确定回路中的最后一个车次时,要确保该车次的终到站为检修站,即确保最后一个车次来源于Ω2。最后把该回路存放到Ω3中,记为一个可行解。

3.4 邻域解的生成

邻域解的生成与初始解的生成方法思路一致,采用生成初始解的方法生成邻域解。若生成的新解已经存放在Ω3中,则从当前新解中随机选中一个车次,扰动其紧后车次,即在当前车次对应的集合中重新选取一个车次,然后按照相同思路接续,直至所有车次都被包含在整体的回路中。

3.5 温度的更新策略

降温方法为

(23)

式中:参数δ一般取0.4;α一般取0.95;kd为高低温迭代次数的分界点,一般为70;φ(Tk)为Tk温度下能量函数期望值的标准差。

3.6 算法步骤

Step1确定初始温度T0。记当前的降温次数k=0,转Step2。

Step2记迭代次数n=0。初始温度下,按照3.3节的方法生成初始解。

Step3当经过k次降温后,在温度Tk下,记第n-1次迭代后的解为Xn-1,按照3.4节中的方法生成邻域解,计算出对应的函数值能量G(Xn),转Step4。

Step4利用Metroplis抽样准则对当前解进行检验,若G(Xn)-G(Xn-1)<0,则无条件接受Xn代替Xn-1;若G(Xn)-G(Xn-1)>0,则以概率γn(Tk)接受邻域解。γn(Tk)为

(24)

转Step5。

Step6算法收敛终止判定。本文设置了两个终止准则:一种是接受率小于给定的阈值时,另一种是能量函数在多次迭代过程中保持不变,两个准则满足一个即结束该算法。否则,转Step7。

Step7按3.5节中的内容进行降温,记降温次数k=k+1,置迭代步数n=0,返回Step3。

4 算例分析

4.1 数据

本文以太原南动车所配属的CRH2A动车组车型为例,选取2021年10月该车型担当的部分车次作为基本数据,进行算例验证分析。太原南站部分列车车次见表3,所研究车次的开行区段覆盖车站11个。动车所与太原南站相连,采用单点检修方式,可为本动车所的动车组提供一级检修。

表3 太原南站部分列车车次

根据TG/CL 127—2017《铁路动车组运用维修规则》[22],CRH2A型动车组的一级检修时间周期Tcycle为48 h,里程周期Lcycle为4 000 km,动车组超期检修的百分比λ为10%,列车接续时间标准tconnect为15 min。

4.2 优化计算

本文所提出的考虑最晚离所时间具有实际背景意义,为了突出构建模型的有效性,在求解算例,分别考虑了两种场景进行计算。首先是不考虑最晚离所时间约束,即忽略模型中的约束条件式(12),利用所提出的模拟退火算法对模型进行求解;同理,在考虑最晚离所时刻约束的基础上,对算例进行重新计算,最终对比两种场景下的计算结果,从而说明本文所建模型的有效性和真实性。

根据本文设计的求解步骤,采用VC++程序设计实现,在Core 2.4 GHz的个人计算机上运行。这里ρ0取值为0.9,β1、β2均取值为50(通过多次试验计算确定),w1、w2取值为0.5。结合实际情况,要求动车组离开动车运用所的最晚时刻为14:00,即Tlatest取值为14:00,晚点惩罚系数β3取值为99(通过多次试验计算取值)。两种场景下的动车组交路优化方案见表4。

表4 两种场景下的动车组交路优化方案

由表4可知,两种场景下得到的交路数量一样,均为7个交路,但具体的交路方案存在差异。对比表4中结果可以发现,场景二与场景一相比,仅有交路2、3、6有所变化,其余交路方案则相同。此外,场景一的交路方案中,交路2的离所时刻为15:12,即过晚发车,这正是由于没有考虑离所时刻约束所导致的情况。相反,场景二的交路方案中均满足最晚离所时刻限制,即离所时刻均早于14:00。

同时,由于列车车次是已知的,并且得到的交路数量也一样,则说明两种场景下交路方案的检修里程利用率相等,但是总运行时间则有所不同。从表4可以看到,场景一中交路运行时间最短为1 226 min,最长为2 308 min;场景二中交路运行时间最短为1 528 min,最长为2 288 min。从运行时间指标来看,虽然场景一得到的交路方案较好,但是存在过晚发车的情况。此外,还统计分析了两种场景下交路方案的总接续时间。列车车次数量一定,各个车次的图定运行时间一定,则总运行时间的不同体现在总接续时间上。经计算,场景一中动车组的总接续时间为5 153 min,而场景二中动车组的总接续时间为5 205 min。场景二的总接续时间仅比场景一多52 min,但是场景二中得到的交路方案可以很好地避免动车组过晚离所。

综上分析,在考虑动车组离所时间约束下,本文所建模型可以很好地避免动车组的过晚离所发车,使动车组的运营更加符合实际运输生产需求。

5 结论

本文研究离所时间限制下的动车组交路优化计划,在建立数学模型时将动车组最晚离开动车所时刻作为约束条件,以动车组接续总时间最少和动车组交路总损失里程最少为优化目标,构建离所时刻约束下的动车组交路优化模型。所建立模型为非线性0-1整数规划模型,为提高求解效率,设计模拟退火启发式算法。最终通过算例分析验证本文提出模型和算法的有效性。结果表明:与不考虑离所时刻约束相比,离所时刻约束下的动车组交路优化方案,可以很好地避免动车组的过晚离所发车,更加符合运输生产实际需求。

本文所建模型是非线性规划模型,求解有一定的难度,因此,在建模前做了简化,如仅考虑单车种、单基地的动车组以及列车运行图是已知的情况等,今后可在考虑多车种、多基地动车组情况下,研究动车组交路和列车运行图的协调优化问题。