钱 程，徐小明，彭飞

(1.合肥工业大学 汽车与交通工程学院，合肥 230009；2.北京电子科技职业学院 汽车工程学院，北京 100176)

在公交运营管理中，运营组织与调度是公交企业工作的核心。公交运营组织和调度的首要任务，是有效管理和合理分配有限的车辆和人力资源，调整供需平衡，争取以最小的人力、物力及财力投入来保障日益增加的客流需求[1]。司机排班问题是公交运营规划的重要组成部分，用于司机的费用大约占整个公交公司运营成本的60%[2]，一个高质量的司机排班计划可以为公交公司节省很多成本。乘务调度问题(CSP)的目标是在满足一系列复杂劳动法规的条件下，合理安排一组乘务人员完成一天内的全部车辆运行任务，公交系统中的乘务调度问题又可称为司机排班问题(DSP)。

司机排班问题自20世纪60年代以来一直受到广泛的关注和研究，班制和用餐约束在司机排班问题中被广泛考虑。在实际的公交系统中，常规班制和早晚班制是两种常见的司机工作班制[3]。在公交司机排班问题中，设置司机用餐休息也有两种常见的方式：一种是在司机达到最大连续工作时间后设置一段长休息作为司机的用餐时间；另一种是更符合人们饮食习惯的“中式用餐”[4]，即设置司机的用餐时间窗，规定司机在用餐时间窗内用餐。

司机排班问题为NP-hard问题，这一点已被许多研究所证实[5]，对于此类问题，通常结合集合覆盖或集合划分模型进行建模[6]。乘务排班问……