许仲豪， 杜 鹏，2

(1. 北京交通大学 交通运输学院， 北京 100044； 2. 北京交通大学 城市交通复杂系统理论与技术教育部重点实验室， 北京 100044)

城市轨道交通乘务计划是安排乘务员值乘的工作计划，是城市轨道交通运营计划的重要组成部分。随着人工成本越来越高，合理、优化的乘务计划在降低运营成本方面的作用日益受到重视，关于乘务计划优化编制方法的研究也成为城市轨道交通运营领域的一个研究热点。乘务计划一般分为乘务排班计划和乘务轮班计划，其中乘务排班计划是寻找列车车次与乘务任务之间的对应关系，是乘务轮班计划的基础，也是整个乘务计划编制过程中最复杂、难度最大的部分。

城市轨道交通乘务排班计划编制过程中，主要涉及以下几个概念。车底是列车周转的基本单位，指执行一次周转任务的一列列车。乘务作业段是乘务员值乘的基本单元，代表一列车从一个轮乘站前往下一个轮乘站之间的驾驶任务。乘务任务是一日内一组满足实际工作中的约束的可由一名乘务员值乘的乘务作业段的组合，乘务任务的工作时长为其第一个乘务作业段的开始时间至最后一个乘务作业段的结束时间。乘务日计划是所有乘务员一日的工作计划，是乘务任务的组合，且这一组乘务任务中包含了所有乘务作业段。乘务计划编制是将车底周转图以轮乘站为边界分解为乘务作业段，再将乘务作业段相互组合成为乘务任务，最终形成乘务日计划的过程。

乘务计划编制问题是根据已有的列车运行计划编制乘务日计划的问题，是交通领域研究的热点之一。目前研究者们对乘务计划编制问题的研究主要集中于铁路、航空及城市地面公共交通行业。乘务计划编制问题由于实际工作中需求不同，目标函数多样、约束条件复杂、解空间巨大，已经被归为NP-Complete或NP-Hard问题，因此针对该问题的算法也多局限于启发式算法：褚飞跃等[1]、杨国元等[2]、夏平等[3]、闫永光等[4]分别将蚁群算法、遗传算法、启发回溯算法、模拟进化算法用于铁路领域的乘务计划编制；李耀华等[5]、吴东华等[6]分别使用遗传算法与结合模糊数学的启发式算法求解航空领域的乘务计划编制问题；陈明明等[7-8]则在地面公交领域使用禁忌搜索算法优化进行乘务计划优化编制。

城市轨道的乘务计划编制与其他交通方式有所不同，具有乘务作业段时间短、乘务员可在异地交接车的特点，因此不能将适用于其他交通方式的乘务计划编制方法生搬硬套进城市轨道交通领域中。在城市轨道领域，研究者们已经做出了大量的研究：李献忠等[9]将乘务计划分作划分乘务作业段与编制乘务日计划两步进行，将问题化为最小费用最大流的问题进行求解；张增勇等[10]在描述问题时，将约束条件分为硬约束与软约束，并对不满足软约束的乘务任务进行惩罚，在此基础上利用离散粒子群算法对问题进行求解，能够有效减少不满足软约束的乘务任务数；丰富等[11]参照中国的“两班倒”工作制度，以乘务任务在车时长的方差为目标函数建立了乘务计划编制的数学模型，并设计了一套可行的遗传算法来求解。

以上研究大多直接使用启发式方法求解问题，能在可接受的时间内得到可行的解。对于乘务计划编制这类拥有大量乘务作业段的问题，启发式方法有很大的应用空间。在规划方法求解方面，以列生成为代表的分解算法也是当前的研究热点之一。Potthoff等[12]使用一种改进的列生成算法，以荷兰的一段城际轨道网的运营为例，探究了突发情况下的乘务调整计划编制，并取得了较好的编制结果；Janacek等[13]提出了一种周期性的乘务计划编制方法，根据时间段将问题分为多个区间，每个区间均作为列生成算法中的一个子问题，便于并行求解，加快新列的生成速度；陈仕军等[14]考虑了中式就餐的特殊约束，以列生成算法为基础设计了求解方法；王莹等[15]针对客运专线的特点，建立了集合覆盖模型并设计了基于列生成算法的求解方法。

