基于改进蚁群算法的铁路乘务交路计划的编制

王东先 孟学雷 乔俊 汤霖 焦志臻

摘 要：针对提高铁路乘务交路计划编制质量和效率的问题，将乘务交路计划编制问题抽象为单基地、均衡行驶路程的多旅行商问题（MTSP），引入均衡因子，建立了以乘务交路用时少和子乘务交路间任务均衡为目标的数学模型。针对该模型提出了一种双重策略蚁群优化算法，该算法首先构建满足时空约束的解空间，分别对乘务区段节点和接续路径设置信息素浓度，然后采用双重策略状态的转移概率，使蚂蚁遍历所有乘务区段，最终找到符合乘务约束规则的子乘务交路。最后运用广深线城际铁路数据对设计的模型及算法进行检验，经与遗传算法的实验结果对比分析表明：在相同的模型条件下，运用双重策略蚁群优化算法编制的乘务交路计划乘务交路个数减少了约21.74%、乘务交路总时长降低了约5.76%、交路超劳率为0。运用所设计的模型和算法编制乘务交路计划能够减少乘务计划交路时长，均衡工作量，避免产生超劳交路。

关键词：铁路;乘务交路计划;均衡因子;多旅行商问题;双重策略蚁群算法

中图分类号：TP301.6

文献标志码：A

Railway crew routing plan based on improved ant colony algorithm

WANG Dongxian1， MENG Xuelei1*， QIAO Jun1， TANG Lin1， JIAO Zhizhen2

1.School of Traffic and Transportation， Lanzhou Jiaotong Unirersity， Lanzhou Gansu 730070， China;

2.China Railway Lanzhou Group Company Limited， Wuwei South Station， Wuwei Gansu 733000， China

Abstract：

In order to improve the quality and efficiency of railway crew routing plan， the problem of crew routing plan was abstracted as a Multi-Traveling Salesman Problem （MTSP） with single base and balanced travel distance， and a equilibrium factor was introduced to establish a mathematical model aiming at less crew routing time and balanced tasks between sub-crew routings. A dual-strategy ant colony optimization algorithm was proposed for this model. Firstly， a solution space satisfying the space-time constraints was constructed and pheromone concentration was set for the node of the crew section and the continuation path respectively， then the transitional probability of the dual-strategy state was adopted to make the ant traverse all of the crew segments， and finally the sub-crew routings that meet the crew constraint rules were found. The designed model and algorithm were tested by the data of the intercity railway from Guangzhou to Shenzhen. The comparison with the experimental results of genetic algorithm shows that under the same model conditions， the number of crew routing in the crew routing plan generated by double-strategy ant colony optimization algorithm is reduced by about 21.74%， the total length of crew routing is decreased by about 5.76%， and the routing overload rate is 0. Using the designed model and algorithm to generate the crew routing plan can reduce the crew routing time of crew plan， balance the workload and avoid overload routing.

Key words：

railway; crew routing plan; equilibrium factor; Multi-Traveling Salesman Problem （MTSP）; dual-strategy Ant Colony Algorithm （ACA）

0 引言

鐵路乘务计划是依据列车运行图、机车交路（动车组交路）、相关乘务规则、车站设备条件等限制因素编制的，对乘务人员（司乘）出、退乘时间和地点及担当车次等做出的详细安排，保证了列车运行计划的顺利实施。其中，列车运行图包含了待完成的乘务任务，机车交路（动车组交路）规定了机车（动车组）担当运输任务的固定周转区段，乘务规则限定了乘务人员的工作时间，车站设备条件限制了车站是否是乘务基地及具备司乘人员换乘或休息的条件。

