School Bus Routing Problem Meta Heuristic Algorithm Design Integration With GIS

Providing safe and efficient school bus service for primary and secondary school students has becomea new and urgent task in China in recent years. However, planning school bus routes is a difficult problemin the operation and management study. Anefficiency school bus routes planning will not only reduce thenumber of required buses, but also can shorten the school bus total traveling distance. The final object is tosaving the cost of school bus operations services. This paper attempts to establish a mathematical model ofthe school bus routing problem (SBRP), designingthe Meta-Heuristic Algorithm to optimize the object, andintegrating the algorithm in the GISenvironmentto provide software tools for the SBRP.School Bus Routing Problem essentially belongs to the category of Vehicle Routing Problem (VRP),so we design the SBRP model based on the VRP model. Consider the situation that the depot for school busis different from the school, we choose theOpen VRPtoestablish the SBRP model. The model subject toseveral constrains, such as the total travel distance of the school buses, the capacity of the school bus, thestudents longest travel time restrictions and so on. The following steps illustrate the algorithm: modeling,initial solution, using the VRP neighborhood swapping operator under theSimulateAnnealing framework,programming the Meta-Heuristic algorithm in C++environment. In order to verify the computationalefficiency of the algorithm, we use our algorithmand the VRP tool in ArcGIS Network Analysis Moduletosolve the same problem and compare the optimization results.After implementing the algorithm, we design theSBRP tools in the GIS. We use ArcGIS10software tomanage theSBRP data include the school, student’spickup station, transportation networks, and othergeographic data. The tools based on the Geoprocessing framework, where using Python programminglanguage to transfer the parameters, to establish SBRP modeland tovisualize theoptimized results. A junior high school is served astest case for the SBRP toolbox.The experimental results showed that:It is feasible to use the Simulate Annealing Meta-Heuristic algorithm to solve the SBRP. Usingmultiple initial solutions with the Simulated Annealing algorithm is more efficiency than the ArcGIS VRPalgorithm with the Tabu algorithm comparing the quality of the solution. In this article the SA basedalgorithm has simple data structure, less memory cost. With the help of the ArcGIS’s network analysisfunctions calculated the OD CostMatrix, our algorithm can be used in the practical problems. The toolboxprovidesplanners an interface to input SBRP data. After setting the data to corresponding parameters,planners can quickly find the optimal solution of the arrangement of school buses and having a visualizedoutput solution.