基于MTSP的机车运用分析与优化

Analysis and Optimization of Locomotive Application Based on MTSP

摘要

不固定牵引区段机车交路极大地提高了机车运用效率，是机车运用工作的发展方向。基于多旅行商问题模型(MTSP)分析武汉局集团公司江岸机务段机车运用情况，并提出优化方案。武汉局集团公司地处全国铁路网中部和地理位置中心，是全国铁路的重要枢纽，也是华中地区综合交通体系的重要组成部分，对于疏解全路车流起到了至关重要的作用。通过结合江岸机务段不同机车交路，针对不固定机车交路牵引方式建立数学模型，在满足列车开行和机车整备约束的条件下，以机车使用台数最少为目标，给出目标函数的具体求解。最后，结合不同分界口机车交路的MTSP模型，给出武汉局集团公司机车运用优化建议，对其他地区的机车运用工作也具有一定指导意义。

Abstract

Greatly improving the efficiency of locomotive operation, Locomotive routing in unfixed traction section represents the future of locomotive operation. This paper analyzed the locomotive routing of Jiangan Locomotive Depot of China Railway Wuhan Group Company, and put forward the optimization scheme. Located in the middle of the national railway network and the geographical center, Wuhan Railway Group plays a vital role in relieving the traffic flow of the whole country as an important railway hub in China and also an important part of the comprehensive transportation system in Central China. By combining different locomotive routes in Jiangan Depot, a mathematical model was established for the traction mode of unfixed locomotive routes. Under the condition of meeting the constraints of train running and locomotive maintenance, the objective function was solved with the minimum number of locomotives used. Finally, via the MTSP model of locomotive routing at different boundary crossings, the optimization suggestions on locomotive operation in Wuhan Group Company were given, which is also of certain guiding significance to locomotive operation in other areas.

关键词

机车运用 / MTSP模型 / 机车交路 / 优化 / 江岸机务段

Key words

Locomotive Operation / MTSP Model / Locomotive Routing / Optimization / Jiangan Locomotive Depot

我国铁路最为常用的机车运转制是肩回式机车运转制，即机车在担当机务本段相邻的2个或多个区段的列车牵引任务时，除了需入折返段整备外，每次返回基本段所在站，均需入段整备^[1]。肩回式机车运转制分为固定牵引方式或不固定牵引方式。固定牵引方式，即1台机车只能担当某一区段的列车牵引任务，例如中国铁路北京局集团有限公司丰台机务段担当丰台西—阜阳北交路的机车出库后只能担当该区段的列车牵引任务，而不能担当丰台西—济西的列车牵引任务，固定牵引方式的机车运转制相对简单，便于机车调度员在日常工作中均衡安排机车运用与检修整备；缺点是容易导致车流等机车的现象，效率不高。不固定牵引方式指的是1台机车既可以担当A—B区段，也可以担当A—C区段，甚至B—C，B—D区段的列车牵引任务。不固定牵引方式可以使机车运用效率大大提高，加速机车周转，有利于机车与车流的无缝衔接；缺点是机车运用相对复杂，跨铁路局集团公司的机车长交路机车运行到其他铁路局集团公司可能存在管理盲区，容易导致机车超整备公里运行，带来安全隐患。以中国铁路武汉局集团有限公司(以下简称“武汉局集团公司”)江岸机务段机车交路为例，基于多旅行商问题(Multiple Traveling Salesman Problem，MTSP)模型对江岸机务段不固定牵引区段机车交路进行分析^[2]，结合多个分界口涉及的机车交路，在满足列车开行和机车整备约束的条件下，以机车使用台数最少为目标函数，对模型进行求解^[3]，根据计算结果对该地区机车运用提出优化建议。

1　基于MTSP的机车运用模型设计

1.1　不固定牵引区段机车运用与MTSP

MTSP是旅行商问题(Traveling Salesman Problem，TSP)的延伸，MTSP指的是给定n个城市，有m个商人从各自城市出发，分别走1条路线，使得每个城市有且有1个商人走过，最后回到出发地，且总里程最短^[4]。不固定牵引区段机车运用方式可转化为MTSP模型，当某铁路局集团公司在不同交路区段使用同一集合的机车，机车在满足相应约束条件的情况下，可在几个交路间任意周转，达到使用机车最少的目标。