因为在编制乘务计划过程中需要同时考虑到乘务交路计划和乘务排班计划相关的大量约束，导致乘务计划的编制有难度大、效率低的特点。所以，为了合理优化乘务计划编制，有效提高编制效率，乘务计划往往被分为乘务交路计划和乘务排班计划。乘务交路计划是乘务排班计划的基础，乘务排班计划编制的优劣取决于乘务交路计划。本文针对乘务交路计划编制，做出进一步的讨论。针对乘务交路计划编制问题，文献[1]建立了0-1整数规划和动态规划模型，利用拉格朗日方法求得问题的下界，设计了树搜索算法求得最优解。文献[2]利用改进的遗传算法结合Dijkstra法分阶段编制了香港轻轨乘务计划，但是该模型对于求解“点多线长”的铁路乘务计划有一定局限性。文献[3]采用列生成技术求解了动车组乘务交路计划。文献[4]运用了禁忌搜索和图着色理论编制了乘务计划。文献[5]重点研究了工作效率对于乘务计划编制的影响，并用蚁群算法进行了求解，但是没有考虑乘务交路的均衡性。文献[6]利用SE（Simulated Evolution）方法编制了京沪高铁的乘务计划。文献[7]借鉴文献[6]的SE方法求解了乘务排班计划，但是没有考虑乘务交路计划。文献[8]首次在国内将列生成技术应用到了乘务交路计划的编制，并把乘务排班计划问题抽象成了旅行商问题，但是该算法在求解初始可行解时效率较低。文献[9]结合了列生成技术和分支定界法，进而提出了求解乘务交路计划的分支定价算法。文献[10]将客运专线的乘务交路计划转化为特殊的旅行商问题，并提出了K条径路的最大最小蚂蚁系统（K-Max-Min Ant System， K-MMAS）算法，但是该模型没有考虑到乘务人员的任务均衡性。文献[11]将乘务计划编制问题拆分为最优回路构造、回路循环优化和排班三个子问题，并设计了遗传算法进行求解，但是编制步骤过多，不利于铁路乘务交路计划的快速编制。文献[12]将乘务交路计划的编制问题分解为值乘区段集合的覆盖和乘务交路段的匹配两个子问题，并设计了改进的蚁群算法进行求解，但是该模型没有考虑乘务计划与乘务交路计划的协同优化。文献[13]根据现场调研统计的结果，建立了基于乘务人员偏好性的乘务交路计划，但是对于复杂的交路，没有给出具体的评价值标定方法。文献[14]通过采用最近邻域搜索算法和模拟退火算法求解了乘务交路计划的数学规划模型，但是该模型没有考虑到乘务交路的均衡性，不适用于城际铁路乘务计划的编制。文献[15]建立了基于遗传算法的乘务计划编制的求解方法，同时对系统的人机交互调整功能进行了设计。文献[16]提出了基于时空接续网络和网络流模型的求解策略来编制高速铁路乘务计划，并利用了拉格朗日松弛算法进行求解，但是该算法的迭代步长由经验公式自行设定，缺乏论证。回顾前人研究成果可以看出，国内大多数学者的研究重点集中于高速铁路宏观层面的乘务计划，但是，对于乘务交路计划研究较少。本文在总结已有的研究成果基础上，结合铁路乘务规则及其特点，将乘务交路问题抽象为多旅行商问题（Multi-Traveling Salesman Problem， MTSP），最后针对本文研究问题设计基于双重策略的蚁群算法求解该模型。

1 乘务交路计划数学模型的建立

铁路乘务交路计划编制是机车乘务计划的核心问题。乘务交路计划编制过程中需综合考虑铁路乘务调度规则及资源约束条件，在列车运行图的基础上，将所有值乘区段组合成若干个可行乘务交路，以劳动强度均衡为原则分配乘务任务，建立乘务时长最短，乘务人员“用户体验”最佳的乘务调度计划。

1.1 问题描述

最优乘务交路计划的一项重要指标是使用最少的乘务人员（组）完成上级下达的运行图任务。编制铁路机车乘务交路计划的主要步骤如下。

1）收集列车运行信息。根据列车运行图和机车交路（动车组交路），获取列车车次、发站、到站及动车组在乘务基地所在站和换乘站的停留作业时间。

2）选定换乘车站。乘务人员换乘车站的选取与车站的设备条件密切相关，选取的车站必须是具备换乘条件的。根据运行图数据，以单条运行线为研究对象，把运行线上的所有车站分为3类：具备换乘条件的乘务基地所在车站、具备换乘条件的非乘务基地所在车站、不具备换乘条件的非乘务基地所在车站。

3）划分乘务区段。根据列车运行信息，在轮乘制的值乘模式下，按照乘务人员一次连续工作时长标准，以可换乘车站为节点，把运行线逐条划分为若干满足乘务规则的乘务区段。

4）建立可行的乘务大区段。一个乘务大区段由两个或两个以上的乘务区段严格按照乘务规则（时空接续规则）组合而成。乘务人员（组）完成一个乘务大区段值乘任务的过程是指乘务人员从乘务基地开始值乘，到达换乘公寓所在站，休息一定时间后值乘另一任务最终返回乘务基地的过程。

5）把若干可行乘务大区段按照乘务接续规则组合成覆盖整个区段的乘务交路。

1.2 乘务交路计划时空规则

1）时间接续乘务规则。相邻的两乘务区段必须要满足时间接续性，即前一个乘务区段的到站时刻必须严格早于后一个乘务区段的发车时刻。如果某一个乘务区段结束后乘务人员正好要换乘（或驻班休息），那么乘务人员在该站的换乘时间必须严格大于这两个相邻乘务区段的接续时间。

2）空间接续乘务规则。相邻的两乘务区段必须要满足空间接续性，即前一个乘务区段的到站必须是后一个乘务区段的发站，保证乘务交路集合必须覆盖所有的乘务区段。因为铁路运行线相比其他交通运行线路较长，经常是跨城市甚至是跨省份的，所以乘务交路必须考虑乘务人员的归属地因素，保证最终生成的乘务交路的发站和到站是同一车站。

