一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。