不固定牵引区段机车运用问题与MTSP相同点为：某车站上下行列车运行线数目相当于多旅行商问题中的城市数目，机车交路数相当于旅行商数，机车从18：00起出发，满足所有列车运行线，最后回到18：00，即成闭合回路，相当于旅行商从各自城市出发，分别走1条线路，每个城市有且只有1个商人走过，最后回到出发地。机车使用台数最少相当于MTSP问题中商人总旅程最短；两者的不同点为：多旅行商问题中商人可以朝任意方向行走，只有空间约束，没有时间约束。但转化为机车运用问题时，机车只能沿时间增大的方向前进。

1.2　江岸机务段机车运用现状

江岸机务段共配属机车415台，其中HXD1B型280台、HXD3C型65台、DF4型30台、DF7型27台、HXN3B型13台。其中HXD1B型机车运用最为广泛，图定担当所有分界口机车交路的列车牵引任务，在不同线路牵引定数不一致的情况下，可以满足江岸机务段所有线路牵引需求。HXD1B型机车担当京广线(北京西—广州)武汉北至郑州北、武汉北至岳阳北/株洲北、孟宝线(孟庙—宝丰)、宁西线(合肥—新丰镇)信阳北至南阳西、漯阜线(漯河东—阜阳北)、武九线(武汉北—九江西)等交路的货物列车牵引任务。其中武汉北至郑州北、孟庙至宝丰、武汉北至阜阳北、漯河东至阜阳北等机车交路图定支配192台，武汉北至岳阳北/株洲北、武汉北至九江西/向塘西等机车交路图定支配88台，根据运输需要可调整跨线支配。机车在武汉北站、信阳站、漯河站、阜阳北站可跨线使用。

江岸机务段HXD1B型干线货运机车执行不固定牵引区段机车运转制，实现了“全局一台车”，符合MTSP模型。

1.3　模型建立

1.3.1　列车开行约束

假设该机车运用模型中列车开行均为单机牵引且为列车成对区段，这也符合基本列车运行图的编制和武汉局集团公司江岸机务段机车运用现状。列车开行约束是指按照列车运行图的规定，某站需在某时刻开行某次列车，那么机务部门必须保证有满足该次列车牵引定数需求、相应机车交路以及时间要求的机车。

1.3.2　机车整备约束

机车整备是机车运用、机车调度过程中不可忽视的一个环节。机车在走行一定的里程后，需安排入库整备作业，若机车超整备公里运行，会带来一系列安全隐患，危及行车安全。所以，在进行机车运用模型求解时，机车整备约束是必须要考虑的一项内容。按照中国国家铁路集团有限公司自2022年1月开始执行的最新《机车整备管理规则》规定：机车整备是指在机车运用周转过程中，自机车入段交接至出段交接时止，为保证机车运用安全、质量稳定所做的技术作业，主要包括油砂补给、排污保洁、维护保养、检查检测、数据分析、机能试验、报修活件处理等，以及为配合以上作业所进行的生产作业计划编制、机车移动、调车、防溜、隔离开关操作等辅助作业。铁路局集团公司要科学安排机车交路，提高机车整备效率，确保机车按规定的整备周期进行整备，严禁机车超整备周期使用^[5]。机车整备周期如表1所示。

1.3.3　机车在站技术作业时间约束

机车在车站需要进行必要的技术作业，包括机车乘务员换班、站场调车作业、机车与车列连挂、列车制动机试验以及必要的机车整备检查时间。因此机车从到达某站起，到从某站出发时止的时间应大于等于机车在站技术作业时间，这也是机车运用建模中必须要考虑的一重约束^[6-7]。

1.3.4　数学模型

（1）定义参数。S表示有机车换挂作业的车站；L_i 表示列车运行图中铺画的第i次列车车次，其中i=1，2，…，M；M为列车总数；T_d表示列车始发时刻；T_a表示列车终到时刻；t表示列车运行时间，min；T_k表示机车在该站最短折返时间，min；n_i 表示牵引L_i 机车的台数，台；D_i表示牵引列车L_i的走行距离，km；d_i 表示机车出发变量，为0-1变量，当L_i 表示从S站出发并换挂机车时，取1，反之取0；x_ij 表示机车接续变量，为0-1变量，当机车牵引L_i 后接着牵引L_j 时，取1，反之取0；t_{ij}为机车在车站S的折返时间，min，其计算公式为

⑴