1.3 乘务交路数学模型

若把乘务区段当作MTSP中的城市，两相邻乘务区段之间的接续就可以看作是城市与城市之间的距离，由于每个子乘务交路都需一个乘务组值乘，故子乘务交路的个数就是所需乘务人员（组）的个数，即旅行商数目。设有N个子乘务交路，则N个子乘务交路从列车运行图过表时刻（默认列车运行图过表时刻为18：00）开始，各子乘务交路有且仅有一个乘务组访问，最后回到过表时刻，形成封閉回路。结合列车运营特点，乘务交路计划编制问题可以抽象为单基地、均衡行驶路程的MTSP。

将所有乘务区段抽象为点集V，所有的乘务区段之间的接续关系抽为成边A，简化后的乘务交路区段可视为有向图G，即建立具有U个节点的乘务交路区段有向图G=（V，A）。其中Vi（Vi∈J）是节点集合V中的节点，本文将节点类型分为3类：乘务区段点集合、乘务基地所在站（起点）集合、乘务基地所在站（终点）集合。其中乘务区段点集合含有以下六点属性：tfi、tdi、sfi、sdi、tti、r 。

弧aij（A={aij/aij=（vi，vj）;vi，vj∈V}）（i、 j=1，2，…，U）表示集合A中的一条连接弧，根据相关乘务规则，本文将弧集合A分为4种类型：接续弧集合、外段（折返段）驻班弧集合、出乘弧集合、退乘弧集合。四种不同类型的弧集合都含有以下两点属性：ttij、σij。模型中的符号定义如表1所示。

定义1 S={si/si=0，si=1，si=2}（i=1，2，…，U）为列车运行图中的车站集合，令Wsi为第i个车站的属性，则Wsi=0表示不具备换乘条件的非乘务基地所在车站，Wsi=1表示具备换乘条件的非乘务基地所在车站，Wsi=2表示具备换乘条件的乘务基地所在站。

定义2 H={Hk/k=1，2，…，N}，令Hk为所有子乘务交路的集合，通常tfi不大于可调度的乘务组总数。

考虑子乘务交路间工作量均衡的乘务交路计划编制问题目标函数包含两部分：1）乘务交路总时长最少;2）使子乘务交路之间的乘务时间相差最小。通过引入均衡因子将两部分目标统一为：

Z=min{∑Nk=1Zk+δ/ε}; ε∈Z*（1）

Zk=∑Ui=1∑Uj=1[ttij+（tti+ttj）/2]xijk（2）

δ=∑Nk=1∑Ui=1∑Uj=1tdkj-（tdkj-tokj）·xijk+tti+ttjN-12N-1（3）

s.t. Sdi=Sfj; i， j=1，2，…，U（4）

∑h∈Hk ∑i， j∈Aij，φi=φlxijk≥1; l∈L， i，  j=1，2，…，U（5）

∑（i， j）∈Aijxijk=∑（j，i）∈Ajixjik; i∈Vli，i∈Vlj，i， j=1，2，…，U（6）

WSfhk=WSdhk≠0且Sfhk=Sdhk; k=1，2，…，U（7）

∑h∈Hk，（i， j）∈Aoijxijk=1; i∈Vli，j∈Vlj，i， j=1，2，…，U（8）

∑h∈Hk，（i， j）∈Adijxijk=1; i∈Vli，j∈Vlj，i， j=1，2，…，U（9）

tdkj≤tdki+（1-xijk）M+tto+ttj ;

（i， j）∈Aoij， i∈Voi， j∈Vli，l∈L， i， j=1，2，…，U（10）

tdkj≤tdki+（1-xijk）M+ttij+ttj;

（i， j）∈Acij，i， j∈Vli，l∈L，i， j=1，2，…，U（11）

tdkj≤tdki+（1-xijk）M+ttd;

（i， j）∈Adij， i∈Vli， j∈Vdi， l∈L， i， j=1，2，…，U（12）

tdkj≤tdo+（1-xijk）M+ttj;

（i， j）∈Asij， l∈L， i， j=1，2，…，U（13）

tdki≥Tcmin-（1-xijk）M-ttd;

（i， j）∈Asij∪Adij， l∈L， i， j=1，2，…，U（14）

tdki≤Tcmax， i∈Vli， l∈L， i=1，2，…，U（15）

tokj≤toki+（1-xijk）M+ttj（16）

∪Nk=1Hk=H（17）

