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

文章来源:网络整理编辑:采集侠2022-08-25 09:09

导读:

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

城市地铁作为城市交通的主动脉之一,承载了城市的巨大客流量,运营管理非常复杂。其中,乘务排班是地铁运营管理的关键环节之一,也是乘务管理的起点和难点。地铁交通运载量大,交路复杂多变,运行间隔密,乘务司机面临着巨大、持续、高强度的运输任务,如何合理安排司机的运转班次和值乘方式、实现人员的最优配置,对于保障地铁高效稳定运行非常重要。

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

地铁乘务排班的痛点分析

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

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

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

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

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

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

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

1、技术选型与建模思路

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

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

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

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

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

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

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

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

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

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

本文链接:http://www.soxunwang.com/kjrd/2022/0825/106143.html

声明:
1、此文内容为本网站刊发或转载企业宣传资讯,仅代表作者个人观点,供读者参考。
2、搜讯网所转载的稿件都会明确标注作者和来源,如您不希望被转载请及时与我们联系删除。
3、搜讯网的原创文章,请转载时务必注明文章作者和"来源:搜讯网",不尊重原创的行为搜讯网或将追究责任。
4、本站提供的图文仅供参考,不能作为任何咨询依据,专业问题请咨询专业人士,谨防受骗。

关注搜讯网微信号

扫描加关注!

搜讯网福利发放

最新热点 更多
相关阅读 更多