作　　者： (侯彦娥）; (孔云峰）; (党兰学）; (王玉璟）;

机构地区： 河南大学计算机与信息工程学院,开封475004 河南大学黄河中下游数字地理技术教育部重点实验室,开封475004

出　　处： 《计算机科学》 2017年第8期216-224,共9页

摘　　要： 针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。 This paper aimed to deal with the multi-school bus routing problem（SBRP）with different types of school buses.Based on the iterated local search（ILS）,we proposed a metaheuristic algorithm,which employs the neighborhood operators originally designed for pickup and delivery vehicle routing problem with time windows（PDPTW）to improve the route solution.In the local search phase,the algorithm adopts the variable neighborhood descent search（VND）to search neighborhood solutions by the neighborhood operators.Guided by an adjustment strategy based on route segment,these operators adjust bus type as much as possible in order to reduce the cost.Our algorithm accepts some worse neighborhood solutions within the scope of cost deviation to keep the search diversification,and it uses the perturbation method with multiple points shift to avoid trapping in the local optima.The results of benchmark datasets show that the proposed algorithm is effective to solve both the mixed-load SBRP and single-load SBRP.In addition,for the multischool homogeneous SBRP,our algorithm outperforms existing algorithms,such as post-improvement heuristic,simulation annealing and record-to-record travel algorithm.

关 键 词： 多车型校车路径问题 多校 迭代局部搜索 可变邻域下降 车型调整策略