铁路货运机车乘务交路计划编制优化方法

叶玉玲，何嘉棋

（1.同济大学交通运输工程学院，上海 201804; 2.同济大学道路与交通工程教育部重点实验室，上海 201804）

货运机车乘务交路是指货运机车乘务组（又称机班）担当值乘任务的周转区段，可表示为机车乘务组从乘务基地（一般为机务段所在站）至乘务换乘站 （一般为折返段所在站） 之间往返的线路区段。 货运机车乘务交路计划的编制不仅影响货运列车能否按计划行车， 还关系到乘务工作效率和运输经济效益。 目前我国货运机车乘务交路以机务段管理人员凭人工经验编制为主， 需要花费较长的时间，有时难以得到较优方案，甚至产生机车乘务超劳、 值乘任务不均衡、 乘务资源浪费等问题。 而且当铁路运输市场需求或线路条件发生变化时，列车运行图需要进行不定期调整，机车乘务计划也需要同步调整，人工编制方法难以适应。 利用计算机技术辅助编制货运机车乘务交路计划，对于提高乘务工作效率和降低铁路运输企业成本具有重要的现实意义。

国内外学者在航空运输[1-2]、铁路运输[3-9]、城市公交[10-11]等领域都开展了有关乘务计划的研究。 但因各种运输方式特点不同且各国运输组织制度存在差异， 乘务交路的编制流程和约束条件也有所不同， 难以直接用来解决我国铁路货运机车乘务交路问题。 国内有关铁路乘务交路计划问题的理论研究主要集中在客运专线上，王媛媛等[12]考虑了乘务继乘的情况， 将乘务交路编制问题看作特殊的旅行商问题（traveling salesman problem，TSP）问题，设计了改进蚁群算法进行求解；张哲铭等[13]基于单一循环乘务值乘计划提出了闭环排班和非闭环排班的概念， 研究了结合乘务休息规则的排班方案；符卓等[14]研究了带立即折返的高速动车组乘务交路优化问题。

现有研究在货运机车乘务交路方面，主要结合线路实际情况或机车交路对乘务机班存在问题进行定性分析[15-16]，缺乏对货运乘务交路计算机编制方法的量化研究。

因此，在借鉴铁路客运乘务交路编制方法的基础上， 考虑货运机车乘务的实际工作要求和特点，研究货运机车乘务交路计划的编制方法，构建货运机车乘务交路编制优化模型，并设计相应的求解算法，为铁路运营企业实现计算机辅助编制货运机车乘务交路提供理论依据。

1 乘务交路计划

乘务交路计划编制 （crew scheduling problem，CSP）是铁路运输组织的一个重要问题，受到列车运行图、沿线车站性质、机车交路和乘务规则等多因素影响[17-18]。目前我国货运机车乘务形式为非立即折返型，即机班从乘务基地出勤后，担当去程乘务片段的值乘任务到达换乘站， 按乘务作业时间标准间休后， 再担当返程乘务片段的值乘任务返回乘务基地。 具体的货运机车乘务交路计划编制步骤如下。

1） 数据收集。 获取货运列车运行信息、机车交路图，确定乘务基地、折返段及可换乘的车站，明确乘务基地的任务范围，梳理机车乘务员的工作时间和休息时间要求。

2） 划分值乘片段。 结合货运机车交路信息，选择合适的乘务制度和值乘模式，根据乘务一次连续工作时间标准，以可换乘的车站为分割点，将列车运行线划分为若干个值乘片段。

3） 组成乘务交路。根据乘务规则，考虑工作、休息时间标准约束和机务本段、 折返段的空间约束，一般按先到先走的原则，将值乘片段组合成乘务交路，作为货运机班一次乘务工作的内容。

4） 组成乘务交路循环。考虑到机车乘务员对所驾驶机车类型和线路的熟悉程度，原则上一个机班通常安排在固定的乘务交路循环中值乘；因此需要将区段内的乘务交路组成若干个乘务交路循环，由若干个机班依次循环执行。 货运乘务交路循环的接续主要考虑担当两相邻乘务交路之间乘务员在本段的休息时间标准，优化乘务交路循环顺序能有效缩短乘务的排班周期。

CSP 问题的最终目标是确定乘务交路循环，保证乘务交路集合完全覆盖全部值乘片段和列车运行线[19]。 根据乘务交路计划的编制步骤，在步骤1）、步骤2）确定的条件下，考虑乘务交路及其循环的组合方法，构建乘务交路编制优化模型。

2 优化模型构建

