Abstract: In practice of school bus route planning,the bus fleet usually consists of a limited number of buses with different capacities,purchase costs and operation costs.However,the heterogeneous fixed fleet school bus routing problem (HFSBRP) has not been well investigated.In this paper,we introduced a mathematical model for HFSBRP and also proposed an iterated local search (ILS) algorithm to optimize the total cost.The ILS is combined with a variable neighborhood descent (VND) algorithm with random neighborhood selection.In local search,the bus type for one or more routes will be adjusted to reduce the costs.Two acceptance rules are used to accept the solution while satisfying the rules.In addition,some worst solutions within the scope of cost deviation are accepted to keep the diversification of the search.Moreover,a perturbation mechanism with multiple points swap or shift is used to avoid local optima.The experimental results demonstrate the correctness and effectiveness of the proposed model.

Key words: Heterogeneous school bus routing problem,Fixed fleet,Iterated local search,Random variable neighborhood search