固定区段轮乘制乘务交路计划编制模型及算法

林 枫

(中国铁道科学研究院集团有限公司 运输及经济研究所,北京 100081)

截至2018年底,我国高速铁路营业里程接近3万km,高铁路网规模逐渐扩大。为了方便旅客出行、提升客运收益,铁路部门在主要长大干线间开行了大量的长途日间动车组列车,如北京—福州和北京—乌鲁木齐等。现行列车乘务组主要采用包乘制,乘务人员外段住宿次数较多,且单次出乘时间较长,导致列车乘务员身心压力大；另外,我国列车乘务组织管理以客运段为单位,各客运段在人员调配、备班等管理上相对独立,导致乘务组与外段调度员沟通不顺畅,且乘务组运用灵活性也较差。高速铁路乘务交路衔接相对紧凑,随车备品较少,乘务组在途中换乘成为可能,为现有乘务组织模式的转变提供了有利条件。为使列车乘务组织工作适应高速铁路的发展规模,亟待对现行乘务模式进行转变。

国外高速铁路列车乘务组织具有自身特点。法国国土面积较小,铁路线路网络上的单程列车径路较短,交路计划中基本不存在乘务员中途换乘的情况[1]。而日本高速铁路网呈线性结构且线路较长,乘务员组织和运用按照JR各公司的管辖范围分区段进行[2]。借鉴国外乘务运用组织的经验,以及国内高速铁路发展现状,本文提出基于“固定区段轮乘”的列车乘务组织模式。首先根据换乘节点,将某条运行线划分为若干区段,每个区段由固定的客运段的乘务员不越区段值乘,根据乘务规则制定基于“固定区段轮乘”的乘务交路计划。

乘务交路计划(Crew Scheduling Problem,CSP)是编制乘务计划的核心内容,也是编制乘务排班计划的基础。国内外学者对乘务计划编制的研究已取得了一系列成果,在乘务排班计划的研究方面, Ernst等[3]、Caprara等[4]、Barnhart等[5]主要采用启发式算法对乘务排班计划进行求解；Hanafi等[6]根据多个乘务基地,构建了乘务组费用最小化的优化模型,从而得出最优乘务交路方案；赵鹏等[7]、李献忠等[8]、石俊刚等[9]以乘务广义费用最小为目标,分别采用Simulated Evolution法、禁忌搜索算法、列生成思想结合拉格朗日次梯算法求解乘务排班问题。在乘务交路计划研究方面,Monfroglioa[10]根据遗传算法的思想,以乘务费用最小化为目标得到求解航空乘务组轮乘交路问题；Tian等[11]、Wedelin等[12]、Lan等[13]、Ryan[14]、郑金子等[15]将乘务交路计划归纳为集覆盖模型(SCP),分别采用了分枝定界法和启发式算法进行求解；王莹等[16]在上述方法的基础上,设计了列生成法和分枝定界法相结合的算法求解SCP问题。

大部分求解算法未考虑实际中普遍存在的乘务组便乘现象,这是因为考虑便乘时,每个值乘区段(根据列车停站和列车运行线分割成乘务员最小任务单元)被选择的次数不止1次,生成的可行解将大幅增加,导致大多数启发式算法很难在大规模问题中较快地得到较优解。而且,当乘务模式由现行“包乘制”转变为“固定区段轮乘模式”时,需要对某一条高铁线路集中编制乘务交路,相比以往以客运段为单位编制时,求解规模成倍增加。因此本文在既有研究的基础上,采用“分层序列法”的思想,设计了多目标多层次求解模型,并应用Python语言设计编制相应的求解算法MOMS (Multi-objective Multi-stage Optimisation of Crew Plans),并生成基于“固定区段轮乘”的列车乘务交路编制软件。

1 问题描述

列车乘务交路计划是指一段时间内,乘务人员(组)从乘务基地出发至回到乘务基地的一次工作计划,包括需要的乘务员(组)数和值乘列车等内容。乘务员(组)一天的工作计划称为交路段[16]。一个乘务交路段由若干满足条件的值乘区段组合而成。乘务交路计划的编制效果直接决定了完成运行计划所需的乘务员(组)数量[17],乘务交路段个数直接影响乘务计划中所需乘务组数。根据我国高速铁路现行乘务员管理情况,为保证乘务员的段内休息和学习培训，以及乘务交路时间的均衡性,部分乘务交路由2个乘务交路段组成。

