Abstract: In school bus route planning for middle and elementary schools,the total cost of school bus service may be reduced if the travel demands of each bus stop can be split and served by several buses.This paper dealt with the split demand school bus routing problem (SDSBRP).Compared with the split delivery vehicle routing problem (SDVRP),the students’ maximum riding time should be considered in SDSBRP.Moreover,the objectives of SDSBRP are minimizing the total number of buses and the total traveling distance.Thus,the methods and strategies for solving classic SDVRP cannot be applied to SDSBRP directly.This paper,for the first time,analyzed the solution properties of SDSBRP,introduced a mathematic formulation for bi-objective SDSBRP,and proposed a metaheuristic algorithm for it.In the algorithm,an initial feasible solution is generated by constructive heuristic.Then,the solution is improved iteratively by neighborhood operators either with or without demand splitting.In addition,a new acceptance criterion and a ruin and recreate mechanism are used to improve the diversity of solutions.For avoiding local optimum,some worsening neighborhood solutions with longer distance can be accepted with a certain probability according to the simulated annealing rule.The efficiency of the proposed algorithm is benchmarked and confirmed by extensive computational experiments.The savings generated from splitting demands are also discussed.

Key words: School bus routing problem,Split deliveries,Metaheuristic algorithm,Simulated annealing