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

在考虑电动公交车里程约束与司机连续工作时间和总工作时间约束的基础上,研究单条公交线路的电动公交车与司机整合调度问题,即将给定时刻表车次分配给电动公交车和司机,同时,生成车辆运营计划和司机排班计划,设计基于列生成启发式方法求解提出的整合调度问题.列生成方法用于生成线性松弛最优解,将整个问题分解为一个主问题和两个定价子问题...

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

This paper investigates the integrated electric buses and drivers scheduling problem for single bus lines. Thetrips 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 totalworking time. The procedure ensures that all trips are covered by vehicle utilization plan and driver schedule plan andthe deadhead trip generated by vehicle utilization plan are also covered by driver schedule plan. The column generationbased heuristic algorithm is designed to solve the problem, which can be decomposed into a master problem and twopricing subproblems. The master problem determines driver schedules and electric bus routes from the feasible vehicleroutes set and driver schedules set and ensure that all trips and deadhead trips generated by vehicle utilization arecovered by electric buses and drivers. The pricing subproblem is described as two shortest path problems with resourceconstraints based on time-space networks to generate feasible vehicle routes and driver schedules. Then the pure divingheuristic approach is used to obtain the integer solution. Three random bus routes in Hefei city are used as examples totest the effectiveness of the proposed algorithm.