环形排列的动车组运用和检修一体化优化模型

环形排列的动车组运用和检修一体化优化模型

该列车使用计划包括具体的旅行时间、出发时间、车站、运营路线和各级维护，是客运线路的基本运营计划之一。由于动车组在客运专线的固定成本投资中占有较大比重,折旧费用和维修费用都较高,因此如何合理使用动车组,减少动车组的使用数量是动车组运用计划的首要目标。借鉴国内外动车组使用经验以及近年来对于动车组应用的研究发现,动车组不固定区段运用是效率较高的运用模式。文献首次提出动车组不固定区段使用模式,并利用紧凑指派的思想通过模拟方法得到动车组运用方案;文献在不固定区段使用的基础上提出采用回送车的方法,通过灵活调配合适的动车组来完成各次运输任务使得各个车次之间的接续时间尽可能短,从而达到提高使用效率的目的;文献在平日动车组运用计划已知的条件下,通过衡量各列车之间接续质量,以一定概率优先满足高质量的列车接续为原则,不断生成好的交路段,构成假日动车组运用计划;文献首先利用文献中算法构造出初始单基地动车组运用计划,进而通过列车分组将其分解成多基地动车组运用计划,并通过路段交换方法不断构造新的动车组运用计划;文献将动车组运用计划编制问题分为交路段生成和基于交路段的交路生成两个问题分步求解;文献将动车组的接续运行与检修计划制定过程转化为TSP问题,并运用计算机模拟方法确定给定列车运行图条件下合理配置动车组套数、存车线数量及动车段设备规模等。本文在不固定动车组运用区段的前提下,以全部列车形成的环形排列为动车组交路,在环形排列中以检修时间间隔和里程间隔为约束,列车接续费用最少为优化目标,建立动车组运用计划和检修计划的一体化优化模型。通过引入罚值函数和三交换邻域结构,设计求解模型的模拟退火算法,最后进行实例分析。1u2009必要的检修时间间隔动车组运用计划问题可简单地叙述如下:给定一些列车,运用若干动车组承担这些列车的运输任务,需要安排动车组的运用交路,满足以下要求:使得动车组数量尽可能少,接续费用尽可能少;按要求在动车组的交路中安排日常检修和一级检修;使得动车组之间所承担的运行里程均匀。对于给定的n列列车l1,l2,…,ln,列车li(i=1,2,⋯,n)的始发和终到站分别为sdi和sai,出发和到达时刻分别为tdi和tai,运行里程为dYi,运行时间为ΤYi=(tai-tdi)modΤ(1)式中,T为一天内的总时间。当动车组完成列车li的运输任务后紧接着承担列车lj的运输任务时,一项主要费用为接续时间。运输任务的接续时间可以分为本站接续和异站接续两种情形来计算,即当列车li的终到站sai与列车lj的始发站sdj相同时,需要花费的最小接续时间间隔为标准接续时间Tbj;当sai与sdj不相同时,需要花费的最小接续时间间隔为标准接续时间Tbj与站sai至站sdj的运行时间TYij之和,其中ΤYij={dij/vdij≤DXΜdij>DX(2)式中,dij为站sai至sdj的里程;v为动车组的运行速度;DX为异站接续的最大里程限制值;M为充分大的罚值,表明太远的两个站之间不允许进行接续的限制。所以,接续时间ΤJij={tdj-taitdj-tai≥Τbj,sai=sdjortdj-tai≥Τbj+ΤYij,sai≠sdjtdj-tai+Τtdj-tai＜Τbj,sai=sdjortdj-tai＜Τbj+ΤYij,sai≠sdj(3)其实,动车组的数量最少与总接续时间最少是等价的,这是因为总接续时间与列车总运行时间之和等于动车组数量的T倍,而列车运行时间始终是常数。另一项接续费用为接续里程dij,简便起见,可以将接续费用综合表示为Cij=ΤJij+ω⋅dij(4)式中,ω为动车组运行单位里程的费用折合成单位时间费用的折算系数。动车组运行一段时间以后需要进行必要的检修,检修项目分为日常检修、一级检修、二级检修、三级检修、大修等。日常检修、一级检修需要在动车组运行交路中完成,其他维修由专门的维修计划实施,在研究动车组交路时仅限于讨论日常检修和一级检修的安排问题。日常检修的作业内容较为简单,作业时间也较短,可以安排在白天或晚上进行;检修车站必须具有日常检修设备;两次日常检修之间的列车累计行驶里程应在日常检修期望里程的规定波动范围内,虽然没达到规定行驶里程要求,但两次日常检修之间间隔时间已达到日常检修的最长期望检修时间间隔的规定波动范围,也应该进行检修。通常,日常检修在动车组运行3000km或2天以内必须进行一次。一级检修的作业内容相对复杂,作业时间也较长,常常限制在白天进行;检修车站必须具有一级检修设备;两次一级检修之间的列车累计行驶里程应在一级检修期望里程的规定波动范围内,虽然没达到规定行驶里程要求,但两次一级检修之间间隔时间已达到一级检修的最长期望检修时间间隔的规定波动范围,也应该进行检修。通常,一级检修在动车组运行30000km或30天以内必须进行一次。记日常检修的期望里程为D0,波动范围为±ΔD0;期望时间为τ0,波动范围为±Δτ0。同样记一级检修的期望里程为D1,波动范围为±ΔD1;期望时间为τ1,波动范围为±Δτ1。根据日常检修和一级检修在时间和地点上的要求,在列车li与lj之间的接续时间内是否可以完成这些检修任务是完全确定的,引入参变量φij和ψij来描述列车li与列车lj之间是否能够完成日常检修和一级检修,其中φij={1li与lj之间可以完成日常检修0否则(5)ψij={1li与lj之间可以完成一级检修0否则(6)2交路维修交路由于所有动车组构成一个大交路能够很好的满足动车组运用的均衡性,所以动车组的运用交路就是列车l1,l2,…,ln的环形排列lu(1),lu(2),…,lu(n),日常检修方案和一级检修方案可以分别引入变量xu(i)u(i+1)(i=1,2,…,n)和yu(i)u(i+1)(i=1,2,…,n)来表示,具体含义为xu(i)u(i+1)={1lu(i)与lu(i+1)之间安排日常检修0否则(7)yu(i)u(i+1)={1lu(i)与lu(i+1)之间安排一级检修0否则(8)变量xu(i)u(i+1)应满足相关约束:其一,日常维修必须在具备条件的两次列车接续时间内维修,即xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,⋯,n(9)其二,在整个交路中至少进行一次日常维修,即n∑i=1xu(i)u(i+1)≥1(10)其三,在每次日常维修后的规定行程范围或规定时间范围内进行下一次日常维修。记p´(d,j)、q´(d,j)分别为环形排列lu(1),lu(2),…,lu(n)中与运行线j刚好满足日常检修里程下限和上限的运行线序号,p´(τ,j)、q´(τ,j)分别为环形排列lu(1),lu(2),…,lu(n)中与运行线j刚好满足日常检修时间下限和上限的运行线序号,则对于j=1,2,…,n,当xu(j-1)u(j)=1时,min{q´(d,j),q´(τ,j)}∑i=min{p´(d,j),p´(τ,j)}xu(i)u(i+1)=1成立的条件是p´(d,j)、q´(d,j)、p´(τ,j)、q´(τ,j)满足以下4个约束:p´(d,j)-1∑i=jdYu(i)＜D0-ΔD0≤p´(d,j)∑i=jdYu(i)(11)q´(d,j)∑i=jdYu(i)≤D0+ΔD0＜q´(d,j)+1∑i=jdYu(i)(12)p´(τ,j)-1∑i=j(ΤYu(i)+ΤJu(i)u(i+1))＜τ0-Δτ0≤p´(τ,j)∑i=j(ΤYu(i)+ΤJu(i)u(i+1))(13)q´(τ,j)∑i=j(ΤYu(i)+ΤJu(i)u(i+1))≤τ0+Δτ0＜q´(τ,j)+1∑i=j(ΤYu(i)+ΤJu(i)u(i+1))(14)上述两组约束保证交路内至少进行一次日常维修,同时任何一次日常维修以后的规定时间内一定进行下一次日常维修,这样的约束下一定可以获得合乎要求的日常维修方案。另外,在考虑接续时间尽可能少的情况下,不会形成两个及其以上的维修交路(最少接续时间下自然形成的多个维修交路除外)。变量yu(i)u(i+1)也应满足类似约束。综上所述,动车组运用计划的数学模型如下:minn∑i=1Cu(i)u(i+1)(15)s.t.xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,…,n(16)n∑i=1xu(i)u(i+1)≥1(17)min{q´(d,j),q´(τ,j)}∑i=min{p´(d,j),p´(τ,j)}xu(i)u(i+1)=1‚若{xu(j-1)u(j)=1∑i=jp´(d,j)-1du(i)Y＜D0-Δ0D≤∑i=jp´(d,j)du(i)Y∑i=jq´(d,j)du(i)Y≤D0+Δ0D＜∑i=jq´(d,j)+1du(i)Y∑i=jp´(τ,j)-1(Τu(i)Y+Τu(i)u(i+1)J)＜τ0-Δ0τ≤∑i=jp´(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)∑i=jq´(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)≤τ0+Δ0τ＜∑i=jq´(τ,j)+1(Τu(i)Y+Τu(i)u(i+1)J)j=1,2,⋯,n(18)yu(i)u(i+1)≤ψu(i)u(i+1)i=1,2,⋯,n(19)∑i=1nyu(i)u(i+1)≥1(20)∑i=min{p˝(d,j),p˝(τ,j)}min{q˝(d,j),q˝(τ,j)}yu(i)u(i+1)=1‚若{yu(j-1)u(j)=1∑i=jp˝(d,j)-1du(i)Y＜D1-Δ1D≤∑i=jp˝(d,j)du(i)Y∑i=jq˝(d,j)du(i)Y≤D1+Δ1D＜∑i=jq˝(d,j)+1du(i)Y∑i=jp˝(τ,j)-1(Τu(i)Y+Τu(i)u(i+1)J)＜τ1-Δ1τ≤∑i=jp˝(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)∑i=jq˝(τ,j)(Τu(i)Y+Τu(i)u(i+1)J)≤τ1+Δ1τ＜∑i=jq˝(τ,j)+1(Τu(i)Y+Τu(i)u(i+1)J)j=1,2,⋯,n(21)xu(i)u(i+1),yu(i)u(i+1)=0,1i=1,2,⋯,n(22){u(1),u(2),⋯,u(n)}={1,2,⋯,n}的环形排列(23)式中,p˝(d,j)、q˝(d,j)分别为环形排列lu(1),lu(2),…,lu(n)中与运行线j刚好满足一级检修里程下限和上限的运行线序号;p˝(τ,j)、q˝(τ,j)分别为环形排列lu(1),lu(2),…,lu(n)中与运行线j刚好满足一级检修时间下限和上限的运行线序号。在模型(式(15)～式(23))中,u(i)表明lu(i)为排列在位置i的列车;列车lu(i)的前一列列车为lu(i-1),后一列列车为lu(i+1)。若i-1<0,则i-1表示i-1+n;若i+1>n,则i+1表示i+1-n,这一项环形排列的运算特征在全文都是如此,其他地方不再做特殊说明。3模型式15的建立为便于求解模型(式(15)～式(23)),设法消去约束条件(式(17),式(18),式(20),式(21)),将其以罚值的形式转入目标函数中,构建一个与之等价的优化模型。特此,对于式(17)和式(20),引入函数X={0∑i=1nxu(i)u(i+1)≥11∑i=1nxu(i)u(i+1)=0(24)Y={0∑i=1nyu(i)u(i+1)≥11∑i=1nxu(i)u(i+1)=0(25)所以,式(17)和式(20)可以通过罚值M1和M2转化成目标函数中新的一项Μ1X+Μ2Y式(18)可以通过罚值M3转化成目标函数中新的一项Μ3∑j=1n(xu(j-1)u(j)(∑i=min{p´(d,j),p´(τ,j)}min{q´(d,j),q´(τ,j)}xu(i)u(i+1)-1)2)(26)式(21)可以通过罚值M4转化成目标函数中新的一项Μ4∑j=1n(yu(j-1)u(j)(∑i=min{p˝(d,j),p˝(τ,j)}min{q˝(d,j),q˝(τ,j)}yu(i)u(i+1)-1)2)(27)综上所述,模型式(15)～式(23)可以转化为如下等价的罚函数模型min∑i=1nCu(i)u(i+1)+Μ1X+Μ2Y+Μ3∑j=1n(xu(j-1)u(j)(∑i=min{p´(d,j),p´(τ,j)}min{q´(d,j),q´(τ,j)}xu(i)u(i+1)-1)2)+Μ4∑j=1n(yu(j-1)u(j)(∑i=min{p˝(d,j),p˝(τ,j)}min{q˝(d,j),q˝(τ,j)}yu(i)u(i+1)-1)2)(28)s.t.xu(i)u(i+1)≤φu(i)u(i+1)i=1,2,…,n(29)yu(i)u(i+1)≤ψu(i)u(i+1)i=1,2,⋯,n(30)xu(i)u(i+1),yu(i)u(i+1)=0,1i=1,2,⋯,n(31){u(1),u(2),⋯,u(n)}={1,2,⋯,n}的环形排列(32)这些约束条件就是模型式(15)～式(23)中的约束条件(式(16),式(19),式(22),式(23))。动车组运用计划的罚函数模型(式(28)～式(32))目标函数中p´(d,j)、q´(d,j)、p´(τ,j)、q´(τ,j)、p˝(d,j)、q˝(d,j)、p˝(τ,j)、q˝(τ,j)为j的函数,与当前环形排列相关,相应地消去约束条件式(18)和式(21)。4环式列车在列车之间的接头关系基于三交换模拟退火算法求解动车组运用计划模型(式(28)～式(32))的框架如图1所示,其中,初始环形排列状交路可通过随机选择交路起点,并将各列车在不考虑检修条件的前提下连成交路得到,模拟退火计划表参考文献确定,而三交换邻域系的构造是算法实现的关键。由于篇幅有限,下面将具体叙述三交换邻域的构造方法。边交换法、点交换法、单点移动法等都是一些有效的邻域系构造方法,但注意到模型所求解的是有向环形排列,其中点对应于列车,点之间的有向弧对应于列车之间的接续,而二交换法(置换两条边)对应颠倒2列列车的接续关系,势必难于继承原有优化结果,所以,这里采用三交换法(置换三条边),除交换边对应的列车接续关系发生变化外,其他