基于模拟退火算法的铁路旅客列车车底套用优化研究*

肖益帆，朱昌锋

(兰州交通大学交通运输学院，甘肃兰州 730070)

铁路旅客列车车底是铁路运输生产组织中的重要资源，合理的车底运用模式对降低铁路运输成本起着至关重要的作用。近年来，随着铁路运输的发展，开行的旅客列车对数逐渐增加，同时也存在着车底运用方式不合理造成的车底在站停留时间过长，车底运用效率降低和车底运行成本增加等问题。文献［1］建立了车底运用的双层指派模型;文献［2］建立了以列车运输能力最大化为目标的整数规划模型;文献［3］分析了采用车底套用模型的优缺点;文献［5－7］主要研究了高速铁路动车组不固定区段运用的优化模型。但上述大部分研究主要针对动车组的不固定区段使用，针对普通旅客列车车底的运用优化又集中在运营成本方面。本文通过考虑不同等级列车间的车底运用和列车晚点对车底运用数量等影响，建立了以旅客列车车底数量为最小的目标模型。

1 变量定义及问题描述

m(m=1，2，…，M)为铁路客运站;

r(r=1，2，…，R)为旅客列车车底;

V={vi=tdi，tfi，tfi'，li，ξdi，ξai}为列车集合。

其中:tdi和tfi分别为列车i的图定始发时刻和终到时刻;tfi'为是列车i实际运行中到达客运站的时刻;li为列车i的等级，ξdi为列车i的始发车站，ξai为列车i的终到车站;ckr为旅客列车车底r的等级k;cmr为旅客列车备用车底r所属的车站m;μi为列车i自身晚点的概率;hi为列车i连带晚点的列车数量;TR为车底在车站的技术作业时间标准。

假设某路网有m个客运站，普通旅客列车、快速旅客列车、特别快速旅客列车可接续不低于同等级列车。但是，备用车底在运用过程中，可不受到列车等级的限制。在列车接续中，需要考虑到列车的晚点问题。以24 h为1个周期，则该车底套跑问题可转化为列车运行网络上具有较多约束条件和目标函数的TSP问题。

2 铁路旅客列车车底套用优化模型建立

我国当前的车底运用基于固定配属制，采取固定区段的使用模式。但是研究发现，不固定区段车底的运用也可能是一种较好的车底运用方式。因此，结合上述2种车底运用模式，可以将运用的车底分为不固定区段使用列车车底和备用车底2种。不固定区段使用列车无固定归属客运段，在整个列车网络内进行运用。备用车底有相应的归属客运段，在结束一次运用过程后，需回到相应的归属客运段;由于列车的晚点具有区间的传播效应，当列车在终到站和终到站前车站晚点时，会对列车的车底运用造成影响，当列车在其他区间晚点时，则可以恢复。

(1)铁路运行图规定每一列旅客列车能且只能分配一列旅客列车车底，同时该列车的等级应不低于被接续旅客列车的等级;

定义决策变量xij判断列车i运行后是否接续列车j，则有:

定义li为旅客列车i等级:

定义crk为不固定区段的旅客列车车底的等级:

由于旅客列车只能由一组列车车底担当，且该车底的等级应不低于相应列车等级，即∀i，j，k，

(2)车底到站后，需进行必要的技术作业，后续列车的始发时刻和前行列车的实际终到时刻差，应满足技术作业时间TR。权重越大则接续的可能性越小，同时使得同等级列车接续的可能性更高。

定义0－1变量Pi:

则有

(3)当列车i属于的运行线路全周转时间大于1个周期结束时间时，该车底只能在下1个周期返回大型客运站，该车底不能再担当其他列车的接续。因此，只有满足列车的全周转时间在1个周期内的车底能够进行列车的接续工作;

(4)列车晚点后，由于列车晚点传播的效应，会造成连带数量的旅客列车晚点。

定义0－1决策变量si:

则在车站n备用列车车底的数量kn为:

(5)由备用车底担当任务时，需要最后返回所属车站m，则当列车j接续列车i由车底r担当列车运用任务时，须满足如下条件。

定义决策变量qrij:

则旅客列车的最短在站停留时间为:

因此，列车车底使用总数为Ntrain－set:

3 算法设计

3.1 解的表示形式

本算法中，解用矩阵 Y=(Y1，Y2，Y3，…，Yn)来表示，Yi=j表示第i次列车终到车站之后，继续担当第j次列车的运行任务，称j为i的接续车次，每次列车采用自然编码。根据解的表示形式，采用两两交换的移动规则，对任一当前解，任选2个不同的终到车次，交换它们担当的车次，即可产生1个新解。

3.2 初始解的产生

任选某一客运中心站的列车时刻表，并对该站的始发终到列车进行顺序编号，初始解为每个终到车次对应的始发车次的编号。例如:1303次列车(编号为i)终到车站后，经过一段时间的整备后，担当1304次(编号为Yi)列车的运行任务。

3.3 温度的控制

根据Δf/t0≈0，Δf为每次邻域移动后目标函数值的增量，由于本文中的目标函数只与相互接续的两个车次的始发终到时刻相关，通过分析不难发现，每次邻域移动后，Δf有以下几种情况，即:0，±1 440。所以，根据Δf/t0≈0，t0越高越好。

采用 T=T × r的降温方式，r=0.95 ～ 0.99，这种降温方法在温度高时降温快，温度低时降温缓慢。理论上终止温度越低越好，最佳状态为0℃，终止温度小于1×10－4℃时，即可停止降温过程。另外，本文采用两数据交换构造邻域，邻域移动次数应不少于C2n次。

针对本模型的实际问题，约束条件处理时应以不影响算法性能和计算的复杂度为前提，在本论文中采取拒绝策略即不满足约束条件时就排除该方案，将0～24 h表示为0～1 440 min，把每一个由时分表示的始发、终到时刻换算成分钟形式。

Step 1指定数据文件名、初始温度、降温系数、终止温度及热平衡次数等参数。

Step 2给定1个初始解S0作为当前解，T=T0，ci=1。

Step 3判断列车i，j是否晚点，若晚点则Pi=Pj=1，否则，Pi=Pj=0。

Step 4判断接续i，j列车的车底是否为备用车底，若为备用车底则pr=pr=1，否则，pr=pripijpjipijpj=0。

Step 5任意交换Yi，Yj，产生邻域解S，检验新解S是否满足约束条件，本文的约束条件为:

(1)每一旅客列车能且只能被分配一车底，同时该列车的等级应不低于被接续旅客列车的等级;

(2)终到车次的终到时刻与其接续的始发车次的始发时刻之间满足整备等时间约束;

若满足上述2个条件转入Step 6，否则转Step 7。

Step 6计算f(S)与f(S0)的差值f，若f＜0，令S0=S，若 f＞ 0，产生1个(0，1)间的随机数 x。若exp(－ f/T)＞ x，则 S0=S。

若f(S0)是历史最优解，则更新最优解;否则，转Step 7。

Step 7 ci=ci+1。如果ci＜ Q，转Step 4;否则，转Step 8。

Step 8如果T ＞ 1 ×10－4，转到 Step 2，否则结束。

4 实例分析

以某铁路网的A，B，C和D 4个站为例。各车站的位置如图1所示。各车站间的径路如表1所示。各车站客车车流信息见表2～5。

图1 铁路网络车站示意图Fig.1 Location of railway passenger stations

表1 铁路网络内列车径路表Table 1 Train routing of railway network

表2 A车站客车车流信息表Table 2 Information of passenger train flow of A passenger station

表3 B车站客车车流信息表Table 3 Information of passenger train flow of B passenger station

K117 A B 20:48 —0.2 2 K179 A B 08:07 — 0.3 1 T817 A B 18:28 — 0.4 1 T167 A B 21:54 — 0.2 2 T201 A B 01:09 — 0.2 3 1918 C B 22:03 — 0.1 2 T198 D B 06:06 — 0.4 1 T138 C B 16:18 — 0.2 3 K126 C B 18:40 — 0.1 1 K132 D B 03:30 —0.1 2

表4 C车站客车车流信息表Table 4 Information of passenger train flow of C passenger station

表5 D车站客车车流信息表Table 5 Information of passenger train flow of D passenger station

根据各站旅客列车车流信息，可计算出车底在站停留时间，可得满足4个车站列车开行方案所需的车底有36组，其中普通旅客列车车底6组，快速旅客列车车底16组，特快旅客列车车底12组。旅客列车在站停留时间如表6所示。

表6 旅客列车在站停留时间Table 6 Stop time at stations of railway passenger trains

用MATLAB计算。其收敛性检验以及初始温度Tf与最优解出现个数的关系如图2和图3所示。

图2 算法收敛性图Fig.2 Convergence of algorithm

图3 初始温度Tf与最优解出现个数的关系Fig.3 Relationship between initial temperature Tf and optimization solutions number

得到列车车底的接续方案如表7－8所示。

通过计算可得调整后的旅客列车车底在站停留时间的总和为16 732 min，比原有的接续方案少7 602 min，可以节约5组车底。根据计算由于每个车站需要1组备用车底，因此，总共可以节约1组车底。

表7 优化后的旅客列车车底接续表Table 7 Optimized train set assignment

表8 优化后的旅客列车车底接续表Table 8 Optimized train set assignment

5 结论

本文针对旅客列车的晚点传播效应，建立了旅客列车车底套用模型，计算方法简便，可操作性强，在实际生产中，还存在着车站的到发线、调集、整备线等均衡运用多方面的因素，这有待进一步研究。

［1］陈 刚，史 峰.铁路旅客列车运行图编制要点分析［J］.铁道运输与经济，2004，26(5):37 －38.CHEN Gang，SHI feng.Analysis on the key points for drawing up passenger train graph［J］.Railway Transport and Economy，2004，26(5):37 －38.

［2］谢金贵，曾 亮，徐昕恺.铁路旅客列车车底套用优化模型的研究［J］.铁道运输与经济，2006，28(12):75－77.XIE Jin-gui，ZENG Liang XUE Xing-kai.Optimization on model of railway passenger train set assignment［J］.Railway Transport and Economy，2006，28(12):75－77.

［3］李 栋.关于利用外局(段)折返客车车底套跑短途旅客列车合理性的探讨［J］.科协论坛，2008(5):43.LI Dong.Study on passenger train set assignment of which is from external railway bureau science＆technology association forum［J］.2008，(5):43.

［4］赵 鹏，富井规雄.动车组运用计划及其编制算法［J］.铁道学报，2006，25(3):1 －7.ZHAO Peng，NORIO Tomii.Train － set scheduling and an algorithm journal of the china railway society［J］.Journal of the China Railway Society，2006，25(3):1 －7.

［5］赵 鹏，杨 浩，胡安洲.高速铁路动车组的不固定区段使用问题［J］.铁道学报，1997，19(2):15 －19.ZHAO Peng，YANG Hao，HU An-zhou.Research on usage of high speed passenger trains on uncertain railroad region［J］.Journal of the China Railway Society，1997，19(2):15－19.

［6］赵 鹏，胡安洲，杨 浩.高速铁路动车组不固定区段使用条件下周转优化问题的研究［J］.北方交通大学学报，1997，21(6):621 －624.ZHAO Peng，YANG Hao，HU An-zhou.Research on the circulating optimization in the condition of using high speed passenger trains in uncertain railroad region［J］.Journal of the China Railway Society，1997，21(6):621－624.

［7］耿敬春，肖荣国，倪少权，等.客运专线动车组周期性运用计划编制的研究［J］.铁道学报，2006，28(4):17－21.GENG Jing-chun，XIAO Rong-guo，NI Shao-quan，et al.Research on periodicity of motor train set scheduling for special lines for passenger traffic［J］.Journal of the China Railway Society，2006，28(4):17 －21.

［8］马建军，许 红，胡思继，等.京沪高速铁路列车运行图指标评价体系的研究［J］.北方交通大学学报，2003，27(5):46－50.MA Jian-jun，XU Hong，HU Si-ji，et al.Study on index evaluation system of train working diagram on jinghu high－ speed railway line［J］.Journal of Northern Jiaotong U-niversity，2003，27(5):46 －50.

［9］孙 焰，刘胤宏，李致中，等.列车运行图的晚点概率分析［J］.长沙铁道学院学报，1994，16(4):83 －89.YANG Yan，LIU Yin-hong，LI Zhi-zhong，et al.The analysis of delaying time probability for the travelling graph of trains［J］.Journal of Changsha Railway University，1994，16(4):83 －89.

［10］杨肇夏，胡安洲，李 菊，等.列车运行图动态性能及其指标体系的研究［J］.铁道学报，1993，15(14):46－56.YANG Zhao-xia，HU An-zhou，LI Ju，et al.A study of the dynamic performance＆index system of the trains operation diagram［J］.Journal of the China Railway Society，1993，15(14):46 －56.