式（1）中：Zk為乘务交路时长，具体表达式为式（2）;δ为子乘务交路间乘务任务分配均衡性，具体表达式为式（3）。目标函数式（1）旨在寻求可以使得乘务交路计划总时长最小的同时尽量达到每条子乘务交路任务均衡的效果。其中ε为均衡因子，ε取较大的值时，表明总目标受交路总时长的影响较大，此时每条乘务交路时长差异较大，均衡交路任务的效果不理想。在正常情况下，可以根据乘务基地在不同情境下的历史乘务数据，得到相应数值。在应急条件下，ε可根据实际需求设定为无穷大值，这种情况下乘务交路间的均衡性不再成为重要约束因素，以此来保证救援乘务组能够快速机动地到达事故地点。均衡因子与目标函数的关系图如图4所示。式（4）为互异乘务区段接续空间约束，即为紧前乘务区段的到站与紧后乘务区段的发站必须是同一车站;式（5）表示所有划分的乘务区段至少被覆盖一次，若某些乘务区段超过一次，则认为该乘务区段为乘务人员“便乘”;式（6）为节点处流平衡约束：表示对于每个乘务区段节点而言，仅有一条边进，一条边出;式（7）描述交路闭合性约束，即乘务大区段的发站（到站）与到站（发站）必须是同一车站，且车站必须是乘务基地所在站（或乘务公寓所在站）;式（8）表示所有乘务大区段的起始弧必须是出乘弧;式（9）表示所有乘务大区段的终止弧必须是退乘弧;式（10）表示乘务大区段中的机车乘务人员出乘时长需满足乘务规则约束;式（11）表示乘务大区段中乘务区段之间接续时长需满足乘务规则约束;式（12）表示乘务大区段中的乘务人员退乘时长参数需满足乘务规则;式（13）描述了乘务人员在乘务公寓驻班或调休后，乘务大区段累计时长需满足乘务规则约束;式（14）、式（15）分别为乘务人员退乘或在乘务公寓驻班时，乘务大区段累计时长需满足乘务规则;式（16）为乘务人员连续值乘累计时长需满足的乘务规则;式（17）表示子乘务交路的集合需组成一个完整的乘务交路计划。

2 双重策略蚁群算法

显然MTSP为NP-Hard问题，常用的解决方法包括分支定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，造成了组合爆炸的情况，精确算法难以求解，启发式算法会体现出它特有的优势。对于基本蚁群算法，一次循环某一路径走过的蚂蚁越多，累积的信息素就越多，而未被走过路径的信息素将减少，根据与信息素有关的转移概率计算出下一步任意可供选择转移位置的转移概率后，采用比例方式（轮盘赌）方式确定。由于信息素的差别过大，且具有挥发性，可能导致某些路径被选择的比例过大，陷入局部最优解。同时初始路径上信息素的水平一致，算法初期人工蚂蚁的运动轨迹具有较强的随机性，虽然通过启发性信息能够向较优路径进化，但当求解问题规模较大时，不容易在短时间内从大量路径中找出较优路径，为了提高搜索效率，增加蚂蚁搜索路径的多样性，本文提出了双重信息素、双重策略的改进蚁群算法，对基于MTSP的乘务交路问题进行求解。算法构建步骤如下。

1）生成解构建图。

将经切割运行线后得到的乘务区段，按相应的乘务规则组合成若干乘务大区段，令所有乘务大区段遍历所有乘务区段。根据抽象的乘务交路MTSP，解构建图由所有表示乘务区段的节点和若干虚拟“原点”组成，其中“原点”是乘务大区段的起点和终点，若干“原点”实质上是一个点经过不断复制得到的具有相同特性的离散点。

2）构建解空间。

让所有蚂蚁从某“原点”出发，每个蚂蚁按照某一概率选择乘务大区段的初始节点，设定初始节点的始发车站为φc，φc=0表示始发车站是乘务基地所在车站;否则φc=1。蚂蚁按照某一概率选择待接续的节点，如果累计时长尚未达到乘务大区段的乘务时长标准，则继续选择待接续的节点，直到接续一系列的节点后返回该“原点”形成一个回路，即乘务大区段。设定乘务大区段的到站为φd，φd=0表示到站是乘务基地所在车站，否则φd=1。若乘务大区段满足φc·φd=0 ，则表示得到了一个满足时空约束的乘务大区段，否则蚂蚁继续搜索，直至使得乘务大区段满足φc·φd=0。蚂蚁重复该过程构建解空间，当所有节点都被乘务大区段遍历时，算法完成了解构建。

3）初始化及更新双重信息素。

由于在解构建图中节点和路径具有同等的重要性，故本文对节点和路径都定义了信息素浓度。设定全部路径上的信息素浓度为τij，全部节点上的信息素浓度为τi。τij表示蚂蚁处在节点i时，接续节点j的重要程度。τi表示蚂蚁处在“原点”时，选择节点i作为下一个乘务大区段起始节点的重要程度。其中，路径和节点的信息素初始浓度设定如下：

τij（0）=1A2-A， i≠j

0，其他（18）

τi（0）=1/A（19）

式（18）、式（19）中A表示互异乘务区段节点之间的接续频数。

信息素浓度与各乘务节点和路径是否参与了最优解的构建成正相关。在最优蚂蚁每次迭代后，各路径和节点上信息素的更新取值设定如下：

