陈霁岩，潘寒川，刘志钢，吴 强，赵 磊

（1.上海工程技术大学 城市轨道交通学院，上海 201600；2.上海地铁第二运营有限公司，上海 200063；3.上海地铁第二运营有限公司 质量安全部，上海 200063）

0 引言

乘务计划是城市轨道交通运营中的重要环节，主要解决轨道交通乘务员的值乘问题。国内多数城市轨道交通的乘务计划由各线路乘务部门编制完成，消耗时间长，变更难度大。乘务计划分为乘务排班计划与乘务轮转计划，其中乘务排班计划根据给定的列车运行图，将运行线根据线路条件与乘务制度进行分割与重组，从而得到可行的任务号集合；乘务轮转计划则是在当期各个运行图的乘务排班计划编制完毕后，根据列车运行图属性(工作日、节假日、延长图等)按照一定的规则使得乘务员轮流执行任务。乘务排班计划作为乘务计划的第一步，其编制质量对整个乘务计划编制结果有直接的影响。

近年来，乘务排班计划编制优化在国内外引起学者广泛的研究，Michael等[1]应用图论解决城市轨道交通车底运用和乘务计划中的每个子问题，不同于以往完成编制运行图后再编制乘务计划，而是同时进行运行图与乘务计划编制，后计算实例证明比现实际使用更低。根据香港轻轨乘务排班计划的特点，Chu等[2]将乘务排班计划分为2个阶段进行研究，依次采用最短路算法、对称匹配及改进的遗传算法进行求解。Elizondo等[3]在对城市轨道交通乘务计划建模时，采用人工智能领域的方法来表示状态空间，分别使用基于网络图的贪心搜索和禁忌搜索算法来解决问题，最后通过数据进行验证。……