图1 “固定区段轮乘模式”乘务交路编制过程

由图1可知,编制基于“固定区段轮乘”乘务交路时,首先选择换乘站c(分界点),将A和B两站间运行线划分为值乘区段Ac和cB；以乘务组总接续时间最少(即乘务组数最少)为优化目标,设W为乘务规则集合(具体见下文“高速铁路乘务规则”),在满足集合W且覆盖区段集合Ac或cB的条件下,分别求得最优乘务交路段集合P1或P2；若集合P1和P2存在过夜交路段,则以过夜费用、便乘费用最少为目标,将过夜交路段两两组合为闭合回路(即过夜交路),从而分别得到Ac和cB集合内的最优乘务交路方案。

高速铁路乘务规则[17]:(1)在一条乘务交路中,后一值乘区段的出发站应与前一值乘区段的到达站相同,且衔接时间不小于乘务组的最低换乘时间标准；(2)生成的可行乘务交路段集合需覆盖所有值乘区段；(3)乘务员一天的出乘时间(包含图定运行时间,本、外段出、退乘时间,接续时间)不允许超过一天最长乘务时间；(4)乘务员退乘后,到下一次出乘的间隔时间不小于8 h；(5)乘务交路最多包含2条乘务交路段。

2 列车乘务交路双层优化模型

高速铁路乘务计划的编制涉及铁路运营组织和乘务员双方的利益。从铁路运营组织的角度,编制乘务计划应尽可能减小乘务组需要数量；而从乘务员的角度,希望过夜次数较少的乘务任务安排。因此乘务交路计划的合理安排是双层规划问题,即以乘务总时间和乘务组过夜次数最少为双层优化目标。

当乘务模式由现行“包乘制”转变为“固定区段轮乘”模式时,乘务交路的编制单位规模由客运段转变为按区域统一编制,相应的求解规模大幅增加。本文采用“分层序列法”,构建了问题的双层规划模型。第一阶段,以总接续时间最小为优化目标,找出最优乘务交路段集合,其中始发、终到站相同的乘务交路段称为非过夜交路段,也可称为“非过夜交路”,始发、终到站不同的乘务交路段称为“过夜交路段”。第二阶段,将上一阶段得到的过夜交路段优先通过两两匹配组合为闭合交路(即过夜交路),无匹配的过夜交路段采用便乘的方式组合为闭合交路,即在便乘时间较少的前提下尽可能减少乘务组过夜。过夜和非过夜交路组合即为最优乘务交路方案。

2.1 最小化乘务交路段方案的总接续时间优化模型

(1)

(2)

(3)

(4)

(5)

(6)

Xijk∈{0,1} ∀k∈K∀i,j∈N

(7)

式(1)为目标函数,表示总接续时间最少。式(2)为接续时间约束,表示相连接的值乘区段i和j的接续时间不小于乘务组最低换乘时间标准。式(3)表示交路段的总乘务时间不允许超过一天最大乘务时间。式(4)为相连接值乘区段出发、到达站的接续约束,即后一值乘区段出发站与前一值乘区段到达站相同。式(5)和式(6)为值乘区段约束,表示每一值乘区段都连接一个前值乘区段和一个后值乘区段。式(7)为0-1变量的约束条件。

2.2 最小化乘务交路方案的过夜和便乘费用的优化模型

本阶段将上一阶段生成的过夜交路段,通过两两匹配或便乘(便乘是指乘务人员为执行值乘任务或结束值乘任务搭乘列车往返于任务地与居住地的行为)的方式组合为闭合交路,得到最优乘务交路方案。

(8)

(9)

Yg∈{0,1} ∀g∈G

(10)

式(8)和式(9)为目标函数,分别表示过夜费用E2和便乘费用E3最小化。计算交路便乘时间时,每条乘务交路的便乘时间范围大部分在100～180 min之间,为了避免交路中过夜费用和便乘费用差别较大,且过夜费用起决定性作用,因此取便乘时间单位费用cbc为1元/min,每条交路便乘费用大部分为100～180元,过夜交路费用取200元/条(选取京沪和京广高速铁路列车经停的重要城市连锁酒店的标间费用,按照每间住2人来计算乘务员外段住宿费用)。式(10)为变量取值约束。

