Optimization Algorithms For Heterogeneous School Bus Routing Problem

It is challenging to provide safe and efficient school bus service for compulsory schools and educational authorities. The design of school bus routes plays an important role in bus operations and a reasonable plan can significantly improve the service quality and efficiency. It is closely related to the bus fleet, the bus depots, the geographic distribution of schools and students and the road network. It also depends on the other constraints such as the school opening times and the maximum riding time of students. The school bus routing problem(SBRP) aims to find an optimal route solution with service quality and/or cost reduction objectives. In real-world applications, the SBRP is usually to reduce the fixed and the daily operating costs of buses.While most existing SBRP researches focus on the homogenous-fleet problems, the heterogeneous SBRP(HSBRP) is more common in real-world route planning. In practice, the fleet of school buses usually consists of different types of buses. It is also necessary to use small buses to visit some areas due to the road conditions. In addition, the bus service quality and efficiency could be improved by combining different types of buses, considering that the students are unevenly distributed. However, a few existing construction or heuristic algorithms for the HSBRP have limited optimization performance. These methods also lack flexibility in solving complex problems. Consequently, this dissertation aims to investigate the high-performance metaheuristic algorithms for the general-purpose heterogeneous SBRPs.The research is conducted in the following steps. First, based on the problem description of the HSBRP, the mathematical models for different planning scenarios are formulated according to the problem constraints such as the number and capacity of each bus type, school time windows and the maximum riding time of students. The objective is to minimize the fixed and/or operating costs. The models for some problem instances could be solved by exact methods. The second step is to design a general-purpose HSBRP algorithm framework, which includes basic data structures, common functions, initial solution construction algorithms, local search operators and heuristic strategies. Using the framework, the third step is to implement metaheuristic algorithms for different HSBRPs, such as the fleet size and mix SBRP(FSMSBRP), heterogeneous fixed fleet SBRP(HFSBRP),the multi-school mixed-load HSBRP and the multi-school single-load HSBRP. The performance of all the algorithms is tested and analyzed on a set of SBRP benchmark instances. Finally, a case study of school bus routing is used to demonstrate the feasibility and advantages of the proposed algorithms.The main research results are summarized as follows.(1) An algorithm framework is designed for solving single-school and multi-school HSBRPs. It consists of general data structures, basic functions, construction algorithms for generating initial solutions and local search operators. It also provides the heuristic mechanisms such as the selection of local search operators, the bus type adjustment in local search, the neighborhood solution acceptance rules and search perturbation methods. Based on this framework, various metaheuristic such as iterated local search(ILS), greedy and randomization adaptive procedure(GRASP) and variable neighborhood search(VNS) are proposed. The design and implementation of the metaheuristics indicate that this framework is flexible enough for solving general-purpose HSBRP.(2) For the single-school HSBRP, two metaheuristic algorithms are developed for FSMSBRP and HFSBRP respectively. An improved GRASP is designed for the FSMSBRP. It can be used to solve three FSMSBRP variants with objectives such as total costs, fixed costs and variable costs. The proposed GRASP overcomes the shortcomings of randomly or fixed selection of parameters, and outperforms the existing algorithms significantly. Compared with RRH algorithm, GRASP improves the three FSMSBRP objectives by 5.28%, 4.84% and 7.22% respectively. Compared with the ALBH algorithm, the objective values are also improved by 6.26%, 6.02% and 7.55% respectively. For the HFSBRP, the mathematics model of it is build, and then a multi-start metaheuristic algorithm(HILS) is developed for the first time by hybriding ILS and variable neighborhood descent(VND) with random neighborhood selection. The algorithm is adapted to solve the two variants of HFSBRP with total costs or variable costs. The test results indicate that HILS can find better solution than CPLEX in short time, and it also has the high stability.(3) An ILS metaheuristic algorithm is developed for solving multi-school HSBRP. Since the multi-school problem is similar to the delivery and pickup vehicle routing problem with time windows(PDPTW), an initial solution is improved iteratively by using three PDPTW neighborhood operators: single pair insertion(SPI), swapping pairs between routes(SBR) and within route insertion(WRI). The bus type adjustment is allowed in the three operators to enhance the solution quality. The proposed algorithm is tested on the benchmark instances, and the results show that the algorithm is effective. Compared with RLBH and ALBH algorithms, the total cost obtained by ILS is reduced by 29.01% and 34.84% respectively for the single load HSBRP. For mixed load HSBRP, the total cost is reduced by 28.93% and 34.66% respectively.(4) The proposed algorithms are tested on a real case with 4 schools. The schools, the student stops, the bus depots and the road network in Huishan District of Wuxi City are prepared in ArcGIS. The Single-school and multi-school bus routes are designed by the metaheuristics proposed in this dissertation. The results indicate that planning routes with heterogeneous school buses is more effective than that with homogeneous buses. For single-school problem, the solution obtained by GRASP algorithm is much better than that obtained by the ArcGIS VRP Solver. For multi-school problems, the single load and mixed load solutions can reduce the total costs by 3.20% and 6.62%, compared with the existing route plan.There are two major contributions in this dissertation. First, a general-purpose algorithm framework for heterogeneous school bus routing problems is designed for the first time. Using this framework, the metaheuristic algorithms for single-school SBRP and multi-school HSBRPs with different cost objectives can be flexibly and efficiently implemented. Second, it is also the first time to propose the metaheuristic algorithms for heterogeneous fixed fleet HSBRP and multi-school HSBRP. All the algorithms developed in this dissertation significantly outperform the existing methods in terms of solution quality.