τij（n+1）=ρτij（n）+Δτij（20）

τi（n+1）=ρτi（n）+Δτi（21）

Δτij=1/Zibest， eij∈sibest

0，其他 （22）

Δτi=1/Zibest， starti=1

0，其他（23）

式（20）、式（21）中ρ为信息素挥发因子（0<ρ<1），n代表迭代次数;式（22）、式（23）中Δτij、Δτi 分别为每次迭代过程中的信息素增量。starti为0-1变量，当乘务区段的节点i在最优解中出现作为某个乘务大区段的起点时1，否则取0。

蚂蚁从“原点”出发，以τi的期望搜索到乘务区段节点i （即乘务大区段的起始节点），此时蚂蚁以τij的期望继续搜索到下一个乘务区段节点j，以此类推，根据某一概率选择下一个乘务区段的节点，若其累计时长尚未达到乘务大区段的乘务时长标准，则继续选择下一个节点，直到接续一系列的乘务区段后返回该“原点”，形成一个回路，即乘务大区段。根据初始信息素浓度的设定（式（18）、式（19）），显然τi（0）>τij（0）。通过设置双重信息素全局更新策略，在每次迭代结束后，只允许全局最优解释放信息素。在最优路径上，蚂蚁才释放信息素，同时信息素才会挥发，这点非常重要，因为在信息素更新时的时间复杂度从O（n2）降到了O（n），所以蚂蚁可以在短时间内从大量路径中找出较优路径，提高蚂蚁的搜索效率。

4）基于双重策略状态的转移概率。

①当第k只蚂蚁所在的乘务区段节点i不是原点时，由节点i向下一个乘务区段节点j转移的概率为：

Pkij=[τij]α·[ηij]β∑l∈Vli[τil]α·[ηil]β， j∈Vli

0，其他（24）

其中：ηij为预见度，表示从乘务区段节点i转移到乘务区段节点j的预见程度。Vli表示蚂蚁待访问的节点集合，随着迭代次数的增加，Vli中的元素不断减少，直至为空，即表示所有乘务区段节点全部遍历完毕。α表示残留信息素的相对重要程度，其值越大，信息素的浓度在转移中起的作用越大。 β为预見值的相对重要程度，其值越大，蚂蚁以越大的概率转移到接续时间较短的下一个乘务区段节点。其中预见度：

ηij=1ttij+（1-Eij）t1-Eijt2（25）

其中：ttij表示两相邻乘务区段接续弧的长度。Eij为0-1变量，Eij=1表示相接续的两乘务区段同属同一动车组交路，否则为0。t1为乘务人员换乘时间标准，t2为乘务人员在同车底上担当不同乘务区段的最小间隔时间。预见度越大，蚂蚁所能搜寻到最邻近的节点的概率越大，也就是说，两相邻乘务区段之间的接续时长越短，两乘务区段接续的概率越大。

②当第k只蚂蚁位于原点时，选择节点i作为下一个乘务大区段起点的概率为：

Pki=[τi]α·[ηi]β∑i∈Dl[τl]α·[ηl]β， Dl≠1

0，其他 （26）

其中：Dl为0-1变量，Dl=1时，表示乘务区段i被蚂蚁选择;否则，Dl=0。其中ηi为预见度，可由式（27）计算获得：

ηi=tsurplus-teitsurplus-tdurationi+ρNnoN+1（27）

其中：tei表示乘务区段i的值乘结束时刻;tsurpius表示除乘务区段i外，其余乘务区段集合中最早结束值乘的乘务区段的结束时刻;tdurationi表示乘务区段i的值乘时长; ρ为可控参数，表示蚂蚁能够选择到最快结束乘务区段的期望值;Nno表示在当前阶段，尚未被选入任何乘务大区段的乘务区段的数量，N表示乘务区段的数量。式（27）表明，随着迭代次数的增加，在没有被选择的乘务区段集合中，能够较早结束的乘务区段越容易被选为乘务大区段的起点。

设置双重策略状态的转移概率主要目的在于提高算法的全局搜索能力，防止其收敛于局部最优解，避免算法停滞或过早收敛。算法针对路径选择策略进行了改进，蚂蚁从“原点”或“非原点”出发，根据相邻乘务区段节点间的接续时间和接续状态动态地调整启发函数。当蚂蚁所在的乘务区段节点i不是原点时，蚂蚁以转移概率Pkij（式（24））接续下一个乘务区段节点j，乘务区段节点距离目标节点越近则接续预见度ηij就越大。当蚂蚁所在的乘务区段节点i不是原点时，蚂蚁以转移概率Pki（式（26））接续下一个乘务区段节点i，能够较早结束的乘务区段越容易被选为乘务大区段的起点，即接续预见度ηi越大。这样， 使算法在降低问题复杂性的同时，减少了算法搜索的盲目性，有效引导算法朝全局最优方向进行搜索;同时增加了蚂蚁搜索路径的多样性，又使得更新的路径具有随机性，能够有效避免算法过早地陷入局部最优，而进入停滞状态。

