Optimization Algoirthms For Large Scale Mixed Load School Bus Routing Problem

Providing school bus service for primary and secondary school students is one of themost important responsibilities of local education authorities. However, balancing the schoolbus safety, service quality and operation efficiency is a challenging task. In practice, areasonable school bus planning can reduce the required number of buses and the overalltraveling mileage so as to save operating costs. The school bus routing problem (SBRP) hasbeen constantly studied since late1960s. Due to the complexity of school bus service and theever-changing of real-world demands, the SBRP for multiple schools is still a class of hardproblems in operations research.SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picksup students from various bus stops and delivers them to their designated schools whilesatisfying various constraints. It is a one of the branches of vehicle routing problem (VRP),well known as the combinatorial optimization problem and NP-Hard problem. When planningschool bus routes for multiple schools in a certain region, allowing mixed load of schoolbuses may significantly reduce the number of required buses and total bus traveling mileage.This paper aims to introduce VRP-based metaheuristic algorithms for solving large scalemixed load SBRP effectively and efficiently, focusing on problem modeling, algorithm designand performance analysis.The research is conducted in the following steps. First, a PDP-based mathematical modelfor mixed load SBRP is defined. In model building, the quality and equity of school busservice are considered as model constraints, and the service efficiency as the objective. Thesecond step is to design a SBRP algorithm framework and the mixed load SBRP algorithmsbased on the general VRP (especially the PDPTW) algorithms. The third step is to test the algorithm performance using SBRP benchmark instances. The algorithm effectiveness isevaluated by combining various neighborhood search strategies and parameter settings.Finally, the SBRP solver is integrated with GIS as a tool of school bus route planning.The main research results in this paper are the design of a general SBRP algorithmframework, the design of a two-stage optimization algorithm, a comprehensive performanceanalysis of the algorithm and a case study.(1) The general SBRP algorithm framework is designed in object oriented architecture. Itconsists of SBRP data structures, neighborhood search operators, common functions, heuristicand metaheuristic VRP algorithms. The metaheuristic algorithms include simulated annealing,variable neighborhood search, and large neighborhood search. Based on this framework,various metaheuristic algorithms for solving SBRP can be constructed flexibly. It provides thecombination of different neighborhood operators, randomized or guided searching strategy,acceptance rules for solution improvement, and setting of other optimization parameters.(2) For the design of two-stage optimization algorithm for mixed load SBRP, therecord-to-record travel (RRT) metaheuristic in first stage aims to minimize the number ofrequired school buses, and the large neighborhood search (LNS) in second stage is to reducethe total traveling distance of school buses. In both two stages, the solution quality isimproved gradually by iterative local searches using PDPTW neighborhood operators: singlepaired insertion (SPI), swapping pairs between routes (SBR) and within route insertion (WRI).Considering the spatial and temporal configuration between schools and student stops, theterm of spatiotemporal ‘distance’ is introduced to reduce the size of neighborhood for eachoperator. The test of a set of16benchmark instances shows that the mixed load SBRPalgorithm based on PDPTW operators outperforms the existing algorithms significantly. Incase of30loops of RRT, the average numbers of required buses are reduced by10.14%for8RSRB instances and by10.61%for8CSCB instances. At the same time, the average total traveling distances are reduced by7.34%and6.30%respectively. In second stage of LNSmetaheuristic, the average distances reduced by10.84%and9.91%respectively. In addition,the spatiotemporal neighborhood search can decrease the average computation time by50%.(3) There are several important findings from the algorithm performance analysis. Forneighborhood search operations, the SPI can reduce the number of routes effectively. Thenumber of routes can’t be reduced by WRI and SBR, but the solution adjustments by WRIand SBR will increase the chance of reducing the number of routes by SPI. Therefore,combination of the three operators can obtain better results than single SPI, and the bestsearch order is SPI, WRI and SBR. The second finding is that the guided search strategy ofselecting a pair of school-student stops on the short paths firstly is more effective than therandomized strategy to to improve the solution. For receiving the improved solution, the rulesof FirstAccceptance and BestAcceptance have no obvious differences in solving large-scaleinstances. In addition, when increasing the number of loops in both RRT and LNSmetaheuristics, there is noticeable opportunity to reduce the number of school buses and totaltraveling mileage. This means that the algorithm may obtain better solution by extending thecomputation time.(4) A tool in GIS is designed for case study. The tool integrates GIS and SBRP solver inArcGIS geoprocessing framework, providing functions such as SBRP data management,model building and problem solving. The school bus planning for8schools in Gongyi City,Henan Province is tested. The solution quality is much better than the results obtained fromthe ArcGIS VRP solver.This paper provides a comprehensive algorithm framework for solving school busrouting problem. It is the first time to propose the PDP-based metaheuristic algorithm formixed load SBRP. Compared with existing algorithms, this algorithm is able to improve thesolution quality remarkably, in terms of the number of required school buses and the total bus traveling distance. The spatiotemporal neighborhood designed for local search can reduce theaverage computation time. The findings from algorithm performance analysis lay a solidfoundation for designing effective SBRP solvers in selection and combination ofneighborhood operators, neighborhood searching strategy, solution acceptance rules,metaheuristics and parameter settings.