3 模型求解

本文借鉴相关算法[18],设计了多目标多阶段乘务交路计划优化算法MOMS 。总体思路是,对每种分界点方案,以“最短路原理”生成总接续时间最少的“第一阶段优化方案”(即乘务交路段方案),在此基础上对过夜次数、便乘次数等目标进行优化,最终得到“第二阶段优化方案”(即乘务交路方案)。MOMS求解算法的具体流程见图2。

图2 MOMS算法流程图

为了比较固定区段轮乘制和包乘制,通过算法求解生成两个指标,一是总接续时间,用来计算总乘务组数；二是过夜交路数,体现乘务组过夜次数。其中总乘务组数是方案选择的主要目标,过夜次数是辅助决策目标。

第一阶段求解算法的目标是尽可能减少乘务组数,在以接续时间最小为研究目标的前提下,该求解算法使得每条乘务交路段尽可能多的包含值乘子区段,从而保证生成的交路段数量最少。交路段数量直接影响所需乘务组数。

3.1 第一阶段优化方案集求解算法

Step1初始化。原有时刻表集合为Rorig,新生成时刻表集合Rnew,值乘子区段为n,交路段为k(k∈K)。

Step2生成新时刻表集合。根据固定区段轮乘制分界点的选择,将原线路时刻表集合拆分后得到新的时刻表集合Rnew,并将Rnew按出发时间升序排序。

Step3生成初始乘务交路段集合。根据高速铁路乘务规则,将集合Rnew中值乘区段按照从上至下的顺序,组合为乘务交路段k,直到每一值乘区段被选择1次为止,最终形成乘务交路段集合K,并计算所有交路段的总接续费用。

3.2 第二阶段优化方案求解算法

为实现便乘时间增加较少的情况下尽可能减少乘务组过夜次数,对“过夜交路段”优先组合成当天返回始发站的“非过夜交路”,然后将剩余“过夜交路段”相互组合成过夜交路,以图1中集合P1的乘务交路段为例,具体生成步骤见图3～图5。

Step4从集合K中筛选出过夜交路段集合。将集合K中所有“过夜交路段”按包含的子区段数分为2类:“多过夜交路段”(包含2个及以上子区段的交路段)和“单过夜交路段”(包含1个子区段的交路段)。

Step5将过夜交路段组合为“非过夜交路”。主要包括以下3步,具体见图3。

Step5-1在多过夜交路段两端并入单过夜交路段,组成“非过夜交路”。在单区段交路段集合中,从上至下搜索满足乘务规则的交路段,并入多区段交路段的首端或尾端,组合为新的“非过夜交路”。

Step5-2将剩余多过夜交路段拆解后与单过夜交路段合并,组成2条“非过夜交路”。在多过夜交路段集合中,从上之下搜索满足乘务规则的交路段,使其起始子区段或末尾子区段能够与单过夜交路段重组为2条“非过夜交路”。

Step5-3在多过夜交路段首端或尾端添加便乘区段,组成“非过夜交路”。对于剩余多过夜交路段,在集合Rnew中,从上至下搜索满足乘务规则的值乘区段,作为便乘区段并入多过夜交路段的首端或尾端,组合为“非过夜交路”。

Step6将过夜交路段两两组合或加便乘的方式形成闭合“过夜交路”,并统计过夜交路数。主要包括以下3步,具体见图4。

图3 过夜交路段组合为非过夜交路

图4 过夜交路段组合为过夜交路

Step6-1多过夜交路段两两组合为闭合“过夜交路”(即第2天返回始发站的交路)。在剩余多过夜交路段集合中,从上至下搜索满足乘务规则的2条交路段,组合为闭合“过夜交路”；若不存在,则在已组合的便乘交路(Step5-3中生成交路)中寻找与其组合为过夜交路,如存在,则删去组合的便乘区段。

Step6-2多过夜交路段与单过夜交路段组合为“过夜交路”。对于多过夜交路段,在单过夜交路段集合中,从上至下搜索满足乘务规则的交路段,与其组合为“过夜交路”。

