求解器COPT应用实践丨地铁乘务排班问题如何优化求解

由于地铁运行网日益复杂，传统的人工排班方式已无法满足高标准的运营需求，自动化和智能化的乘务排班成为必然趋势。智能排班作为一个复杂的运筹优化问题，对算法、模型和求解器要求较高，目前国内应用并不普遍，以下根据某一线城市地铁线路的成功实践，为你解析如何基于国产求解器COPT实现智能乘务排班。

地铁乘务排班的痛点分析

一般地铁运营公司进行乘务排班的流程是：根据当前运行图导出车次运行区段和时间等信息表，人工根据这些信息表拆分出乘务轮值表，再根据轮值表编制乘务排班母表，最后以排班母表为基础对乘务组进行轮循分配，形成最终的排班表。整个过程依靠人工编制，主要存在以下三大问题：

排班效率低：乘务排班业务规则复杂，工作量大，人工编制效率很低，至少需要一周时间，人力和时间成本高;

调整难度大：遇到列车故障、乘务员临时请假等突发情况时，很难快速地对排班计划做出调整，影响运营管理效率;

任务分配不均衡：人工排班具有主观局限性，对人的经验依赖性较强，排班不合理会导致任务分配不均衡，排班有失公平，乘务员满意度较低。

基于杉数求解器COPT的智能乘务排班方案

杉数科技为某地铁线路构建的智能乘务排班方案，利用运筹优化技术将乘务排班问题抽象为数学规划问题，通过定制化算法和求解器高效求解优化，在排班效率和效果上都实现了显著提升。方案以地铁运营部门提供的时刻表(即运行图)为基础，综合考虑车次的接车下车时间地点、换乘约束以及班制运营要求，以优化正线值乘人数及乘务人员满意度为目标，编制轮值表。然后基于轮值表，以优化乘务人员之间周/月工作内容的整体均衡性为目标，按照特定的班组转换模式偏好编制排班母表。

排班类问题属于混合整数规划(MILP)问题，决策变量和约束数量大，建模和求解难度大。传统的时空网络模型因存在维度爆炸等计算复杂度限制，求解难度较大，而且需要根据业务逻辑进行算法定制化开发和模型拆解。在该项目中，杉数科技采用组环/组链模型+时空网络模型进行建模，并应用求解器COPT求解【1】，一次性考虑所有约束条件进行全局优化。

1、技术选型与建模思路

大规模公共交通系统的人员排班问题(Crew Scheduling + Crew Rostering)，涉及的决策维度多，约束条件耦合程度高，即使是在最基础的设定下，学界和业界目前也都缺乏高效的求解方法。

由于各类约束之间存在复杂的耦合关系，建模求解过程中需要考虑相互之间的影响，求解难度较大。以用餐相关约束为例，用餐约束与班制和工时息息相关，在设计算法和模型时不能只考虑用餐时间和地点，还要考虑白班和夜班的不同用餐时间限制等约束。因此，如何借助算法来处理这种复杂的耦合关系是智能排班方案需要解决的关键问题之一。

在最近的相关综述论文中【2】，长距离轨道交通的人员排班以集合覆盖问题为原型，并结合列生成的方法为主，城市轨道交通中则更偏向于网络流模型结合启发式算法或拉格朗日松弛等求解技巧。因本项目属于超大规模问题，涉及50余项约束条件，项目算法团队定制化开发了“先轮值，再排班”的业务解耦模型。

图为：轮值表和排班母表模型示意图

轮值表模型中，核心决策为每日值乘任务的拆分与组合，主要考虑换乘规则、班制规则、里程工时上限等业务规则，输出为完成每日值乘任务所需人数及相应工作安排，即轮值任务卡。

排班母表模型中，核心决策为轮值任务的有效均衡分配，主要考虑任务分配的均衡性，输出为轮值任务卡与值乘人员的对应关系，即每位轮值人员每日的任务。

2、轮值表求解优化(Crew Scheduling)

