基于集合覆盖理论的公交线路驾驶员排班优化方法

A Method of Optimizing Work Schedule of Bus Drivers Based on Set Covering Theory

为解决公交驾驶员调度优化问题,提出了一种基于人员成本最小化的公交线路驾驶员排班优化模型。在运营公交车辆最少的前提下,以单条公交线路的车次链为研究对象,考虑车辆运营任务、换班时间、劳动规则要求等约束,借助集合覆盖理论进行数学建模,并提出了一种基于启发式的0-1整数规划算法进行模型求解。最后,结合济南市公交调查的实际数据,以MATLAB为平台,实现了上述算法,求出公交驾驶员的排班方案。试验结果表明:与其他算法相比,该算法可减少驾驶员候车时间消耗,降低班次总工作时间和人员成本,进而降低公交公司运营成本;该算法在提高驾驶员工作效率的基础上,有效保障了驾驶员的工作时间,为公交线路驾驶员排班组合优化问题提供了合理方案。

To optimize the work schedule of bus drivers,a work schedule optimization model of bus route based on minimizing labor cost is proposed. In the premise of minimizing the number of operating buses,taking the bus schedule chain of single bus line as the research subject,considering the constraints of vehicle operation task,shift time,labor rules,etc.,the mathematic model is constructed by set covering theory,and a 0- 1 integer programming algorithm based on heuristic method is designed to solve the model. Finally,according to the real investigation data of Jinan public transit,the above algorithm is realized and the schedule scheme is worked out based on the platform of MATLAB. The experiment result shows that（ 1）compared with other algorithms,this algorithm can reduce the drivers＇ waiting consumption and reduce the total work time and personnel cost to achieve the purpose of reducing the bus company operating costs;（ 2）the method can protect the drivers＇ working hours based on improving the efficiency,which provided a reasonable solution for optimizing work schedule of bus drivers.