Step6-3选择某一区段与多过夜交路段组合为过夜交路。对于多过夜交路段,在集合Rnew中,从上至下搜索满足乘务规则的值乘区段,与其组合为“过夜交路”。

Step7为剩余单过夜交路段添加便乘,组成“非过夜交路”,减少过夜次数。对于单过夜交路段,在集合Rnew中,从上至下搜索满足乘务规则的值乘区段,与其组合为“非过夜交路”。

Step8将剩余单过夜交路段两两组合为过夜交路。Step7、Step8见图5。

图5 单过夜交路段组合为闭合交路

Step9输出交路方案,统计分析评价指标。计算结束,输出交路方案,统计交路方案的各主要评价指标,例如:交路数,便乘数,过夜数,月均乘务时间等,算法结束。

3 实例分析

本文选择2017年3月京沪和京广高速铁路的本线列车以及跨线车在本线的运行区段作为研究对象。筛选后京沪高速铁路为171对列车,京广高速铁路总车次为168对列车。其中“原方案”是以现在采用的“包乘制”进行乘务交路编制,“分界点方案”是以“固定区段轮乘”模式进行乘务交路编制。在获取了京沪、京广高速铁路各路局的现行乘务排班计划后,发现各路局的排班计划相对略有差别,且存在本线和跨线组合的乘务交路,为了避免各路局交路的差别,本文编制了“高速铁路列车乘务交路编制软件”,根据乘务规则采用统一标准,应用软件编制不同方案的列车乘务交路和计算相关指标值。其中，乘务组数是根据总乘务时间来计算，即

n=(T总/t)·(1+L备)

(11)

t=T标/30

(12)

式中:n为所需乘务组数,组/月；T总为乘务交路方案总乘务时间,h；t为乘务组每天乘务时间标准,h；L备为班组备员率,依据铁路部门的标准L备=0.1；T标为乘务组每月乘务排班工作时间标准,T标=166.6 h。

根据客运段在路网的重要性(综合有无动车检修所、动车运用所数量等指标)、是否具备一定规模的乘务休息场所(固定区段轮乘制下会产生大规模乘务组在分界点换乘和休息)、值乘子区段保证必要的乘务作业时间,以及各乘务组换乘次数的均衡性,京沪高速铁路分界点分别选择济南西、徐州东和南京南；京广高速铁路分界点分别为郑州东、武汉和长沙南。应用乘务交路软件得出京沪、京广高速铁路各乘务交路方案指标值见表1、表2。

表1 京沪高速铁路乘务交路指标值

表2 京广高速铁路乘务交路指标值

(1)京沪、京广各分界点方案相比原方案增加的总乘务时间，见图6、图7(图7中负值表示总乘务时间比原方案小)。

图6 京沪各分界点方案相比原方案增加的总乘务时间

(2)京沪、京广各方案每月过夜次数，见图8、图9。

图8 京沪各方案每月过夜次数

图9 京广各方案每月过夜次数

(3)京沪高速铁路各运行区段密度和接续时间，见图10～图12。

图10 京沪高速铁路各区段个数和换乘次数

图11 京沪高速铁路各区段平均接续时间

图12 京沪高速铁路各方案总接续时间

(4)京广高速铁路各运行区段密度和接续时间，见图13～图15。

图13 京广高速铁路各区段个数和换乘次数

图14 京沪高速铁路各区段平均接续时间

图15 京广高速铁路各方案总接续时间

由表1、表2得到图6～图15,可以看出:① 随着分界点增加,总乘务时间逐渐增加,而过夜次数和便乘时间则逐渐减小；② 在1个分界点方案中,分界点距离运行线中部较近的方案过夜次数最少且总乘务时间较小,优越性较强。

从各分界点方案相比原方案增加的总乘务时间(图6、图7)可知,在京沪高速铁路方案中,总乘务时间随着分界点的增加增幅较大,分界点总乘务时间相比原方案最大增幅在158 h；而京广高速铁路方案中,总乘务时间随着分界点的增加先增加后逐渐减小,而3个分界点方案的总乘务时间相比原方案减少了18.40 h。

从便乘时间(表1、表2)可知,随着分界点的增加,便乘时间大幅减小,从而减少了乘务低效作业时间(因为乘务便乘时不执行乘务任务)。