考虑到乘务计划编制问题具有较强的地域性，实际工作中的目标与约束也有较大差异。直接使用启发式算法，虽然能够获得可行解，但是求解过程比较特殊，且对具体问题的依赖性较强。规划方法具有模型严谨的优点，但是应用在乘务计划编制领域，也存在求解方法较为复杂、繁冗的困难，如何适应实际需求值得深入研究。本文沿用前人使用列生成框架求解的思路，提出一种实用的乘务排班计划优化编制方法。在子规划的设计方面，建立了一种新的能够快速生成判别数较小的新列等效网络图模型，该模型利用主规划每次迭代过程中所产生的影子价格，以影子价格向量中最大的分量所对应的乘务作业段为基础选取最短路，从而快速产生质量较优的新列。

1 问题描述

以某个乘务任务为例简单说明，见图1。图1中有3列车辆的周转任务，“BT021”等为车底编号。该线路上有一个轮乘站，该轮乘站将每列车辆的运行任务分割为一系列乘务作业段，每个乘务作业段有其开始/结束的时间与地点，在图中一个完整的矩形代表一个乘务作业段。当若干个乘务作业段满足实际工作的需求时可以相互组合。以最小间休时间10 min、一次最长在车时间120 min为例，可将3个深色乘务作业段组合为一个乘务任务(乘务任务1)。该乘务任务共有两段间休时间，分别为15、10 min。最小间休时间在图中用虚线白色矩形表示。间休时间中超出最小间休时间的部分属于非必要劳动时间，在图中以黑色矩形表示。该例子中，第一次间休中有5 min为非必要劳动时间。

一个乘务任务中，乘务员用于驾驶的时间与乘务任务的工作时长之比为该乘务任务的工作效率，如图1所示的乘务任务1，驾驶时间为135 min，工作时长为160 min，则工作效率为84.38%。非必要劳动时间的存在影响了乘务日计划的工作效率，非必要劳动时间越多，日计划的工作效率越低。除工作效率外，一个乘务日计划中乘务任务的个数也是衡量乘务日计划质量优劣的重要标准。乘务任务数代表一个日计划运用乘务员的数量，对运营机构的人工成本有直接影响，乘务任务数越多，需要的乘务员数量就越多，人工成本越高。乘务任务数与工作效率共同反映了乘务计划编制的优劣情况，运营机构一般倾向于较少的乘务任务数与较高的工作效率。

2 模型构建

在列生成算法的框架下，主规划是一个线性规划，其目标函数和约束条件描述了解的构成，但是每次迭代只在部分列中寻优；子规划则根据实际需要构建，不断生成具有较优判别数的可行新列代入主规划，使主规划的解在下一步获得更优的解。简而言之，列生成算法是一个通过不断提高主规划中的列的质量，从而得到最优解的算法。

2.1 主规划

集合分割模型[8,10-11,13]与集合覆盖模型[12,14-15]均可用于描述乘务计划编制问题。采用集合覆盖模型的优点在于能够直观地将问题描述为允许乘务员在多个轮乘站之间周转的情况，集合分割模型对问题的描述会更为切合实际，即一个乘务作业段能且仅能被一个乘务任务执行。

本文采用集合分割模型作为主规划为

minw=∑cjxj

( 1 )

s.t.

∀i∈Ut

( 2 )

xj∈{0,1} ∀j∈Us

式中：w为总成本；Us为乘务任务的集合，j∈Us，为乘务日计划中第j个乘务任务；cj为乘务任务j的成本，与组成的乘务作业段及其衔接关系相关，取值详见2.2节；xj为0-1变量，表示乘务任务j是否入选日计划，1为入选，0为未入选；Ut为乘务作业段的集合，Ut={1，2，…，m}，i∈Ut；aij为0-1参数，表示乘务任务j是否包含乘务作业段i，1为包含，0为未包含。

考虑到在列生成框架下，主规划每次迭代时可选的列均由子规划产生，因此主规划仅需对乘务任务是否入选进行约束，乘务任务的可行性约束可以在子规划中讨论。

2.2 迭代过程与成本函数

根据转轴迭代法，判别数最小的列入基才能使主规划的目标函数得到最大改善。第j个乘务任务的判别数为

σj=cj-πAj∀j∈Us

( 3 )

式中：π为行向量(π1,π2,…，πm)，其中πi是主规划中第i个约束条件的单纯形乘子，又称为影子价格，由成本cj与基矩阵B共同求得；Aj为第j列上aij组成的列向量，即第j个乘务任务的组成形式。