铁路货运机车乘务调度成本主要受机班数量决定，而值乘时间占总工作时间的比例是决定机班数量的重要因素。 也就是说在符合劳动时间标准的前提下，乘务值乘时间比例越高，说明乘务调度越充分，所需要的总机班数量也就越少。 为了降低乘务交路编制问题的复杂性，以乘务交路非值乘时间最少， 即值乘片段间的接续时间最少为模型目标。根据乘务交路计划的编制步骤，模型分为乘务交路问题和乘务交路循环问题，其中乘务交路问题的解为乘务交路循环问题的输入条件， 乘务交路问题主要求解机班一次乘务工作的内容， 乘务交路循环问题是确定机班执行各交路任务的值乘顺序。

2.1 乘务交路问题

对于若干个值乘片段i=1，2，…，n，构成乘务交路需要满足的条件为[20]

1） 第一个值乘片段的起始地点与最后一个值乘片段的结束地点为同一机务本段；

2） 相邻两值乘片段i，j， 前一值乘片段的结束地点sdi与后一值乘片段的起始地点soj相同；

3）相邻两值乘片段i，j，前一值乘片段的结束时间tdi小于后一值乘片段的起始时间toj，且接续时间满足乘务在外段休息时间标准。

通过构造值乘片段之间接续时间tij（单位：min）的n 阶矩阵来表示各个值乘片段之间的接续可能性。

式中：M 为一个足够大的正整数， 表示值乘片段i，j之间由于不满足地点接续性而不能组合成乘务交路。

根据乘务休息时间约束， 机车乘务员在本段的休息时间每次不应少于16 h，即960 min；在外段调休的时间不得小于5 h，即300 min；在外段驻班休息时间不得少于10 h，即600 min；轮乘制外段换班继乘休息时间不得少于6 h， 即360 min。需要根据值乘片段i 的结束地点和换班方式对tij进行调整。

式中：t′ij+1 440 表示值乘片段j 可与第2 天的值乘片段i 接续。

因此，tij≠M 时说明值乘片段j 与值乘片段i接续间有一定的休息时间， 有可能形成乘务交路。为了最小化乘务交路所需要的总机班数，保证乘务在外段停留时间越少越好， 即去程值乘片段i 与回程值乘片段j 的接续时间tij越小越好， 在编制乘务交路时遵循乘务先到先走原则，即先到达外段的去程值乘片段优先接续最早出发的回程值乘片段，形成最优乘务交路方案。

2.2 乘务交路循环问题

由于单循环排班方式有利于均衡乘务员之间的工作量以及提高机班对值乘机车类型和值乘区段的熟悉程度，在我国货运机车乘务领域可操作性强。 本文采用单循环的乘务排班方式，即将某乘务基地管辖范围内所有的乘务交路，在符合乘务规则的条件下组成一个有序的循环，乘务员按照乘务交路循环的顺序依次值乘。 对于同一乘务基地而言，任意2 个乘务交路p，q 的起始和结束地点相同，满足空间接续性。

通过构建有向图以更好地描述乘务交路循环问题，如图1 所示。 设G=（V，E）为有向图，V 表示有向图的顶点集合，E 表示有向图的弧集合，Vp（p=1，2，…，n）表示第p 条乘务交路，弧（p，q）∈E 表示乘务交路p 与乘务交路q 接续关系， 弧上的权值tpq（单位：min） 表示乘务交路p 与乘务交路q 之间的接续时间。 可构建接续时间矩阵Tpq，表示乘务交路p 与乘务交路间q 的接续时间，为非对称矩阵。

图1 乘务交路循环有向图Fig.1 Directed graph of crew routing cycle

对于单循环的乘务排班方式，寻求乘务交路循环最优方案的实质，是找到各个乘务交路之间的接续次序，同时保证总接续时间最短，可视为寻找该有向图内经过所有顶点的最短路径。 乘务交路循环问题可转化为非对称旅行商问题[21]。

对于若干乘务交路p=1，2，…，n（p∈V），不同交路之间的接续时间为tpq，定义决策变量xpq

3 求解算法设计

3.1 基于先到先走的遍历搜索算法设计

当一个乘务交路去程的值乘片段i 与之可接续的回程值乘片段不止一个时，为了最小化所需要的总机班数，需要保证乘务在外段停留时间越少越好， 即去程值乘片段i 与回程值乘片段j 的接续时间tij越小越好。 在满足机车乘务员外段休息的时间标准下，基于先到先走原则，即先到达外段的去程值乘片段优先接续最早出发的回程值乘片段，设计求解乘务交路问题的遍历搜索算法，如图2 所示。

图2 基于先到先走原则的遍历搜索算法流程图Fig.2 Flowchart of the traversal searching algorithm based on “first come first serve” principle

步骤1 输入值乘片段、接续时间矩阵Tij和机务段所在站；

步骤2 将出发地点为本段的值乘片段按退勤时间由早到晚排序，并组成集合S；

步骤3 取集合S 中的第一个值乘片段进行判断；

