校车路径问题的改进迭代局部搜索算法

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

An improved iterated local search algorithm for the school bus routing problem

This paper deals with the school bus routing problem (SBRP) that considers bus stop service time and student travel time constraints. An improved iterated local search (ILS) algorithm with adaptive perturbation mechanism based on large neighborhood search (LNS) was proposed for this problem. In LNS perturbation, a set of parameters with certain selection probability were used to destroy the solution. After certain iterations, the selection probability for each parameter was periodically updated according to its history solution quality. To improve the diversification of ILS algorithm, a worse solution within the scope of deviation was accepted. The experiments on the benchmark dataset are tested. The results show that ILS with adaptive LNS perturbation is more competitive than ILS with commonly used perturbation methods or with general LNS perturbation. Compared with ant colony optimization (ACO), the proposed ILS algorithm is more effective.