摘要
公交系统在实际运营过程中经常受到车辆故障、交通拥堵以及客流量增加等因素的干扰,造成异常车次的产生,并以延误车次和临时新增车次最为常见.在制定公交车辆调度计划时,预先考虑可能发生的干扰,可以提高调度计划的鲁棒性,降低恢复正常运营的成本.本文针对公交车辆调度计划的制定问题,考虑延误车次和新增车次两种受扰车次,提出重新分配车次和调整车次发车时间两种恢复策略,建立考虑异常车次的车辆调度模型,以提供鲁棒性较强的车辆调度计划,并设计了一个基于行列生成算法的启发式算法进行求解.在求解过程中,原问题被分解为主问题和三个子问题,并分别使用Bellman-Ford算法求解初始线路、使用标号法求解修正线路,以及使用禁忌搜索算法提高求解效率.最后,一系列的对比实验表明,本文提出的模型可以提供更具鲁棒性的公交车辆调度计划方案,能够减少干扰场景下车次的调整次数,对减轻公交调度管理人员的工作复杂性具有帮助作用.
Bus system in the actual operation often suffers vehicle breakdowns,traffic jams and excessive passenger demands,which causes disruptions,i.e.,delays or extra trips.When making a bus scheduling plan,considering the possible disruptions in advance can enhance the robustness of bus scheduling plan and reduce the cost of rescheduling.In view of the vehicle scheduling problem,we proposed two recovery methods including reassigning some trips and adjusting the start times of trips to handle these disruptions.Furthermore,we propose a vehicle scheduling model with disruptions for a robust scheduling plan,and design a row-and-column generation based heuristic algorithm for solving.During the solving process,we decompose the problem into the master problem and three sub-problems.The three sub-problems are solved by Bellman-Ford algorithm for the original routes,labeling method for the modified routes,and tabu search algorithm for the efficiency improvement,respectively.Finally,a series of comparative experiments show that the model proposed in this paper can provide a more robust bus scheduling plan and reduce the expected number of trip adjustments in disruptions,which reduce the workload of scheduling managers.
作者
于昕曜
朱宁
马延明
贺正冰
YU Xinyao;ZHU Ning;MA Yanming;HE Zhengbing(College of Management and Economics,Tianjin University,Tianjin 300072,China;Laboratory of Computation and Analytics of Complex Management Systems(CACMS),Tianjin University,Tianjin 300072,China;College of Metropolitan Transportation,Beijing University of Technology,Beijing 100020,China)
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2023年第3期910-928,共19页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(71971154,72122015)。
关键词
公交车辆调度
异常车次
恢复策略
行列生成
bus scheduling
disruptions
recovery methods
column-and-row generation