步骤4 若片段x 的接续时间全为0，则按顺序取下一片段重新判断；若不是所有接续时间为0， 则找出值乘片段x 接续时间最小对应的值乘片段j，并将值乘片段x，j 加入待选集合Un中；

步骤5 判断片段j 的到达地点是否为本段，若是， 则集合Un中的值乘片段按顺序组为一个乘务交路；若否，则返回步骤4 继续寻找片段j 接续时间最小的片段；

步骤6 直至集合S 中所有的片段都被遍历，则生产乘务交路集合V。

3.2 遗传算法设计

与旅行商问题相似， 乘务交路循环问题是NP难的组合优化问题，当交路数目不是很多时，可采用精确算法求解；对于乘务交路数目较多、问题规模较大、方案编制较为复杂的情况，选择启发式算法有利于提高计算效率、减少计算时间，得到较优的全局解[22]。 本文设计了遗传算法对乘务交路循环问题进行求解，算法流程如下。

1） 编码个体。一个乘务交路循环可直接以交路的次序来表示，例如包含6 个乘务交路的循环可表示为[3，4，1，2，5，6]，即循环从交路3 开始依次经历交路4，1，2，5，6，然后重新值乘交路3，满足所有交路均遍历一次且仅一次。

2） 生成初始种群。随机产生一组包含n 个个体的初始种群，每个个体代表一个可行解。

3） 计算适应度。乘务交路循环问题为最小化问题，可以取目标函数的倒数为适应度函数，符合适应度越高、选择概率越大的要求。 考虑到最优解可能有多个，为了使乘务交路的接续时间分布尽量均衡， 适应度函数同时考虑了接续时间方差的大小，具体如下

式中：F 为适应度函数；Z 为2.2 节中乘务交路循环问题的目标函数；V（tpq）为该乘务交路循环的接续时间方差；C1，C2为参数，根据Z 和V（tpq）的数量级来确定。

4） 选择。 采用轮盘赌选择法对种群进行选择。取适应度的指数倍为计算依据，以扩大个体间的优劣差距。

5） 交叉。 根据交叉概率Uc对个体交叉进行部分匹配交叉操作，保证形成的子代基因无冲突。

6） 变异。 根据变异概率Uv在变异个体中随机产生2 个变异点，进行逆转变异操作。

7） 取代。 经过选择、交叉、变异后，产生的子代种群代替换原有父代种群，利用子代继续重复步骤3）至步骤6），直至迭代次数N 大于500 或连续50代的适应度未改变，则停止迭代，最终得到的种群中适应度最好的个体为该问题的最优解。

4 算例分析

选取某铁路机务段为研究对象，该机务段管辖范围如图3 所示，包括6 个技术站，其中车站C 为货运车间Ⅰ所在站，E 为货运车间Ⅱ所在站，均为乘务基地。

图3 某机务段的管辖范围Fig.3 Jurisdiction of the locomotive depot

货运车间Ⅰ负责A～E 的直达、直通和区段货物列车牵引任务， 以C 站为支点实行半循环制式，上行列车机车乘务在C 站直通不换班，下行列车乘务在C 站换班。 货运车间Ⅱ负责E～F 的直达、直通和区段货物列车牵引任务，以E 站为支点，实行肩回制。 下面以货运车间Ⅱ的乘务计划为例具体说明。

1） 数据收集。根据《铁路机车运用管理规则》规定，货运机车乘务每月应安排1～2 次不少于48～72 h的大休时间； 在E 站的换班休息时间每次不少于16 h，即960 min；在F 站的换班休息时间每次不少于6 h，即360 min；月度大休时间最小值为48 h，即2 880 min。

2） 划分值乘片段。 由于E～F 区段的最长运行时间不超过乘务最长工作时间标准， 可将该区段内每列车视为一个值乘片段。 假定出勤时间比列车出发时间提前70 min， 退勤比列车到达时间晚30 min，出退勤时间主要用于完成乘务报到、列车运行预告、接受派班、领取和归还值乘物件、准备机车出库、交接班等作业。 该区段的货物列车信息和值乘片段信息见表1。

3） 求解乘务交路方案。 根据2.1 节值乘片段接续时间的定义，计算表1 值乘片段的接续时间矩阵Tij，见表2。

表1 货运车间Ⅱ的列车信息和值乘片段信息Tab.1 Trains and crew duties of the railway freight workshop Ⅱ

表2 货运车间Ⅱ的值乘片段间接续时间矩阵Tab.2 Connection time matrix of crew duty fragments of the railway freight workshop Ⅱmin

利用3.1 节基于先到先走的遍历搜索算法，得到表3 中编号1～16 的交路方案。 由于货物列车并非成对开行， 在求解时会存在一些值乘片段没有回程片段接续的情况，无法形成完整的乘务交路。在实际工作中有两种处理办法：一是便乘，即对乘务员进行异地调度， 使其在不担任值乘任务的情况下， 从上一结束车站乘车至下一任务的起始车站，一般会产生额外支出；二是调整值乘范围，即安排这些乘务员继乘其它区段的货物列车牵引任务，但这对乘务员的业务能力要求较高，他们需要熟悉不同区段的线路情况甚至需要操纵不同类型的机车。