（2）目标函数。以机车使用台数最少为目标，可以转化为机车全周转时间最短^[8]。因为机车全周转时间的总和=运用机车台日数×24，即运用机车台日数与机车全周转时间成正比例关系^[9-10]。Z表示以使用机车台数最少为目的的目标函数，其表达式为

Z=\mathrm{m}\mathrm{i}\mathrm{n}(x_{ij}{t}_{ij}+t_i)⑵

式中：t_i为第i次列车的运行时间，min。

（3）约束条件有以下5个。

列车在站到达的接续机车总数不超过牵引列车的机车台数，可表示为

{\sum }_{j=\mathrm{1}}^M{x}_{ij}{n}_{ij}=N_i\forall i\in M⑶

列车在站出发的牵引列车的机车总数不超过到达列车的机车台数，可表示为

{\sum }_{i=\mathrm{1}}^M{x}_{ij}{n}_{ij}=N_j\forall j\in M⑷

机车接续必须满足机车在站折返时间标准，可表示为

{\sum }_{k=\mathrm{1}}^K{d}_{jk}{t}_{ij}\ge T_k\forall t_{ij}>\mathrm{0}⑸

式中：k为车站代号；d_jk 为列车L_j 的区段出发车站。

机车只能在同一车站接续，可表示为

{\sum }_{k=\mathrm{1}}^K{x}_{ik}{d}_{jk}=\mathrm{1}\forall x_{ik}=\mathrm{1}⑹

机车走行公里需满足机车整备周期，可表示为

{\sum }_{k=\mathrm{1}}^K{x}_{ik}{D}_i\le \mathrm{3}\mathrm{000}⑺

2　算例分析

2.1　固定牵引区段机车周转制算例

以武汉北站出发到达的列车为例，以武汉北站为机务本段，选取武汉北—阜阳北、武汉北—株洲北部分区段列车和直通列车的机车交路，按照固定牵引区段机车周转制进行计算^[11-12]。武汉北—阜阳北列车运行时刻表如表2所示，武汉北—株洲北列车运行时刻表如表3所示。

当机车交路为固定牵引区段运转制时，设机车在武汉北、阜阳北、株洲北的折返技术作业时间T均为120 min。

若执行固定牵引区段机车运转制，即武汉北—株洲北、武汉北—阜阳北间的机车交路相互独立，机车不混用。经过测算，武汉北—株洲北区段需使用18台机车，方能满足该区段列车牵引需求，机车在武汉北需入库整备，部分机车没有达到整备周期，一定程度浪费了整备能力；武汉北—阜阳北区段需使用16台机车，方能满足该区段列车牵引需求，机车在武汉北同样需入库整备。如果按照固定牵引区段机车运转制，这2个区段共需机车34台。

2.2　不固定牵引区段机车周转制算例

若执行不固定牵引区段机车运转制，江岸机务段机车在以上交路区段担当列车牵引任务时，可以打破固定机车交路限制，在满足相应约束的条件下，在这几个交路间任意周转。机车在武汉北站按照MTSP模式，执行不固定牵引区段机车周转制，在满足机车整备周期约束的条件下，机车减少了出入库调车作业走行时间、在库整备作业时间，仅存在站场转线调车作业走行时间，则机车在武汉北站折返技术作业时间可压缩至60 min，且机车在满足机车整备周期的前提下，可以在2个区段任意周转，即机车返回武汉北后，可以去株洲北，也可以去阜阳北。计算武汉北到达机车最早出发时间表如表4所示。

记到达机车最早出发时间比出发列车时刻早为1，否则记为0，则可构造机车到达-出发32×32阶矩阵。以前10对列车为例，可以得到矩阵如下所示。

\left(\begin{array}{cccccccccc}\mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right)

依次构造32×32阶矩阵，使用匈牙利法进行试指派，即可求得江岸机务段机车在武汉北站基于MTSP模型的机车周转图^[13-15]。根据求解，基于MTSP的江岸机务段不固定牵引区段机车运转制在武汉北至阜阳北、株洲北交路使用机车32台。由此可见，基于MTSP的不固定牵引区段机车运转制比固定牵引区段的机车运转制在上述2个区段可以节省2台机车。若将江岸机务段所有货运机车交路均按照MTSP模型进行计算，理论上可以节约30台机车，足以体现基于MTSP的不固定牵引区段机车运转制的优势。

3　机车运用优化建议

