论文研究校车路径问题的改进迭代局部搜索算法.pdf

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题（SBRP），提出一种改进迭代局部搜索（ILS）算法以提升求解质量。该算法使用大规模邻域搜索（LNS）算法作为扰动算子；在解的破坏过程中，设计一组解的破坏因子并赋予一定的选择概率，每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率，进而调整解的破坏程度。为提升ILS解的多样性，算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试，测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升；与蚁群算法的比较结果进一步验证了改进算法的有效性。