在轮值表优化阶段，杉数科技以优化正线值乘人数为目标，基于时空网络模型结合割平面的方法对轮值表场景进行了定制化的精确求解建模，具体来说，就是将时空网络中一个个离散的任务基于时空连续性和业务规则约束组成一条条任务链。

其中，提高求解效率的核心在于将部分约束条件前置到预处理部分，通过排除大量不可行方案缩小模型规模，并生成割平面使得模型更紧凑。

(1)连接性 - 其中时空连续性和特殊换乘地点、换乘时间等基础业务规则约束可在预处理模块的连接性判断环节中得以保证。

(2)非法任务链(Illegal Sequence) - 任务数上限、连续驾驶时长上限等约束可通过在预处理模块中通过广度优先搜索(BFS)、深度优先搜索(DFS)等方式搜索非法任务链或最小非法任务子链(Minimal Illegal Subsequence)，并以割平面的方式添加到模型中，割平面只由核心决策变量X_ij组成。这种思路与A.E. Roth et al.【3】提出的通过预先搜索最小不可行路径(Minimal Infeasible Path)，来刻画多向肾脏交换图中链/环的长度约束(CCMcP)异曲同工。

(3)非法任务链&合法任务子链 – 实际业务场景中，也存在有些不可行任务链可以是可行的任务子链(如：用餐、出退勤地点相关约束)，故不能完全排除出可行域外。此类场景中，需要在割平面中加入判定头、尾等的相关辅助变量来刻画对应的逻辑关系。

上述方法在不牺牲最优性的前提下，用更多的约束条件换取了更少的决策变量，且添加的割平面往往会使得系数矩阵更稠密，求解过程中需要对应地调整求解器预求解等参数的强度。

项目团队在与业务部门沟通中，也挖掘出一些业务中通用的“潜规则”，从模型的角度考虑，可以理解为牺牲一定的最优性以缩小问题规模并显著提升求解效率。例如，对于出发或到达站台为可换乘且不可出退勤站台的值乘任务，可以通过构建二分图，以换乘时间为权重进行最小权重最大匹配，基于匹配结果进行任务预连接并生成对应便乘任务。

通过设计一系列定制化算法对各项约束进行预处理，然后基于业务逻辑进行建模，再结合求解器COPT进行求解，求解速度明显加快。特别值得一提的是，COPT求解器团队还针对问题本身的特有结构开发了定制化加速模块，打造了更适用于乘务排班的专属求解方案。

3、排班母表求解优化(Crew Rostering)

轮值表优化完成后，乘务团队需要将轮值表中的任务，合理且均衡地分配给每一位司机，即制定排班母表。在制定排班母表时，既要保证轮值表中的每一项任务都有符合驾驶条件的司机执行，又要保证每一位司机有充足的休息时间，在邻近的车站出退勤，按时接受培训，更要均衡每位司机每周工作时长和驾驶里程，甚至要为司机休假或者个人突发状况做好备班准备，问题纷繁复杂。

针对该场景的复杂变量和约束，杉数科技基于业务规则构建了混合整数规划模型，并开发了定制化求解器进行求解。整个建模求解思路如下，首先，梳理可执行性相关约束，将班制约束、出勤地点约束等业务约束前置考虑，有效缩小每个司机可执行任务集合，通过现实的业务约束减小问题规模。随后，模型执行任务初分配(可行性验证)和任务再分配(均衡性调整)两个关键步骤。在任务初分配中，模型智能决策排班母表司机总人数;在任务再分配中，模型对任务进行重新分配，以实现各个司机里程和工作时长的均衡，并输出排班母表。

图为：耦合模型VS分解模型对比

