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

Abstract: 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 multi-school homogeneous SBRP,our algorithm outperforms existing algorithms,such as post-improvement heuristic,simulation annealing and record-to-record travel algorithm.

Key words: Heterogeneous school bus routing problem,Multi-school,Iterated local search,Variable neighborhood descent,Bus type adjustment strategy