5）终止策略。

蚂蚁经过若干次搜索后，找到的解不再改变，且所有乘务区段都已经被乘务交路所遍历时，算法终止。本文算法具体实现流程如下所示：

步骤1 令nc ← 0，k ← 1，初始化α、 β、 ρ、蚂蚁数量、最大迭代次数等参数。

步骤2 将m只蚂蚁随机地放置在原点，构建一个n维向量Crew-section，n维向量Crew-section中的元素代表了所有的乘务区段，所有元素都为0-1变量。当某一元素为0时，表示该元素对应的乘务区段未被乘务大区段遍历，否则为1。初始化向量Crew-section，令所有元素初态为0。

步骤3 蚂蚁k以概率Pkj选择下一个乘务大区段的起点，同时更新向量Crew-section，把被乘务交路遍历过的乘务区段所对应元素取值为1。判断向量Crew-section中的所有元素是否为1。若是，则令k ← k+1，若k>m则跳转至步骤6;否则重复步骤3。对于蚂蚁k，若Crew-section向量中仍有0元素，则进行下步。

步骤4 蚂蚁k以概率Pkj為节点i向下一个乘务区段节点j转移。同时更新向量Crew-section，把被乘务交路遍历过的乘务区段所对应的元素取值为1。判断Crew-section向量中的所有元素是否为1，若是，则令k ← k+1，若k>m则跳转至步骤6，否则重复步骤3。对于蚂蚁k，若Crew-section向量中仍有0元素，则进行下一步。

步骤5 若接续乘务区段的累计工作时长已达到乘务大区段的工作时间标准，则完成一个乘务大区段的构建，返回原点，跳转至步骤3;若累计工作时间标准还没有达到乘务大区段的时间标准，而连续工作时长已达上限，则调整乘务区段之间的接续时间标准，给乘务人员（组）增加调休时间，并返回步骤4;否则直接返回步骤4。

步骤6 当向量Crew-section中的所有元素返回值为1时，m个蚂蚁已经生成了可行的乘务大区段回路。计算生成的乘务大区段的数量，并确定此次迭代产生最优解的蚂蚁。

步骤7 根据式（20）和式（21）更新解构建图中所有路径和乘务区段节点上的信息素浓度。

步骤8 令nc ← nc+1，如果nc小于步骤1中指定的最大迭代次数，更新向量Crew-section，转至步骤2;否则，终止计算，输出当前最优解。

3 实例验证及分析

3.1 实验数据

为了验证本文理论研究和算法的有效性，选取广深线上城际列车数据进行验证。广深线起点广州站，终点深圳站，全长147km，途经广州、广州东、东莞、常平、樟木头、平湖、深圳7个车站，并办理客运营业业务，周内每日开行73趟列车，周末每日开行95趟列车。动车组的检修基地设置在广州东站接轨的石牌动车检修所。乘务基地设置在广州东站，深圳站设乘务人员公寓，供在深圳驻班或调休的乘务班组休息。线路示意图如图1所示。

广深线乘务运用情况说明：机务乘务组应遵循早出乘早下班、晚出乘外下班的出乘原则。所有乘务组在乘务基地进行出退乘作业，广州东广州乘务值乘方式为双班单司机，广州东深圳乘务值乘方式为单班单司机。广深线乘务人员值乘方式如图2所示。

现以广深线6：00—24：00的城际列车开行方案数据为例。其中，有18对列车为广州至深圳直达列车，57对列车为广州东至深圳直达列车，以广州东站为乘务基地，以深圳为换乘站，将广深线城际列车开行方案数据划分为150个乘务区段，如表2所示。

3.2 算例结果

根据上文所述乘务规则约束，输入乘务交路时间相关的参数，实验参数可根据现场具体车站的乘务规则作出相应调整。根据广深线调研数据可得，乘务交路相关时间参数设置为：乘务交路长度不超过2880min，换乘时间不少于12min，间休时间不少于为40min，连续值乘时间不超过300min，出乘时间60min，退乘时间20min。正整数M的取值为2880， ε取值为1（在正常情况下，根据乘务基地广州东的历史乘务数据，查定得到的数值）。运用本文设计的改进蚁群算法进行求解，其中：信息素重要程度因子α=2，启发式信息素重要程度因子为5，信息素挥发因子取0.2，蚂蚁个数取40，设迭代次数为300次。并运用Matlab R2015b进行求解，在Intel core i7-8550U CPU 1.8GHz，内存8GB的计算机上迭代到92次时，目标函数值已趋于稳定且达到最小，此时目标函数值为18452.71523min，迭代过程如图3所示。共得到36条乘务大区段，如表3所示。得到18条子乘务交路，如表4所示。子乘务交路累计工作时长与平均时长关系如图4所示，由图4可看出子乘务交路间任务量较均衡。根据优化结果，可以看出乘务大区段有三种类型：①广州东（广州）广州东，乘务大区段个数为18，占比50%;②广州东深圳，乘务大区段个数有9，占比25%;③深圳广州东，乘务大区段个数为9，占比25%。

