图源:摄图网
摘要:公交系统在实际运营过程中经常受到车辆故障、交通拥堵以及客流量增加等因素的干扰,造成异常车次的产生,并以延误车次和临时新增车次最为常见。在制定公交车辆调度计划时,预先考虑可能发生的干扰,可以提髙调度计划的鲁棒性,降低恢复正常运营的成本。本文针对公交车辆调度计划的制定问题,考虑延误车次和新增车次两种受扰车次,提出重新分配车次和调整车次发车时间两种恢复策略,建立考虑异常车次的车辆调度模型,以提供鲁棒性较强的车辆调度计划,并设计了一个基于行列成算法的启发式算法进行求解。在求解过程中,原问题被分解为主问题和三个子问题,并分别使用Bellman-Ford算法求初始路线,使用标号法求解修正路线,以及使用禁忌搜索算法提髙求解效率。最后,一系列的对比实验表明,本文提出的模型可以提供更具鲁棒性的公交车辆调度计划方案,能够减少干扰场景下车次的调整次数,对减轻公交调度管理人员的工作复杂性具有帮助作用。
关键词:公交车辆调度;异常车次;恢复策略;行列生成
一、研究背景与意义
城市道路公共交通系统是城市公共交通的重要组成部分,包括公共汽车系统、无轨电车系统、出租汽车等。其中,公交车以其灵活机动、成本较低和运力较高等优点成为了城市公共交通中的重要组成部分。2021年6月的《国务院关于建设现代综合交通运输体系有关工作情况》的报告中提到,截至2019 年,我国的公交运营线路长度达148万公里,公交专用道超过1.6万公里。公交系统的快速发展极大的缓解了人们的出行压力,但公交运营线路的飞速增长也对管理者带来了更大的挑战。公交公司的管理人员需要科学、高效的公交车辆管理调度计划,以辅助其管理公交线路的日常运营。
在日常运营中,异常车次的频繁产生给公交车辆的管理调度带来了巨大的困难与挑战。城市交通系统常常受到天气事件、车辆事故、交通拥挤或者客流量骤增等不确定因素的干扰,从而导致了异常车次的产生。根据对数据的分析和企业实际操作经验发现,部分企业所运营的公交线路有6%的车次存在延误时常高20%以上的情况,而在面临暴雨等恶劣天气时,通常会考虑临时新增车次。本文就比较常见异常车次,即延误车次与为了满足突发性出行需求而产生的临时新增车次为研究对象。异常车次的产生常常干扰到公交车辆的正常运行计划,使得管理者需要在较短时间内对原本制定的公交车调度计划进行临时性的调整,以尽可能减少异常车次的影响,这大大增加了公交日常运营管理工作的不确定性与复杂性,提高了公交调度部门的人力成本。
二、主要内容
本文拟从计划的视角研究考虑异常车次的公交车辆调度问题(vehicle scheduling problem with dis¬ruption, VSP-D)。具体来说,即在制定公交车辆调度计划时,将预期可能出现的异常车次以随机干扰场景(包含车次发车时间、起始场站等信息)的形式考虑入模型之中,并在各场景下考虑了公交车辆可能的线路调整方案,以评价原始计划线路的鲁棒性。从实践角度出发,本文所提出的模型可以为公交管理部门制定车辆调度计划提供决策支持,使得调度计划兼具经济效益和鲁棒性。此外,异常车次的引入大增加了模型的复杂性和求解难度,本文设计了基于行列生成的启发式算法(row-and-column gen¬eration based heuristic, R&CG-H), 以满足大规模案例的计算需要。最后,算例实验表明,基于本文模型所制定的调度计划可以在不必或是较小幅度地调整原调度计划的情况下保证公交系统的正常运营, 在不增加经济成本的前提下减弱了异常车次的消极影响,降低了管理人员的工作量与复杂度,对提高公交管理部门调度计划制定决策的鲁棒性具有指导意义。
2.1 基于线路的考虑异常车次的车辆调度模型
2.2 基于行列生成的启发式算法流程图
本文的创新之处总结如下:
1)在计划层面考虑异常车次的车辆调度问题,提出了一个考虑异常车次的车辆调度模型(VSP-D)。该模型以总成本,即最小化运营成本和期望的恢复策略的成本之和为目标函数,旨在完成公交车辆车次运营要求的前提下增强调度计划的鲁棒性。
2)考虑了两种异常车次并提出了两种恢复策略。常见的两种受扰车次拖延车次和新增车次被包含 在模型中,覆盖了多数干扰因素造成的扰动场景,采用了重新分配车次和调整车次发车时间两种恢复策略,能够解决大部分的再调度问题。
3)提出了基于行列成算法的启发式框架求解该混合整数规划问题。将该问题分解为主问题和三个子问题,子问题采取了包含并行算法、标号法、禁忌搜索算法在内多种加速技巧加快问题的求解效率。
4)基于湖南省某市的实际公交运营状况生成了不同规模的算例。测试算例证明了该算法的可行性和有效性,与求解器与和基于领域搜索的启发式算法相比,提高了求解效率并保证了解的质量。
三、算例测试与结果分析
本小节所有的算例均根据湖南省某市的公交状况随机生成,主要包括发车时刻表、场站和干扰场景的生成。
3.1 小规模算例分析
本小节通过观察小规模算例的实验结果分析本文提出的算法的可行性,部分小规模算例可以直接 调用CPLEX求解器进行求解,求解时间限制为5000秒;基于行列生成的启发式算法的中止条件为求解时间达到1000秒或者连续一定迭代次数(根据算例规模设置为5-10代)后目标函数的值不再改进。
根据小规模算例的实验结果可以发现,对于小规模算例,本文提出的基于行列生成的启发式算法可以在给定时间内获得质量较高的解,而CPLEX仅仅给出了部分算例的最优解。从运行时间的角度来看,算例的运行时间随着车次数量和场景数量的增加而增加,且在使用CPLEX可以求出可行解的算例中,CPLEX的求解时间大约是算法运行时间的4-8倍,这表明该算法可以在较短时间内给岀一个高质量的解。
此外,本部分针对公交车辆调度计划的鲁棒性进行了分析检验。在制定修正线路时,如果该修正线路包含了不属于其对应初始线路的车次时,那么将加入惩罚成本,以避免或者减少修正线路对初始线路的调整,增强初始线路在干扰场景下的鲁棒性。为了验证在初始调度计划下线路鲁棒性的提升,本部分将该惩罚成本忽略,仅考虑在干扰场景下修正线路的可行性,此时考虑一场车次的车辆调度模型(VSP-D) 退化为了 一般的车辆调度模型(VSP)。
根据对VSP-D和VSP的求解结果进行了对比,车次平均调整次数代表了所有场景下将初始线路中未包含的车次调整入对应修正线路的平均次数,该部分对应的惩罚成本亦在VSP模型求解之后加入其总成本之中。从实验结果中可以看出,当干扰场景较多时,VSP-D结果下的车次平均调整次数远远低于忽略了惩罚成本的VSP模型的结果,而其总成本也因能够较好地减少干扰场景下的恢复成本而保持与VSP相近或是更低的水平。这些结果表明,在面临干扰场景时,本文所提出的VSP-D模型能够制定更稳定的初始调度计划,并能够在对初始线路较小幅度的调整下处理异常车次,降低了公交调度人员制定调整线路工作的复杂性与不确定性,具有更好的鲁棒性。
3.2 大规模算例分析
小规模算例的实验结果通过与CPLEX求解器的对比,证明了基于行列生成算法的启发式框架求解小规模问题的高效性。本节进一步探究该算法对大规模算例的适用程度,大规模算例的生成过程类似于小规模算例且更接近于湖南某市真实的公交运营状况,一个基于领域搜索(Local-search)的启发式算法被设计出来作为对照,以验证基于行列生成的启发式算法(R&CG-H)的高效性。
通过对实验结果的观察可以发现,本文所设计的基于行列生成的启发式算法(R&CG-H)可以在相近,甚至更少的时间内获得优于邻域搜索(Local-search)算法的解。此外,通过不同数量场景下的算例的观察,例如当干扰场景数量从3提升到6时,基于行列生成的启发式算法与邻域搜索算法的 “Gap”也随之扩大,说明了基于行列生成的启发式算法能够更好地求解多干扰场景数量的案例。最后,通过对比基于行列生成的启发式算法下性松弛解与整数解的目标函数,可以看到二者的差异并不明显。这说明了线性松弛的限制主问题是原整数规划限制主问题问题的一个比较接近的近似,侧面印证了基于行列生成的启发式算法在该问题上的适用性。
四、结论与展望
本文研究了考虑延误车次和临时新增车次两种异常车次情况的公交车辆调度问题,并将预期的异常车次以干扰场景的形式,基于随机规划理论建立了一个车辆调度模型。该模型的决策包括初始线路 计划的制定和各干扰场景下线路的修正两个部分,两种恢复策略:车次分配调整和车次发车时间调整被考虑入线路的修正之中。由于干扰场景和修正线路的引入增加了模型的复杂性,本文提出了一种基于行列生成的启发式算法以求解该问题。原问题被分解成限制主问题和三个定价子问题,并通过最短路标号法、禁忌搜索等算法求解以进行迭代求解。本文根据湖南省某市公交线路的数据,生成一系 列不同规模的算例。最后,在算法效率的测试实验中,通过与CPLEX求解器和一个基于邻域搜索的启发式算法的对比,本文所提出的基于行列生成的启发式算法能够在给定时间内获得质量更高的解。关于不同干扰场景数量和算例规模下的实验反映了异常车次对公交车辆调度计划的总成本的影响。此外,本文将所提出模型与未考虑异常车次的车辆调度模型进行了对比,算例实验表明:本文所提出的考虑异常车次的模型能够给岀更具鲁棒性的调度计划,能够在对初始线路较小幅度的调整下处理异常车次,降低了修正线路制定计划的复杂性,减少了公交调度部门的工作量和人力成本,对提高公交管理部门调度计划制定决策的鲁棒性具有指导意义。
本文的局限在于仅考虑了新增与延误两种异常车次,然而公交车管理部门在实际运营中还面临着车辆故障、人员临时调整等不确定因素对车辆调度计划的影响。另外,新插入的车次也可能出现更灵活的管理方式,如只执行完成部分线路,而不是全部线路。因此,考虑更加复杂的现实场景和设计相应的模型和高效的算法是未来一个值得研究的方向。
本文摘编自《系统工程理论与实践》第43卷第3期论文《考虑异常车次的公交车辆调度计划问题研究》(点击题目链接全文);
作者:于昕曜1,2, 博士研究生,研究方向:城市交通管理;朱宁1, 博士,教授,研究方向:交通,物流与设施管理;马延明1;贺正冰3, 博士,教授,研究方向:智能交通系统,交通大数据分析,交通流理论
1. 天津大学 管理与经济学部, 天津 300072;
2. 天津大学 复杂管理系统实验室, 天津 300072;
3. 北京工业大学 城市交通学院, 北京 100020