铁路客运过站径路优化模型研究

铁路客运过站径路优化模型研究

列车经过的路线是铁路的入口业务，列车占用的路线是出发业务的起点。列车通过的路径优化是连接客运和货运的综合优化问题。旅客列车过站径路优化克服了接车进路排列、到发线运用、发车进路排列等3个单项优化的不足,突出了优化方案的整体性。文献对旅客列车过站进路优化进行了研究。文献将旅客列车过站径路选择划分为接车作业进路、占用到发线和发车作业进路的分项选择,对任意2列列车的各种接发车作业进路和到发线选择进行相容性约束,以接发车作业进路和到发线运用效用最大为优化目标,建立旅客列车过站径路优化的0-1规划模型,求解时首先将问题转化为最大权和独立集,并设法剔除一些变量以缩小问题规模,然后利用分枝切割法进行求解。文献注意到旅客列车接发车作业进路唯一确定旅客列车占用的到发线,以接发车作业进路为决策,到发线和道岔占用相容性为约束,建立到发线运用和一端咽喉接发车作业进路综合优化的0-1规划模型,针对该问题的特征,提出极大列车进路方案及其剔除邻域系概念,依此设计模拟退火算法。相比之下,文献中模型的决策变量数明显少于文献,其模拟退火算法比文献的分枝定界法具有更强的求解能力。在文献综合优化一端咽喉接发车作业进路排列与到发线运用的基础上,本文进一步综合优化全站的接发车作业进路排列与到发线运用问题,即旅客列车过站径路优化问题。在给定铁路客运站站形布局和列车运行图的前提下,以旅客列车接发车作业进路为决策,以道岔和到发线占用相容性为约束,在尽可能多地为相对重要的旅客列车安排过站径路的条件下,以旅客列车过站径路方案的接发车作业进路和到发线运用效用最大为优化目标,建立旅客列车过站径路优化的0-1规划模型,并设计了基于极大列车过站径路方案剔除邻域系的模拟退火算法,求解旅客列车过站径路优化问题。1道岔占用及过站径路由于旅客列车过站径路优化问题是接发车作业进路排列和到发线运用的综合优化问题,而接发车作业进路唯一确定旅客列车占用的到发线,所以只需要确定旅客列车的接发车作业进路,便可确定旅客列车过站径路。所有旅客列车过站径路必须彼此相容。这种相容性体现为2个方面:首先是道岔占用相容性,即同一道岔在同一时刻最多只能被1项作业占用;其次是到发线占用相容性,即同一条到发线在同一时刻最多只能被1列列车占用。描述道岔占用相容性时,需要确定作业占用的道岔及占用时间。作业占用的道岔由作业所选进路决定,而作业占用道岔时间则需要根据列车起始位置、运行速度、列车长度、作业起始时刻、进路解锁方式、道岔所处轨道电路区段位置等来综合确定,具体计算方法参见文献。描述到发线占用相容性时,需要确定列车占用的到发线及占用时间。列车占用的到发线由接发车作业进路决定,而列车占用到发线的时间由列车运行图确定。在满足道岔和到发线占用相容性的基础上,确定旅客列车过站径路时,应尽量排列长度短、道岔少的接发车作业进路,所占用的到发线应符合到发线的使用要求,方便旅客乘降。值得注意的是,旅客列车过站径路方案与列车运行图是配套的。当调整列车运行图时,相应地也要调整旅客列车过站方案,如果列车到达强度超过车站接发车能力,无法为全部列车排列过站径路,则应尽可能多地为相对重要的列车安排过站径路,以减少运行图的调整工作量。综上所述,旅客列车过站径路优化问题是在满足道岔和到发线占用相容性的基础上,尽可能多地为相对重要的列车排列长度短、道岔少的接发车作业进路,所占用的到发线符合到发线的使用要求、方便旅客乘降。2列车占用到发线方案的确定记列车集为I,到发线集为W,列车i(i∈I)的进站端为o(i),出站端为d(i),o(i)与到发线w(w∈W)之间的第k条进路为Rko(i)wko(i)w,k=1,2,…,n(o(i),w),到发线w与d(i)之间的第k条进路为Rkd(i)w,k=1,2,…,n(w,d(i))。记列车i的接车作业为i(0),发车作业为i(1);对于b=0,1,记作业i(b)所在咽喉区的道岔集为V(i(b))。对于列车i,在办理接车作业i(0)时,必须选择进站端i(i)至某条发线之间的1条进路,即对于i∈I,有∑w∈Wn(o(i)‚w)∑k=1xki(0)w=1(1)∑w∈W∑k=1n(o(i)‚w)xki(0)w=1(1)式中:xki(0)w为0-1变量,若作业i(0)选择进路Rko(i)w,则其值为1,否则为0。相应地,在办理发车作业i(1)时,必须选择某条到发线至出站端d(i)之间的1条进路,即对于i∈I,有式中:xki(1)w为0-1变量,若作业i(1)选择进路Rkd(i)w,则其值为1,否则为0。作业i(0)与i(1)选择的进路唯一确定列车i占用的到发线。引入0-1变量ziw,若列车i占用到发线w,则其值为1,否则为0,则对于i∈I,w∈W,有列车占用到发线时必须满足到发线占用相容性约束,即同一条到发线在同一时刻最多只能被1列列车占用,因此需要在列车、到发线、时间3维空间进行约束。注意到只有列车进入到发线的时刻才可能破坏相容性,所以只需要在列车进入到发线的时刻检查到发线占用相容性约束,将约束限制在列车和到发线2维空间范围内。记列车i占用到发线的时间为[ti,t′i],对于i∈I,w∈W,则到发线占用相容性约束可表示为排列接发车作业进路时必须满足道岔占用相容性约束,即同一道岔在同一时刻最多只能被1项作业占用。对于列车i,记其作业i(b)占用道岔v的时间为[ti(b)v,t′i(b)v],与到发线占用相容性约束类似,对于i∈I,v∈V(i(b)),进路相容性约束可表示为式中:yi(b)v为0-1变量,若作业i(b)占用道岔v,则其值为1,否则为0。yi(b)v的取值由作业i(b)选择的进路决定,对于i∈I,v∈V(i(0)),有相应地,对于i∈I,v∈V(i(1)),有yi(1)v=∑k‚w∶v∈Rkd(i)wxki(1)w(7)在满足到发线占用相容性约束的条件下,列车占用到发线应尽量符合到发线固定使用方案,并且乘降人数较多的列车应尽量停靠在邻近车站出入口的到发线上,以方便旅客乘降。记列车i占用到发线w的效用为ciw,若列车i满足到发线w的使用要求,则ciw>0,否则,ciw=0。在满足符合到发线使用要求的基础上:到发线w越靠近出入口ciw的值越大;列车i的乘降人数越多ciw的值越大;列车i占用到发线w越符合到发线固定使用方案ciw的值越大。将到发线运用效用最大作为第1优化目标,即maxE=∑i∈Ι∑w∈Wciwziw(8)在满足道岔占用相容性约束的条件下,接发车作业应尽量选择长度短、道岔少的进路,以提高作业效率。对于列车i,记进站端o(i)至到发线w的第k条进路的效用为cko(i)w,到发线w至出站端d(i)的第k条进路的效用为ckd(i)w,进路长度越短、经过道岔越少则效用越大,反之效用越小。将接发车作业进路效用最大作为第2优化目标,即将上述目标函数式(8)和式(9)归一化,得到新的目标函数其中0≤α1,α2≤1,α1+α2=1。由此可得旅客列车过站径路优化的0-1规划模型M1:式(10);式(1)—式(7)。值得注意的是,模型M1并不一定总是有解的,当某一时段列车密集到达强度超过车站能力时,车站无法为所有列车安排过站径路,只能尽可能多地为相对重要的列车安排过站径路。为此,对于i∈I,松弛约束条件式(1)和式(2)如下∑w∈Wn(o(i)‚w)∑k=1xki(0)w≤1(11)∑w∈Wn(w‚d(i))∑k=1xki(1)w≤1(12)引入列车i的等级权重ei(列车i的等级越高,ei越大),足够大的罚因子β和γ,将目标函数式(10)扩展如下maxΗ=∑i∈Ι∑w∈W[α1ciwziw+α2(n(o(i)‚w)∑k=1cko(i)wxki(0)w+n(w‚d(i))∑k=1ckd(i)wxki(1)w)]-∑i∈Ιei[β(1-∑w∈Wn(o(i)‚w)∑k=1xki(0)w)+γ(1-∑w∈Wn(o(i)‚w)∑k=1xki(0)w)](13)由此可将模型式M1扩展成为模型M2:式(13);式(3)—式(7),式(11),式(12)。当模型M1可行时,模型M2与之等价,并且目标函数值相等;当模型式(M1)不可行时,模型M2也可行,由于β和γ为足够大的罚因子,最优解为列车等级总权重最大前提下,接发车作业进路和到发线运用效用最大的过站径路方案。3极大列车过站径路方案由于模型M2是0-1线性整数规划问题,约束条件与变量数较多,特此选择模拟退火算法求解。这里省略模拟退火算法的通用框架,借鉴文献的思想构造模拟退火算法的邻域系,模拟退火计划表将在算例中给出。模型M2的1个可行解对应1个列车集及其相容过站径路方案(其他列车不安排过站径路),其中列车集可表示为J⊂I,相容过站径路方案可表示为在i∈J范围内满足约束条件式(1)—式(7)的X(J)={xk′i(0)w,xk″i(1)w:k′=1,2,…,n(o(i),w),k″=1,2,…,n(w,d(i)),i∈J,w∈W}为了缩小搜索范围引入极大可行解的概念:对于模型M2的可行解(J,X(J)),如果X(J)不存在可行性扩展,即对于任何j∉J,均使得X(J)∪{xk′j(0)w,xk″j(1)w:k′=1,2,…,n(o(j),w),k″=1,2,…,n(w,d(j)),w∈W}不满足约束条件式(1)—式(7),则称(J,X(J))为极大可行解,也称为极大列车过站径路方案。借助于极大列车过站径路方案的概念,构造极大列车过站径路方案(J,X(J))的k剔除邻域。首先从J中任意剔除k列列车得J′,然后对J′进行极大化扩展,即寻找列车集J″⊂I-J′,使(J′∪J″,X(J′∪J″))构成极大列车过站径路方案,其中X(J′∪J″)=X(J′)∪{xk′j(0)w,xk″j(1)w:k′=1,2,…,n(o(j),w),k″=1,2,…,n(w,d(i)),j∈J″,w∈W}满足上述条件的所有(J′∪J″,X(J′∪J″))构成极大列车过站径路方案(J,X(J))的k剔除邻域系。值得注意的是,对J′进行极大化扩展过程中,是在完全保持J′的过站径路方案X(J′)不变的基础上进行的。J″可以通过对列车j∈I-J′按照随机顺序进行极大化扩展,相应的过站径路只需在已占用到发线和道岔的剩余网络中求解即可。不满足极大化扩展条件的列车及其过站径路方案不需重复尝试。之所以选择极大列车过站径路方案作为搜索对象,一方面在于极大列车过站径路方案比它的任何子方案因安排了更多列车的过站径路而优越;另一方面在于按照上述极大化方法,很容易从当前极大列车过站径路方案的邻域中求出新的极大列车过站径路方案。4到发线运用效用以某客运站为例,运用上述模型和算法为18:00—0:00时段的旅客列车安排过站径路。该客运站的站形布局如图1所示,其中Ⅰ,3,5道用于接发下行列车,Ⅱ,4,6,10道用于接发上行列车,Ⅰ和Ⅱ道为正线,8道为机走线。10道为接近车站出入口的到发线。该客运站18:00—0:00时段到发列车见表1(单、双数编号的列车分别为下、上行列车)。根据列车性质、到发线使用要求和位置,确定的到发线运用效用见表2。简便起见,仅考虑到发线运用效用最大,不考虑进路效用,进路采用1次解锁,左端咽喉作业占用道岔时间为1min,右端咽喉为2min,平衡因子α1取1,α2取0;惩罚因子β,γ均取10000.0,始发和终到列车列车等级权重取10.0,其他列车等级权重取5.0,邻域系采用2剔除邻域系。模拟退火计划为:初始温度取20000.0,温度下降比例取0.9,温度低于10时采用等步长下降,步长取0.5,同一温度的迭代次数取200,温度低于0.5或接受概率在20次迭代无改变时算法终止。通过计算所得的过站径路方案效用为27720,具体方案见表3。过站径路方案对应的到发线运用方案如图2所示。由图2所示的到发线运用方案可见,上行方向列车均安排在用于上行列车接发作业的4,6,10道,由于20:00—23:00时段下行旅客列车到达强度超过下行方向到发线数,使得下行方向列车T19和T39被迫分别占用6道和4道。注意到列车T39被安排在4道,而没有安排在更靠近出入口的6道,这是由于T20的发车作业与T39的接车作业在时间上冲突,只有将T39安排在4道才能为2项作业排列平行进路,这正体现出到发线运用与接发车作业进路之间的密切联系,也反映了综合优化到发线运用与接发车作业进路的必要性。另外,本文未考虑到发线运用的均衡性。5列车过站径