Research On Optimization Of School Bus Routing

The development of technology accelerates the progress of economy, as wellas standard of living, so people attach importance to education more and more, andinvestment for education by the government is increasing year after year. Manyproblems emerge one after another with increase of students and traffic is one ofthem. In addition, with the development of economy, there are more and moresedans and many students go to school by it, which do not only make traffic jamand pollution more serious but also cost a lot of parents' time and energy.At present, school buses are used in many schools to solve above problems,but now vehicle scheduling is accomplished by handwork, distributing of route isso unreasonable that the cost is very high and the runtime is long, etc.Therefore, research on optimization of school bus routing can achieve theaims such as reducing the cost, decreasing students' traveling time, lighteneconomic burden of parents, mitigating traffic jam and lessening environmentpollution. It can bring many economic and social benefits.This paper takes primary school attached to northeast normal university as thecase to optimizing the vehicle routing. Based on the research in theory, it isformulated as a multi-objective combinatorial optimization problem, and four aimsare put forward as follows:(1) Minimize the amount of needed vehicles.(2) Minimize whole runtime of school buses.(3) Minimize total traveling time of students in every stop.(4) Balance load and runtime of every school bus.This is a capacitated VRP with hard time windows. For the case, the studentswho go to school by school buses are numerous and the routes are distributed inevery district of changchun city, the difference of quantity of students in every stopis great. Because of the above characters, there are two differences compared withformer researched problem types as follows:(1) the aims needed to optimize aredifferent;(2) Each stop was allowed to visit by one bus and the demands weresatisfied entirely in the problems had been studied, but in this problem, each stop isvisited by more than one bus that is students in one stop can travel by differentbuses (namely the demand can be divided), which is propitious to take fulladvantage of vehicle's load and reduce the number of vehicles.Algorithms literatures have had can not be used in this problem directly, so anoptimization-based heuristic for its solution is proposed. This algorithm is acombination of heuristic and optimization (the K best solutions of Lawler and theshortest path algorithm of Dijkstra). Then the above aims are optimized with fourphases, numerical results are reported using test data from the school eventually. Ithas shown to be effective with a saving of 19.2% in total pupils'traveling times,and 14.4%in total bus loaded travel times, when comparing to existing routesplanned manually.This method is not only applied to school bus scheduling, but also to routingproblem of enterprise bus or autobus and so on, which has a great practicalsignificance.