3.3 实验结果评价分析

利用设计了乘务交路时间较少、子乘务交路间乘务任务均衡为目标的优化模型和双重策略蚁群算法，编制了广深线

乘务交路计划，计算结果的指标分析如表5所示。结论如下：

1）根据本文设计的基于双重策略的蚁群算法，得到了18条乘务交路。乘务人员执行完一条乘务交路需要两天时间。若乘务人员第一个工作日内早晨6点出乘，那么该乘务人员值乘当日最后一列车不超过14点，即早出乘，早退乘。

比如C7023次列车从广州6：00始发，值乘这次列车的乘务人员就需要5：00从广州东整备出勤，到中午12：41值乘完当天最后一列车退乘休息。充分保证了乘务人员的休息时间，使乘务人员有更多的时间学习业务知识，也利于照顾家人，大大提升了乘务人员的生活幸福指数。

2）从编制的18条乘务交路计划中可看出，没有发生超劳的情况，乘务人员单日最大值乘5列，并且在连续值乘4列后，乘务人员都有不少于40min的间休时间，使乘务人员有更充沛的精力值乘后续列车，有效地保障了列车运行安全。

3）在本文编制的乘务交路计划中，充分考虑到人性化因素。比如每天有9对车底在深圳过夜，即每天必须有9个乘务组需要在深圳公寓休息。这9个乘务组都是从15：00以后出乘，即晚出乘，外下班。比如C7129次列车从广州东18：11始发，直到乘务人员值乘完C7121最后一列车，在深圳站23：53退乘，乘务人员当晚在深圳公寓驻班休息。第二个工作日内，该乘务人员经过充分休息在12：18值乘C7038次列车从深圳始发，20：37值乘C7020从广州东退乘。对于乘务人员来说，每值乘一条乘务交路都有充足的休息時间，体现了乘务交路编制过程中的人性化标准。

4）设计的目标函数既考虑了乘务交路总时长，又考虑了各子乘务交路之间的均衡性。如果某车站发生突发事件，比如深圳市某日要举办大型国际会展，客流激增的情况下，交路间的均衡性不再成为乘务交路编制的关键限制因素，此时重点考虑交路时长问题。根据乘务基地广州东的历史乘务数据，查定得到均衡因子取不同数值时目标函数值的变化，突发事件条件下，可根据乘务交路时长与均衡因子关系图（如图5）对均衡因子进行调整，Pkijε可根据实际需求设定相应较大的数值（如图5），这种情况下乘务交路间的均衡性不再成为重要约束因素，以此来保证救援乘务组能够快速机动地到达事故地点。

3.4 算法对比分析

多数学者在求解乘务计划问题时多采用遗传算法，因此，本文以遗传算法作为对比算法。在同一台计算机上运用Matlab R2015b求解，均衡因子取值与上相同，经过203次迭代后，结果趋于稳定，运行结果为19580.23793min。通过对比分析得，本文设计的改进蚁群算法与遗传算法相比，能够更快地收敛，解的质量也有大幅提升。其中，乘务交路减少了约21.74%、乘务总时长降低了5.76%、交路超劳率为0。两种算法对比结果如表6所示。

4 结语

1）本文建立了总交路时间最小且各子乘务交路间任务均衡的MTSP模型，引入了均衡因子这一概念，使得模型更具备实际意义，在突发事件发生后更容易调整乘务交路计划。同时提出了一种双重策略状态转移的蚁群算法，其特点在于设计了双重信息素、双重策略，提高算法搜索效率的同时避免了传统蚁群算法易陷入局部最优的缺点。

2）通过改进后的蚁群算法与遗传算法相比，得出了本文设计的改进蚁群算法效率更高、解质量更好，对该问题求解有很强的适应性。

3）该模型及算法可为铁路机务部门编制机车乘务人员乘务交路计划提供有价值的决策支持，对增强铁路机务系统应急处置能力具有实际意义和帮助，可作为铁路系统应急处置决策理论的组成部分。

参考文献

[1]BEASLEY J E， CAO B. A tree search algorithm for the crew scheduling problem [J]. European Journal of Operational Research， 1996， 94（3）： 517-526.

[2]CHU S C K. Generating， scheduling and rostering of shift crew-duties， applications at the Hong Kong International Airport [J]. European Journal of Operational Research， 2007， 177（3）： 1764-1778.

[3]DENNIS HUISMAN. A column generation approach for the rail crew re-scheduling problem [J]. European Journal of Operational Research， 2007， 180（1）： 163-173.

