A Hybrid Metaheuristic Algorithm for the School Bus Routing Problem with Multi-School Planning Scenarios

摘要

In the practice of multi-school bus route planning,the characteristics of the bus fleet and the operation modesof buses have produced a variety of bus planning scenarios.In recent years, many methods have been used to arrangethe routes of school buses for the school bus routing problem(SBRP) with a specific planning scenario. However, it is still achallenging task to develop a general-purpose algorithm thatcan effectively apply to the bus route planning for a variety ofbus planning scenarios. This paper tries to develop a hybriditerated local search (ILS) metaheuristic algorithm for SBRPwith multiple planning scenarios, which including homogenousor heterogeneous fleets, single load or mixed load operationmodes. Within the framework of ILS, a variety of neighborhoodstructures are used to improve the initial solution as well as theroutes generated in the process of local search are recorded.For heterogeneous SBRP, the fleet adjustment strategy basedon route segments is also applied. In addition, the perturbationmechanism and the acceptance of worse solutions within acertain deviation range are adopted to enhance the diversityof solutions. Finally, the local best solution is further promotedby the set partitioning procedure (SP), which is modeled bythe history routes in the local search process. The experimentresults prove that the proposed algorithm is effective and it alsooutperforms the existing algorithms for multi-school SBRP.