Improved Iterated Local Search Algorithms For Split Demand School Bus Routing Problem

With the development of social economy in China, more and more districts and schools begun to provided school bus service for the primary and secondary students. However, compared to the developed countries, school bus service started late in our country. The operation manner of school bus and bus routing are also in exploration. As an important part in the school bus operation management, reasonable bus route planning can reduce cost and improve the quality of service.The school bus planning problem can be converted to school bus routing problem(SBRP), which is a NP-hard problem in combinational optimization area. In classic SBRP, the students in one bus stops must be served by one bus and this reduce the utilization of school bus. In our country has high population density, and people live in concentrated area. There may be many students waiting for a bus at one bus stop and the number of students may be larger than the bus capacity. The classic SBRP can not applied to this case. The existing research on the split delivery vehicle routing problem has shown that the cost can be reduced by splitting the delivery. Therefore, in this paper, the SBRP is extended to the split demand school bus routing problem(SDSBRP). The optimization objectives are the minimization of the number of school buses required and the total travel distance. In this paper, we proposed an improved iterated local search method to solve SDSBRP.The main work of this paper is as following.(1) The SDVRP and SDSBRP were systematically studied. The SBRP was extended to SDSBRP, and several neighbor search operators used in heuristic algorithm were designed. The effect of neighbor search operators play in our algorithm was analyzed.(2) An improved Iterated local search(ILS) algorithm was proposed. There is little research on SDSBRP and the existing algorithms mainly focus on exact methods and heuristic algorithm. These algorithms cannot obtain higher quality solutions. This paper proposed an improved ILS algorithm for solving SDSBRP. The core of ILS lies in the local search and perturbation, these two parts affect the performance of genetic algorithm.Local search is easily trapped in local optimum which may be far from the optimum, so we introduce simulated annealing(SA). SA has a strong local search ability, so in our improved ILS algorithm we introduced SA in the local search part of ILS. In local searching, the minimization of the number of school bus required is as the first objective. In optimizing the travel distance, we used SA and some worse solutions which has longer distance may also be accepted.For perturbation, the ruin and recreate is introduced as new perturbation mechanism. The ruin and recreate algorithm deletes some routes at random and rebuild the solution destroyed. This can improve the chance of escaping the local optimum.(3) The proposed algorithm can applied to solve the SBRP with or without split demand. The algorithm was tested on benchmark instances and show its effectiveness.