[4]GAMACHE M， HERTZ A， OUELLET J O. A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding [J]. Computers and Operations Research， 2007， 34（8）： 2384-2395.

[5]陈海平.高速铁路乘务组织理论与优化研究[D].北京：北京交通大学，2013：42-61.（CHEN H P. Research on theory and optimization of crew organization of high-speed railway [D]. Beijing： Beijing Jiaotong University， 2013： 42-61.）

[6]趙鹏，胡安洲，杨浩.机车乘务人员运用计划的优化编制[J].铁道学报，1998，20（4）：8-13.（ZHAO P， HU A Z， YANG H. Research on optimization of crew scheduling [J]. Journal of the China Railway Society， 1998， 20（4）： 8-13.）

[7]阎永光，黄斌.广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报，2010，8（1）：25-29.（YAN Y G， HUANG B. Research on the crew schedule programming method of Guangzhou-Shenzhen intercity trains [J]. Journal of Transportation Engineering and Information， 2010， 8（1）： 25-29.）

[8]程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京：北京交通大学，2007：21-30.（CHENG Y Y. Research and design of domestic railway crew scheduling method [D]. Beijing： Beijing Jiaotong University， 2007： 21-30.）

[9]王莹，刘军，苗建瑞.客运专线乘务交路计划编制的优化模型与算法[J].铁道学报，2009，31（1）：15-19.（WANG Y， LIU J， MIAO J R. Modeling and solving the crew scheduling problem of passenger dedicated line [J]. Journal of the China Railway Society， 2009， 31（1）： 15-19.）

[10]王媛媛，周成晨，倪少权.基于蚁群算法的客运专线乘务交路计划编制方法研究[J].铁路计算机应用，2009，18（7）：11-14.（WANG Y Y， ZHOU C C， NI S Q. Study on algorithm of crew routing scheduling for passenger dedicated line based on ant colony optimization[J]. Railway Computer Application， 2009， 18（7）： 11-14.）

[11]黄珊.机车乘务人员运用问题及其辅助编排系统研究[D].长沙：中南大学，2014：30-44.（HUANG S. Locomotive crew scheduling problem and scheduling assistant system [D]. Changsha： Central South University， 2014： 30-44.）

[12]田志强.高速铁路乘务计划编制优化理论与方法研究[D].成都：西南交通大学，2011：45-72.（TIAN Z Q. Study on theory and methods of crew planning problem of high-speed railway[D]. Chengdu： Southwest Jiaotong University， 2011： 45-72.）

[13]陈旭，李海鹰，王莹，等.放射状路网条件下动车组运用优化研究[J].铁道学报，2017，39（11）：1-7.（CHEN X， LI H Y， WANG Y， et al. Research on optimization of EMU scheduling for radial HSR network [J]. Journal of the China Railway Society， 2017， 39（11）： 1-7.）

[14]郭璞.铁路客运机车乘务交路编制问题研究[D].长沙：中南大学，2013：24-32.（GUO P. Railway passenger train crew scheduling problem [D]. Changsha： Central South University， 2013： 24-32.）

[15]银大伟.乘务计划编制系统的研究与设计[D].成都：西南交通大学，2008：30-41.（YIN D W. Research and design of crew scheduling system [D]. Chengdu： Southwest Jiaotong University， 2008： 30-41.）

[16]张哲铭，王莹，陈旭，等.高速铁路单一循环乘务值乘计划优化研究[J].铁道运输与经济，2018，40（1）：21-27.（ZHANG Z M， WANG Y， CHEN X， et al. Research on single-circulation crew rostering plan optimization for high-speed railway [J]. Railway Transport and Economy， 2018， 40（1）： 21-27.）

[17]马良，朱刚，宁爱兵.蚁群优化算法[M].北京：科学出版社，2008：57-73.（MA L， ZHU G， NING A B. Ant Colony Optimization Algorithm [M]. Beijing： Science Press， 2008： 57-73.）

[18]段海濱.蚁群算法原理及其应用[M].北京：科学出版社，2005：212-232.（DUAN H B. Ant Colony Algorithms： Theory and Applications [M]. Beijing： Science Press， 2005： 212-232.）

This work is partially supported by the National Key Research and Development Project of China （2016YFB1200100）， the National Natural Science Foundation of China （71861022， 61563028）.

WANG Dongxian， born in 1992，M.S. candidate. His research interests include operation management and decision optimization of rail transit.

MENG Xuelei， bon in 1979，Ph.D.，professor.His research interests include operation management and decision ayoptimization of rail transit.

QIAO Jun， born in 1993，M.S. candidate. Her research interests include operation management and decision optimization of rail transit.

TANG Lin， born in 1989，M.S. His research interests include operation management and dcision optimization of rail transit.

JIAO Zhizhen， born in 1992， assistant engineer. His research interests include organization and optimization of railway traffic， organization of cargo transportation.