A matheuristic algorithm for the school bus routing problem
研究校车路径问题，提出结合迭代局部搜索和整数线性规划的数学启发式算法，在112个测试实例中19个优于现有最优解，适用于校车调度优化。
This paper addresses a variant of the school bus routing problem, which involves decisions related to the selection of bus stops from a set of predefined candidate locations, the assignment of students to stops, and the routing of buses. The objective consists in minimizing the total routing cost for picking up students at the bus stops and delivering them to a single school, satisfying the vehicle capacity and the maximum walking distance for students to reach the stops. To solve the problem, we propose a matheuristic algorithm that combines iterated local search (ILS) with an exact procedure based on integer linear programming (ILP). In particular, the ILS procedure makes use of several neighborhoods and auxiliary data structures to efficiently explore the solution search space, whereas the ILP approach attempts to optimally combine the most promising routes found during the search. The proposed algorithm was tested on 112 benchmark instances and it was shown to be capable of providing high-quality solutions, 19 of which were better than the best ones from the literature.