从区段个数(图10、图 13)可知,京沪高速铁路各区段的个数在210左右,而京广高速铁路各区段个数在130左右,因此京沪高速铁路各区段密度相对较大,区段之间接续性较好。

从总接续时间(图12、图15)可知,京沪高速铁路中,各方案总接续时间随着分界点的增加而逐渐增大；而京广高速铁路中,原方案的总接续时间与分界点方案接续时间相差较小,且总接续时间随着分界点增加而先增大后减小；在京沪高速铁路原方案中,过夜交路较少,为240次/月(8次/d),大部分列车当天即可返回始发站；其次,由于北京开往上海的往返列车比例较高(45对),占总开行列车比例的26%；此外,对比图10、图11,区段数较多时接续时间较短(徐州东与南京南),而区段数较少时接续时间较长(南京南与上海虹桥)。综上所述,各区段列车的接续时间相对均衡。因此,对于全程运行时间较短,采用固定区段轮乘制后,总接续时间和总乘务时间随着分界点的增加而大幅增加,导致所需乘务组数大幅增加,而且也未能实现过夜次数大幅减少的需求。因此，对于运行时间较短的线路,例如京津高速铁路不适合采用固定区段轮乘模式。

而在京广高速铁路原方案中,过夜交路较多,为690次/月(23次/d),大部分列车当天无法返回始发站；其次,北京开往广州的往返列车比例较低,占总开行列车比例的3%；此外,对比图13和图14,区段数较少的平均接续时间较短(郑州东与武汉),而区段数较多的接续时间较长(长沙南与广州南),综上所述,各区段列车的接续时间相对不均衡。

综上所述,对于京广高速铁路方案,由于各区段列车接续时间较不均衡,且整条线路总运行时间较长,无法在当天返回始发站,当采用固定区段轮乘模式后,将整个运行线划分为若干小区段后,例如分界点为3个时(郑州东、武汉和长沙),不仅降低了区段内列车的平均接续时间(表1和表2),而且,乘务便乘时间也大幅减少；此外,过夜交路数大幅减少,进而减少了乘务过夜次数。因此本文提出采用固定区段轮乘制的适应条件为:(1)全程列车比例较小,且列车开行密度较大但各区段列车接续时间相对不均衡；(2)列车全程运行时间较长,当天无法实现往返。由于乘务组一天出乘时间最长为16 h,刨除必要的出退乘时间1 h,可知采用固定区段轮乘制的整条线路总运行时间应大于7.5 h。

4 结束语

当乘务模式转变为“基于固定区段的轮乘模式”时,需要对某一条高速铁路线路集中编制乘务交路,相比以往以客运段为单位编制时,求解规模大幅增加,传统的分枝定界和启发式算法很难在较短时间内获得较优解,本文设计了MOMS算法并采用Python语言编程实现,能够在10 s内生成最优方案。选择京沪和京广高速铁路本线列车以及跨线车在本线的运行区段作为研究对象,对比分析了“包乘制”和“基于固定区段的轮乘模式”的乘务交路方案,得出如下结论:(1)相比包乘制,固定区段轮乘制可以大幅减少乘务组外地过夜次数,且分界点越多,过夜次数越少。过夜次数减少不仅降低了铁路部门的成本,而且提高了乘务员的工作热情。(2)对总乘务时间和过夜次数影响较大的因素分别是分界点个数及分界点在运行时间上是否均衡分布。当分界点个数确定时,分界点在运行时间上相对均衡分布的方案总乘务时间和过夜次数较少,方案较优。(3)综合考虑总乘务时间、过夜次数和便乘时间3项指标,京沪高速铁路的最佳方案是原方案；京广高速铁路的最佳方案是以郑州东、长沙和武汉3个分界点的方案。(4)从运行线长度,列车开行密度和全程列车开行比例3方面分析论证固定区段轮乘模式的适用条件。认为当整条线路总运行时间大于7.5 h,列车开行密度较大,但全程列车开行比例较小(或各区段间平均接续时间较不均衡)时,适合采用固定区段轮乘模式；当整条线路总运行时间小于7.5 h时,不适合采用固定区段轮乘模式。