由于在式( 3 )中除列向量Aj外各参数皆与cj的取值有关，因此cj取值的定义将直接影响新生成的列的质量。因为运营机构更倾向于选择拥有较少的乘务任务数与较高的工作效率的乘务日计划，cj的取值也需要反映这两项标准。其中，工作效率为乘务日计划中值乘时间与工作时间的比，值乘时间与间休时间共同组成了工作时间。在值乘时间不变的情况下，间休时间越长，工作效率越低，该乘务任务的成本cj越高，乘务任务数则可在每个乘务任务的成本cj中添加作为惩罚值的常数进行约束。

本文通过为每个目标设定权重系数将多目标化为单一目标，既便于求解，又能直观反映运营机构对各目标的重视程度。成本cj可以为

∀p，q∈Ut

( 4 )

式( 4 )中W0、α、β皆根据运营机构的需要与实际情况赋值，将直接影响编制结果。其中，期望工作时间W0是一个惩罚值，代表每增加一个组成日计划的乘务任务所增加的基础成本，以此约束乘务任务的数目。非必要劳动时间与值乘时间则是与工作效率直接相关的量，是成本的重要参数。

需要注意的是，当β取0时，代表在成本函数中完全忽略了非必要劳动时间的影响，即不再考虑工作效率的高低，以此得到的乘务日计划中乘务任务数最少。另外，因为在车时间的总和为定值，所以α的取值不影响日计划的统计指标，只影响目标函数值。

2.3 子规划

根据式( 3 )中经典判别数计算方法，生成的新列需要有最小的判别数以优化主规划的目标函数，可将子规划的目标函数写为

( 5 )

式中：A=(a1,a2,…,am)，ai为乘务作业段i是否被新乘务任务执行；c(A)即为式( 4 )中的cj，代表cj是A的函数。在子规划中，需要求出可行的A使σj最小。本文用一个等价的最短路问题来描述子规划。

建立网络图G(N,E)，集合N为图中的点的集合，每个点代表一个乘务作业段。同时，每个点上都有点的属性N(tbp,tep,sbp,sep,trp,wp)，tbp、tep代表该乘务作业段的开始与结束时间，sbp、sep代表该乘务作业段的开始与结束地点，trp为执行该乘务作业段的车底，wp为该点代表的乘务作业段的权值，由该点对应的主规划的行的单纯形乘子决定。集合E为图中有向弧的集合，每条有向弧代表该弧相连的两个点在时间与空间上可接续，并且从时间关系上来看，弧只可由先进行的乘务作业段指向后进行的乘务作业段。弧上有权值dpq，由该弧相连的两个点代表的乘务作业段的时空关系决定。弧的主要约束包括如下两条

tbq-tep>Trsbq=sep且trq≠trp

( 6 )

tbq-tep>Twsbq≠sep

( 7 )

式( 6 )代表间休时间的约束，即非连续值乘时，期间的休息时间需大于最短间休时间Tr；式( 7 )代表异地接车时间约束，即在异地接车时需要为乘务员安排一定的走行或便乘时间Tw。当满足这两个条件时，弧epq存在。

综上，可以用网络模型描述子规划的解空间。令s为图上的一条路径，s(N)为路径的点集合，s(N(n))代表s上的第n个点，且s总共包含z个点。s(E)为路径的弧的集合。根据乘务计划编制的要求，建立的作为子规划的最短路问题的数学模型为

( 8 )

s.t.

∀p∈s(N)

( 9 )

tes(N(z))-tbs(N(1))

(10)

tes(N(p))-tbs(N(q))

trs(N(p))=trs(N(p-1))=…=trs(N(q))

(11)

tbs(N(p))-tes(N(p-1))>Td

(ds,de)∩(tes(N(p)),tbs(N(p-1)))≠∅

(12)

式( 9 )为s作为路的基本约束；式(10)为工作时长约束，即从出勤时刻到退勤时刻的约束；式(11)为连续最长在车时间约束，即连续值乘的时间不能大于规定的最长连续在车时间；式(12)为就餐约束，即为乘务员安排的最短就餐时间。当一名乘务员的工作时间跨越规定就餐时间段时，需要为其安排就餐时间，且不得小于最短就餐时间。

为了令网络图的最短路问题与子规划问题等价，需要对图上点与弧的权重进行定义。根据一个乘务任务的成本函数式( 4 )与子规划目标函数式( 5 )，可以将子规划目标函数为

(13)

整理后得

(14)

式中:W0为常数，在求解最优解时可忽略。为使子规划目标函数与网络图中最短路的权值等价，可以将与ap相乘的数作为点上的权值，将与bpq相乘的数作为弧上的权值

wp=-(αTp+πp)