货运车间Ⅱ还有4 个无法成对的值乘片段，根据便乘规则， 按基于先到先走原则的遍历搜索算法，得到表3 中编号17～20 的交路方案。

4） 求解乘务交路循环方案。 根据2.2 节乘务交路接续时间的定义， 计算表3 中20 个乘务交路的接续时间矩阵Tpq，见表4。

表3 货运车间Ⅱ的乘务交路集合Tab.3 Set of crew routing of the railway freight workshop Ⅱ

表4 货运车间Ⅱ的乘务交路接续时间矩阵Tab.4 Connection time matrix of crew routing of the railway freight workshop Ⅱ min

在利用3.2 节遗传算法求解乘务交路循环方案时，规定遗传种群内个体个数n=50，适应度函数参数C1=106，C2=0.01， 并取适应度的10 次幂来计算累积概率， 以放大不同个体间的适应度值差距。 设交叉概率Uc=0.7， 变异概率Uv=0.005。遗传算法适应度变化曲线如图4 所示，当迭代次数N=364 时开始收敛。 乘务交路循环本段接续时间总和变化曲线如图5 所示， 迭代至42 代开始本段接续时间总和TW趋于稳定。 得到最 优 乘 务 交 路 循 环 方 案 为：1 →20 →17 →14 →10→11→13→15→9→6→5→4→18→12→8 →2→16→7→3→19。

图4 遗传算法适应度变化曲线Fig.4 Fitness variation of genetic algorithm

图5 乘务交路循环本段接续时间总和变化曲线Fig.5 Total connecting time variation at locomotive depot of the crew routing cycle

该循环中， 乘务值乘时间TZ为15 065 min，外段休息时间TB为11 407 min， 本段休息时间TW为25 213 min，乘务交路循环总时间T 为51 685 min。

根据劳动强度要求和月大休时间标准，可计算乘务交路循环方案的月循环次数和机班配备数。

式中：P 为机班配备数；β 为乘务交路循环每个月可循环的次数；取β1，β2中的较小值；C 为月平均工作时间最大值，根据《中华人民共和国劳动法》取176 h，即10 560 min；TM为剔除一次48 h 大休时间后的月时间换算值，一个月按30 d 计算，取40 320 min。计算得到，β＝β1＝0.701，完成该乘务交路循环所需要配备的机班43 个。

同样的计算方法可得到货运车间Ⅰ的乘务编制计划，结果见表5，完成该乘务交路循环方案共需要配备124 个机班。

表5 货运车间Ⅰ的乘务交路循环方案Tab.5 Result of crew routing cycle of the freight workshop Ⅰ

5） 结果分析。 通过分析上述算例的结果，得出以下结论。

①该模型能有效节省货运机车乘务资源。利用优化模型所计算得到的货运机班数量相比原有人工经验方案的要少，2 个车间分别有效节省了22.5%和17.6%的乘务资源，具体见表6。

表6 乘务交路编制结果对比Tab.6 Results contrast of crew scheduling

②该算法能有效提高乘务交路编制效率。上述算例利用本文所设计的基于先到先走遍历搜素算法和遗传算法，平均用时3.35 s 能求得该优化模型的乘务交路计划编制方案，且收敛性较好，相比目前我国铁路机务段现场工作的人工经验编制方法，编制效率和质量大大提升。

③单一交路循环能均衡乘务工作量并减少机班配备数。 本模型所采用的单一乘务交路循环方法，相比各乘务交路独立循环或若干乘务交路成组循环的方法，能保证同一货运车间的机车乘务员同属一个循环组，组内值乘时长、休息时间、月大休时间相同，对于均衡各机车乘务员的工作量和收入水平具有实际意义。 同时，单一乘务交路循环方法能尽可能地减少乘务交路的接续时间，整体上减少总循环时长，可相应地减少乘务组的配备数。

5 结论

1） 提出了以乘务员非值乘时间最少为优化目标的乘务交路计划编制优化模型，符合铁路货运机车乘务交路计划编制问题的原理和流程，考虑了机班工时符合劳动管理规定、乘务交路的时间和空间约束，满足乘务交路覆盖所有车次。

2） 根据模型特点分别设计了基于先到先走原则遍历搜索算法和遗传算法，确定求解思路和具体步骤，能有效提高货运部门乘务交路编制的效率。

3） 以某铁路货运机务段为算例，验证了本文提出的模型和算法可以完整求解铁路货运乘务交路计划方案，并且与人工经验方法相比，有效减少了货运机班的配备数，具有一定的实际意义。