摘要
arXiv:2505.02485v1 类别: cross
摘要: 公交司机排班问题(BDSP)是一个组合优化问题,目标是设计班次以覆盖预先安排的巴士旅游。目标不仅考虑运营成本,还考虑司机的满意程度。由于严格的法律法规和集体协议,该问题受到了严格的约束。本文的目标是提供最先进的精确和混合解决方案方法,以提供不同规模实例的高质量解决方案。本文提出了对一种精确方法(分支定价,B&P)以及一种大型邻域搜索(LNS)框架的研究,该框架在修复阶段使用B&P或列生成(CG)来解决BDSP。文中还提出并评估了一种新的B&P和LNS更深的集成方法,存储LNS子问题生成的列,用于其他子问题的修复,或者找到更好的全局解。文章对解决方案方法的多个组成部分及其影响进行了详细分析,包括对B&P子问题的一般改进,该子问题是高维资源受限最短路径问题(RCSPP),以及LNS的组成部分。评估结果显示,我们的方法为所有规模的实例提供了新的最先进的结果,包括小型实例的精确解,以及中期实例与已知下限的低差距。结论:我们发现B&P在小型实例中提供了最好的结果,而LNS与CG紧密结合可以为较大规模的实例提供高质量的解决方案,进一步改进了仅将CG作为黑箱使用的LNS。提出的解决方案方法具有普遍性,也可以应用于其他规则集和相关优化问题。