其中模型分解至关重要，以基于班制规则的日期分解为例，将周度模型分解为七个日度模型，并考虑连续日期间的耦合约束，通过分解极大提升求解效率。假设乘务团队采用四班三运转班制，则每位司机的任务以“白班-夜班-早班-休息”的周期循环往复，如图(耦合模型示意图)所示。直接基于该模型进行可行性验证或均衡性调整非常困难，所以将其分解为多个日度模型。如图(分解模型示意图)所示，只考虑周一的任务，并且考虑周日和周二的"夜班-早班"耦合约束，有效降低了问题规模。类似的模型分解在实际求解过程中不一而足。

方案价值：乘务排班更加高效和均衡

智能乘务排班方案帮助该地铁运营公司实现了乘务管理的智能化升级，打破人工排班的局限性，在满足地铁稳定运行的情况下，考虑各项业务规则和人员能力，从全局角度最优化排班计划，合理、均衡分配任务，实现人和车次的最优配置，全面提升了乘务排班的效率和弹性。

图为：任务分配均衡性对比

运营公司在乘务排班时，将更加灵活便捷，遇到高峰期或突发情况时可以快速调整排班方案，提升乘务管理效率。同时,也提升了人员利用率，为地铁运营公司节省了大量人力成本。对于乘务司机而言，方案兼顾运营需求和乘务司机的主观需求进行综合优化，降低了排班的不合理性，提高了任务分配的均衡性，整体乘务司机满意度大幅提升。

杉数求解器COPT的应用价值和优势

国产求解器COPT在本项目中表现出色，给整个优化求解方案带来了多方面助力和提升：

第一，实现快速稳健的优化。COPT求解性能领先，在求解速度上处于国际一流水平，本项目中应用混合整数规划求解器进行求解，求解过程顺畅、稳定、高效。

第二，通过定制化模块提高求解速度和效果。COPT应用灵活，扩展性好，可以根据不同的业务场景进行定制化，相对于常规求解器，针对于乘务排班的定制化求解器在初始解求解速度、分支策略和整体求解效率等方面都更加优秀。

第三，可以规模化复制和应用。基于一条地铁线路的定制化求解能力，可以快速推广到类似场景中去，帮助运营公司快速实现更大范围的优化升级。

第四，国产化技术支撑，COPT求解技术自主可控，可以有效保证系统安全运行。

除了乘务排班，基于求解器COPT的智能决策解决方案目前在列车检修、列车调度、运行图编制等多个轨交场景中都已经开始应用，其正在为轨交系统的全面智能化升级注入新的动力，未来的应用潜力值得期待。

Reference:

[1] D. Ge, Q. Huangfu, Z. Wang, J. Wu and Y. Ye. Cardinal Optimizer (COPT) user guide. https://guide.coap.online/copt/en-doc, 2022.

[2] J. Zhou, X. Xu, J. Long and J. Ding. Integrated optimization approach to metro crew scheduling and rostering. Transportation Research Part C. 123 (2021) 102975

[3] A.E. Roth, T. Sonmez and M.U. Unver. Efficient kidney exchange: coincidence of wants in markets with compatibility-based preferences. American Economic Review. (2007) 97:828–851

更多求解器应用案例，可在CORIDM教学平台了解

CORIDM(全称Center for Operations Research and Intelligent Decision Making)是杉数科技推出的运筹与智能决策的案例教学平台，集成了多个经典运筹学问题以及多个行业多个领域的真实案例，并且提供一站式的Jupyter Notebook编程环境，旨在为教授和学生带来“理论结合实践”的案例教学/学习体验。

● 内嵌Python编程/COPT/运筹优化等基础知识介绍。用户可以在平台中学习各种基础知识，为解决工业界的实际问题做充足的准备;

● 汇聚零售、消费、制造、物流、航空等多个行业的智能决策案例。对于每个案例，平台提供了详细的案例介绍、解决方法和数学模型、实现代码、总结拓展等，提供了充足的学习资源，能够让学习者充分掌握每个案例的内容和思想;

● 提供开箱即用的Jupyter Notebook编程环境。所需的Python第三方包包括COPT求解器已经部署完成，用户不需要自行安装任何软件即可运行代码;