（1）在牵引定数一致、使用机车类型一致的区段，推广基于MTSP的不固定牵引区段机车运转制，能够减少机车运用台数，缩短机车全周转时间。可以探索将襄阳机务段汉丹线(武汉—襄阳)货运机车交路加入华中地区基于MTSP的不固定牵引区段机车交路中，在机车整备制度上完善管理细则，做到机车跨段整备，减少机车在枢纽地区的换挂。

（2）探索打通经京广线、宁西线/小厉线(小林—历山)、焦柳线(焦作—柳州)、汉丹线武汉北至信阳北/南阳西/襄阳北至武汉北机车交路，便于疏解南阳西站的压力，南阳西站使用江岸机务段机车不再只有宁西线小林口1个方向，可以根据车流情况，使用江岸机务段机车担当宁西线信阳方向或焦柳线襄阳方向列车牵引任务。目前宁西线、焦柳线新丰镇至襄阳北、信阳北间货运机车交路由中国铁路西安局集团有限公司(以下简称“西安局集团公司”)新丰镇机务段双机HXD3型机车担当，打通江岸机务段机车在武汉北至信阳北/南阳西/襄阳北区段机车交路后，可不使用西安局集团公司新丰镇机务段担当南阳西至襄阳北、信阳北机车交路，减少双机在平原地区牵引定数的浪费。

（3）目前江岸机务段机车交路均由江岸机务段机车乘务员值乘，在一定程度上有利于保证机车质量，但也限制了其机车交路的长度。在满足机车整备周期的基础上，根据车流情况，探索使用江岸机务段机车担当自武汉北出发的单程800~1 000 km的跨局机车长交路，采取跨局轮乘的乘务制度，增加机车日车公里，提高机车运用效率。

（4）目前江岸机务段货运电力机车绝大部分是回到江岸机务本段进行整备，在满足条件的折返段投入整备作业，并与同样配属HXD1B型机车的郑州机务段、向塘机务段签订跨段整备协议，保证机车在外铁路局集团公司按照同样标准进行整备作业，可以减少机车运用过程中存在的超机车整备周期安全风险，使基于MTSP模型的机车运用过程中机车整备约束条件更加容易满足。