(15)

dpq=βRpq

(16)

综上，网络图中的最短路即为子规划的最优解。

3 求解算法

3.1 构建初始解

使用列生成算法求解问题时需要先构造一组初始可行解。本文以所有乘务任务只包含一个乘务段的日计划为初始可行解。这种做法的优点一是便捷，无需经过繁琐的步骤即可获得满足条件的乘务任务，二是该初始可行解易于用矩阵形式表达，初始矩阵即为单位矩阵。

3.2 迭代过程

迭代过程分为主规划和子规划两部分。作为主规划的整数规划，一般先被松弛为线性规划，求出最优解后经过剪枝得到整数解。这一部分的求解算法较为成熟，也不乏商业软件应用。但是子规划需要在拥有数百个节点、上千万条弧的网络中找出若干条满足各种约束条件的最短路，经典的搜索方法计算量过于庞大，不适用于本问题。除了问题规模较大以外，在实际工作中还需要考虑到各个乘务任务在车时间的均衡性。现场工作中往往会采用将所有乘务任务中乘务作业段的数目限制在一定数额的做法，如每个乘务任务中均包含2～4个乘务作业段。这也导致了经典的标号法如dijkstra算法并不适用于本问题。对此，本文结合现场实际情况提出一种基于影子价格选择的标号法。

基于影子价格选择的标号法在进入子规划的第一步按照一定标准选出一个乘务作业段作为起始的乘务作业段，同时删去无法与该乘务作业段接续的无关乘务作业段。在随后的迭代步骤中，以选择的起始点为中心，向前后搜寻可以接续的点并标号。

本方法能够搜索到拥有固定数目乘务作业段的乘务任务中耗费成本较少的乘务任务。由于在第一步采用了局部最优的选择方法，大幅度降低了迭代过程中的搜索范围，加快了算法的速度。

(17)

式中：

wq=-(αTq+πq)

(18)

(19)

Step3对所有可接续的路进行筛选，若一条路代表的乘务任务不满足约束式(10)～式(12)，则跳过这条路。

Step6若k达到了预设的每个乘务任务包含乘务段的个数限制，则退出迭代。若还未达到，则返回Step2。

本方法一次迭代可以生成若干个包含不同个数乘务段的新列，同时代回主规划中，既可以加快主规划收敛的速度，也增加了乘务日计划的灵活性。初始点的选取是该方法中的重要一环。在每次求解主规划后，在网络中选择一个合适的初始点，能够较快捷地找到让主规划得到更大优化的新列。

综上，本文所使用的乘务计划优化编制方法的流程见图2。

4 实例分析

在本文提出的模型和算法基础上，使用C#语言开发了城市轨道交通乘务计划优化编制系统，其中主规划求解部分嵌入了ILOG CPLEX调用。应用该系统，对北京地铁某线路的乘务计划编制问题进行了系统研究。

该线路每日运营时间为05:10～23:55，高峰小时最小发车间隔为4 min，使用车底24组。将列车周转图按轮乘站和车辆段进行划分，可分为255个乘务作业段。当前的乘务日计划为每日76个乘务任务，每个乘务任务工作时长由3 h到8 h不等，其中包含2至4个乘务作业段，工作效率为82.352%。

本次研究根据现场乘务日计划的情况与实际运营中对各项目标的重视程度，为成本函数中的参数赋值，设定每次迭代生成的乘务任务中包含2至4个乘务作业段，对比数种状况下不同日计划包含的乘务任务数与工作效率的优劣性。

为了验证本文提出的算法的可行性与优越性，取α=0,β=1，同时W0的取值为180至480，代表现场所使用的乘务日计划中乘务任务的持续时长为3～8 h。将通过算法得到的乘务日计划与现场目前使用的乘务日计划做对比，比较二者根据式( 1 )与式( 4 )计算得出的成本，见表1、图3。

表1α=0,β=1时改变W0原日计划与算法日计划成本比较

W0原计划成本本文算法成本W0原计划成本本文算法成本18035 02533 59536048 70546 79924039 58537 78942053 26551 73930044 14542 77548057 82555 186

可以看出，不论期望工作时长如何取值，本算法取得的乘务日计划的成本都比现场使用乘务日计划的成本更少，可见本研究算法不仅可行，编制的乘务日计划也优于现场使用的日计划。采用本算法的编制系统运行于普通PC机(1.70 GHz CPU、4.00 GB RAM)，仅需几分钟即可自动生成优化方案，而现场人工编制出一套方案往往需要若干天。

