公交司机排班问题的混合元启发算法研究

针对我国公交企业中司机在1 个工作日内驾驶同一辆车的“人车绑定”管理模式， 提出混合元启发算法求解司机排班问题.首先建立以车辆数为目标的车辆调度模型，获得仅 满足司机休息时间的非可行解；接着迭代地使用局部搜索算子、破坏重建扰动等方法对解进 行调整，使其满足司机工作时间和吃饭时间等约束，并尽可能地降低排班成本；在迭代搜索 过程中记录发现的可行排班链集合，迭代结束后构建集合覆盖问题(SCP)模型对其进行改 进，以获得最佳的司机排班方案.在13 条公交线路案例上进行测试，实验结果验证了本文算 法的有效性.

A Hybrid Metaheuristic Algorithm for the Transit Bus and Driver Scheduling Problem

This paper deals with the bus and driver scheduling problem that arises from most transit companies in China where a driver should drive the same bus in the same day. A hybrid metaheuristic algorithm is proposed for the problem. Firstly, a bus schedule model with minimum number of buses is built and solved as the initial solution, which is an invalid solution just satisfying with the constraint of driver break time. Secondly, the local search operators are literately used to adjust the invalid solution to a feasible solution as well as reducing the solution cost. And then, a ruin and recreate method is introduced to expand the search space to avoid trapping into the local optimum. All the blocks of the feasible solution in the local search are also collected. Finally, a set covering problem (SCP) model tries to select global best solution from the collected historic blocks. The algorithm was tested on 13 real world instances and the results show that the proposed method is effective.