摘要
在考虑电动公交车里程约束与司机连续工作时间和总工作时间约束的基础上,研究单条公交线路的电动公交车与司机整合调度问题,即将给定时刻表车次分配给电动公交车和司机,同时,生成车辆运营计划和司机排班计划,设计基于列生成启发式方法求解提出的整合调度问题。列生成方法用于生成线性松弛最优解,将整个问题分解为一个主问题和两个定价子问题。其中,主问题从可行车辆行车路径集合和司机车次链集合中选择最优的司机车次链和电动公交车行车路径,覆盖所有车次,并保证车辆运营计划产生的空驶弧都被司机排班计划覆盖;定价子问题描述两个基于时空网络的资源约束最短路问题,分别用于生成可行的车辆路径和司机车次链,并设计深浅算法得到整数可行解。使用合肥市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.
作者
刘昊翔
吴啊峰
龙建成
周珏
LIU Hao-xiang;WU A-feng;LONG Jian-cheng;ZHOU Jue(School of Automotive and Transportation Engineering,Hefei University of Technology,Hefei 230009,China;Anhui Province Key Laboratory of Industry Safety and Emergency Technology,Hefei University of Technology,Hefei 230009,China)
出处
《交通运输系统工程与信息》
EI
CSCD
北大核心
2021年第4期211-220,共10页
Journal of Transportation Systems Engineering and Information Technology
基金
国家自然科学基金(71801067,71925001)
中央高校基本科研业务费专项资金(JZ2020HGTB0026)。
关键词
城市交通
整合调度
列生成算法
电动公交车
时空网络
资源约束最短路
urban traffic
integrated scheduling
column generation
electric bus
time-space network
constrained shortest path