为进一步分析乘务任务数与工作效率之间的关系，从而为运营机构编制乘务计划提供有效的参考，本文采用控制变量法，研究了成本函数中各参数的取值变化对编制结果中乘务任务数与工作效率的影响。

先保持值乘时间与非必要劳动时间的权重不变，调节期望工作时长W0，可得到统计结果分别见表2、表3，以及展现其变化趋势的柱状折线见图4。

表2 α=1,β=1时改变W0对编制结果的影响

表3 α=0,β=1时改变W0对编制结果的影响

不论是否考虑在车时间的影响，可以看出当α、β保持不变时，期望工作时间W0越大，乘务任务数在逐渐减少，但工作效率呈现逐渐降低的趋势。这是由于当增大每个乘务任务的期望值乘时间时，加大了单个乘务任务成本中的常数值，在非必要劳动时间的权重参数不变时，对非必要劳动时间长短，即工作效率的考虑会有所下降。因此编制结果会倾向于选择用更少的乘务任务完成所有乘务作业段，而对工作效率的要求便会降低，工作效率会随着期望工作时长的增加而减少。

若保持期望工作时长W0不变，并且取值乘时间权重α分别取0或1时，调节非必要劳动时间权重β，可得到如下的编制结果，分别见表4、表5，及展示趋势见图5。

表4 W0=360，α=1时改变β对编制结果的影响

表5 W0=360，α=0时改变β对编制结果的影响

可见，若保持期望工作时长不变，随着非必要劳动时间的权重β增大，编制结果中工作效率会逐渐上升，同时乘务任务数也会呈现增多的趋势。这是由于β的增大表示对非必要劳动时间的重视程度增加，在成本函数中期望工作时长W0不变的情况下，乘务任务数的权重相应减少，受重视的程度逐渐降低。

较特殊的，当β=0时工作效率与乘务任务数都呈现较明显的低谷。这是因为当β=0时，编制过程不再考虑非必要劳动时间的多少，而是仅考虑日计划中乘务任务的数目。因此求解主规划的整数规划的过程仅在尽量使组成日计划的乘务任务数目最少，工作效率的高低对评价结果没有影响。

综合比较以上两组编制结果，可以得到关于α取值的结论：在上述两种情况下，α=0时的工作效率都比α=1时的工作效率高，但在大部分情况下会拥有更多乘务任务数。这是由于一份列车运行计划中的值乘时间总和是固定的，其权重越大，非必要劳动时间权重相对减小，对非必要劳动时间的重视程度降低，导致非必要劳动时间因α=1而增多，工作效率降低，同时乘务任务数也因为工作效率降低而增加。

在实际的工作中，运营企业需要根据运营需要，合理设定对工作效率与乘务任务数的权重，以得到对运营企业而言较为理想的结果。本例中，通过第一组编制结果的对比可以得到令α=0能取得较少的乘务任务数，人工成本在300～420内时编制效率较高；另一方面，β值在1～3时乘务任务数增长的趋势不明显或在一个数目周围不规则波动，并且随着β值的增加工作效率有所提高，因此可以选择α=0、β=3、W0=360为一组合适的参数。

5 结论

本文提出了一种基于列生成算法的乘务计划优化编制方法，将子规划构造为在以乘务段为顶点，可行衔接关系为弧的网络图上的最短路问题；根据实际运营情况通过引入权重综合考虑乘务任务数和工作效率，设计单目标函数，并依此设计了一种基于影子价格选择的标号法，在保证求解质量的同时，能够以较快的速度求出满足现场工作需求的乘务日计划。

案例分析中，通过设定不同的权重系数并与当前现场所使用的乘务日计划的对比，体现了本文提出的乘务计划优化编制方法的优越性。通过调节权重系数，可以做本文提出的方法的灵敏度分析，并为实际工作中应选用何种权重系数组合做出合理的判断。由实例编制结果可知，在其他参数不变的情况下，通过增加人工成本W0可令乘务任务数目呈现减少的趋势，而增加非必要劳动时间权重β则可有效提高日计划的工作效率。

此外，通过比较工作效率与乘务任务数目的变化趋势可以取得较为合理的参数搭配，使编制的日计划更符合运营机构的要求。并且从实例中可发现：随着对使用乘务员数目的重视程度增加，乘务任务日计划中乘务任务数呈现下降的趋势，同时工作效率也在不断降低。当乘务任务数下降趋势变缓或不再减少时，即可获得针对该乘务编制问题较理想的乘务日计划。