(5）精确计算机车整备周期，减少不必要的入库整备。自武汉北整备完毕出库担当武汉北至株洲北交路的机车，返回武汉北后可接续担当武汉北至郑州北、阜阳北、宝丰交路，无需入库整备。其中担当株洲北至郑州北间直达货物列车的机车交路，可根据武汉北站接发能力，部分调整至京广线横店站乘务换班作业。这样有利于提高武汉枢纽的通过能力，使不技术检查作业的列车不进武汉北站，压缩机车全周转时间。

（6）持续推进机车“客转货”工作，将HXD3C型机车回归货运，同时保留HXD3C型机车的双管供风和直供电功能。江岸机务段已实现65台HXD3C型机车的“客转货”任务，该型机车在担当货运任务的同时，可以很方便地担当直供电旅客列车的救援任务。同时，培训部分客运机车乘务员担当货运任务，实现客货动态调整，按照客货兼备、一专多能、动态储备、弹性调剂的原则，实现“宜客则客，宜货则货”。通过机车和机班的“客转货”工作，实现以货补客、货运增量的任务。

（7）利用好《铁路运输组织考核办法》，运用经济手段，合理制定跨局长交路机车在外局占用费，督促铁路局集团公司用好外铁路局集团公司机车，不滞留机车。铁路局集团公司机车调度动态监测江岸机务段机车在中国铁路郑州局集团有限公司、中国铁路上海局集团有限公司、中国铁路广州局集团有限公司、中国铁路南昌局集团有限公司等保有量，加强与上级机车调度的联系，协调在外局的机车及时放回。利用好重点分界口差异化考核手段，对关键分界口涉及的铁路局集团公司调度所、机务段进行考核(奖励)。

（8）建立全路货运机车动态调拨、入助机制，通过连续一段时间的各铁路局集团公司货运机车运用检修概况数据分析以及不同区段列车开行状况耦合分析，得到某段时期机车供应矛盾突出的铁路局集团公司的相应交路区段，寻找机车供应矛盾不严重、机车尚有备用且机型一致的铁路局集团公司，动态调配机车，满足某些区段短时期货运增量的需求，做到“全路一盘棋、全路一台车”。

4　结束语

以武汉局集团公司江岸机务段的机车运用情况为实例，分析基于MTSP的不固定牵引区段机车运转制的货运机车交路。通过将武汉北—株洲北、武汉北—阜阳北区段的机车交路的图定机车周转图勾画过程转化为机车出发-到达矩阵进行求解，证明了基于MTSP的不固定牵引区段机车运转制的优势，并结合计算结果和现场工作实际对武汉局集团公司机车运用工作提出优化建议。由于货物列车采取了组织型的开行方式，其并非完全按图行车，日常临时调整概率较高，故模型理想效果无法完全实现，但基于MTSP的机车运用思想，在实际机车运用中亦有一定的理论意义和较强的实用性。

参考文献

[1] 牟从凯，王慈光，刘伟达. 机车不固定牵引方式的有利性分析[J]. 铁道运输与经济，2010，32(10)：85-89.

[2] 运筹学教材编写组.运筹学(第四版)[M].北京：清华大学出版社，2015.

[3] 张　杰. 机车周转图编制优化及系统设计[D].成都：西南交通大学，2013.

[4] 闫海峰，崔　燚. 编制机车周转图的优化模型[J]. 中国铁道科学，2006，27(4)：123-128.

[5] YAN Haifeng， CUI Yi. Optimization Model of Locomotive Working Diagram[J]. China Railway Science，2006，27(4)：123-128.

[6] 中国铁路总公司 ．铁路技术管理规程[M]．北京：中国铁道出版社，2018．

[7] 王　瑶. 铁路机车周转图编制模型与算法研究[J]. 铁道运输与经济，2008，30(9)：84-87.

[8] WANG Yao. Study on Drawing Model of Railway Locomotive Working Diagram and Its Algorithm[J]. Railway Transport and Economy，2008，30(9)：84-87.

[9] 姜启源，谢金星，叶 俊.数学模型(第四版)[M].北京：高等教育出版社，2010.

[10] FRISCH S， HUNGERLÄNDER P， JELLEN A，et al. Solving a Real-World Locomotive Scheduling Problem with Maintenance Constraints[J]. Transportation Research Part B：Methodological，2021，150：386-409.

[11] 张　杰，倪少权，葛露露，等. 基于机车顺次接续的机车周转图编制方法[J]. 中国铁道科学，2014，35(2)：98-103.

[12] ZHANG Jie， NI Shaoquan， GE Lulu，et al. Method for Establishing Locomotive Working Diagram Based on Sequential Connection of Locomotive Routing[J]. China Railway Science，2014，35(2)：98-103.

[13] 中国国家铁路集团有限公司.铁路机车统计规则[M].北京：中国铁道出版社，2020.

[14] 陶　然，吕红霞，陈广秀. 基于MTSP的机车周转图编制模型与算法[J]. 西南交通大学学报，2006，41(5)：653-657.

[15] TAO Ran， Hongxia LYU， CHEN Guangxiu.Model and Algorithm for Making Locomotive Working Diagram Based on Multiple Traveling Salesmen Problem[J]. Journal of Southwest Jiaotong University，2006，41(5)：653-657.

[16] 何奉道，何冬昀. 基于变异进化的不固定牵引方式双肩回交路机车最优配置算法[J]. 交通运输系统工程与信息，2007，7(2)：88-92.

[17] HE Fengdao， HE Dongyun. A Mutating Evolution Algorithm for Locomotive Diagram with Double Shoulders-Circuit Locomotive Routing by the Mode that Unfixed Traction[J]. Journal of Transportation Systems Engineering and Information Technology，2007，7(2)：88-92.

[18] 卢厚清，王辉东，黄　杰，等. 任务均分的多旅行商问题[J]. 系统工程，2005，23(2)：19-21.

[19] LU Houqing， WANG Huidong， HUANG Jie，et al. Dividing into Equal Task of MTSP[J]. Systems Engineering，2005，23(2)：19-21.

[20] NIELSEN L K， KROON L， MARÓTI G. A Rolling Horizon Approach for Disruption Management of Railway Rolling Stock[J]. European Journal of Operational Research，2012，220(2)：496-509.

[21] ANDRÉS J， CADARSO L， MARÍN Á. Maintenance Scheduling in Rolling Stock Circulations in Rapid Transit Networks[J]. Transportation Research Procedia，2015，10：524-533.

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(P2021X009)