基于列生成启发式的单线电动公交车与司机整合调度优化

Column Generation-based Heuristic Approach for Electric Bus and Driver Scheduling on Single Bus Lines

在考虑电动公交车里程约束与司机连续工作时间和总工作时间约束的基础上,研究单条公交线路的电动公交车与司机整合调度问题,即将给定时刻表车次分配给电动公交车和司机,同时,生成车辆运营计划和司机排班计划,设计基于列生成启发式方法求解提出的整合调度问题。列生成方法用于生成线性松弛最优解,将整个问题分解为一个主问题和两个定价子问题。其中,主问题从可行车辆行车路径集合和司机车次链集合中选择最优的司机车次链和电动公交车行车路径,覆盖所有车次,并保证车辆运营计划产生的空驶弧都被司机排班计划覆盖;定价子问题描述两个基于时空网络的资源约束最短路问题,分别用于生成可行的车辆路径和司机车次链,并设计深浅算法得到整数可行解。使用合肥市3条公交线路随机生成算例检验提出算法的有效性。

This paper investigates the integrated electric buses and drivers scheduling problem for single bus lines.The trips are assigned to both electric buses and drivers to generate vehicle utilization plan and driver scheduling plan,which considers the range anxiety of electric bus and the constraints of driver’s continuous working hours and total working time.The procedure ensures that all trips are covered by vehicle utilization plan and driver schedule plan and the deadhead trip generated by vehicle utilization plan are also covered by driver schedule plan.The column generation based heuristic algorithm is designed to solve the problem,which can be decomposed into a master problem and two pricing subproblems.The master problem determines driver schedules and electric bus routes from the feasible vehicle routes set and driver schedules set and ensure that all trips and deadhead trips generated by vehicle utilization are covered by electric buses and drivers.The pricing subproblem is described as two shortest path problems with resource constraints based on time-space networks to generate feasible vehicle routes and driver schedules.Then the pure diving heuristic approach is used to obtain the integer solution.Three random bus routes in Hefei city are used as examples to test the effectiveness of the proposed algorithm.