在我国当前各大城市的轨道交通运营管理中，列车运行图已经实现软件的自动编制，而乘务计划作为列车运行图的具体执行，目前主要由技术人员手工编制，手工编制耗费时间长，难以灵活应对运行图的调整和突发状况，从而影响到城市轨道交通的服务水平，计算机自动编制乘务计划成为必然的趋势。不同规模的城市轨道交通线路，乘务计划的编制难度与编制效率也有所区别，本文针对编制难度较大的大规模乘务排班计划进行优化研究。 本文梳理了不同交通方式乘务排班计划的研究成果，总结了城市轨道交通排班计划的编制流程，以乘务班次数目最少为目标，构建了基于集合分割模型和集合覆盖模型的优化模型与算法，通过案例研究证明了算法的有效性。本文主要的研究内容如下： （1）本文基于0-1整数规划模型和列生成算法，构建满足用餐时间、休息时间、工作时间、连续值乘时间约束和乘务片段的全覆盖约束的城市轨道交通乘务排班计划模型。基于一个可行的排班方案构造初始限制主问题，并且通过建立网络图模型，将列生成算法的定价子问题转化为网络图中带资源约束的最短路问题。提出了考虑复杂约束的改进的邻接矩阵构建方法，采用Floyed算法求得网络的最短路径集合。在求解具有最小检验数的新班次时，提出了基于工作效率和工作时长综合惩罚的优化规则，以提高新班次集合的质量。最后利用整数规划模型，从列生成算法生成的新班次集合中选择部分班次，构成最终的排班方案。 （2）以成都地铁1号线的乘务排班计划编制为例，将本文的模型求解结果与手工编制的乘务计划进行对比，同时，本文针对集合分割模型和集合覆盖模型，以及两种不同的乘务作业段生成方式，分析比较不同组合场景下的四种排班模型在求解过程中的差异性，并分别编制排班计划，从排班目标、工作时间、值乘时间、接续时间、工作效率五个方面对结果进行评价分析。计算结果表明，本文模型求得的排班方案在编制效率、班次数量、乘务员工作效率、完成相同值乘任务所需的总工作时间等方面都优于手工编制的排班方案；集合覆盖模型比集合分割模型具有更多的优化空间，可以得到理论上的更优排班方案；在大规模的乘务排班计划中，乘务作业段的完全枚举会增加算法的复杂度，降低求解效率，而采用没有乘务片段重叠的乘务作业段能够简化问题，在较短时间内获得更好的排班方案。
NETL
