Research On Single School Bus Routing Problems Based On Improved Ant Colony Algorithm

Providing school bus service for primary and secondary school students is not only the reality that the national government departments promote the compulsory Education,but also a challenging task faced by the Ministry of education.In practice,a reasonable school bus planning can reduce the required number of buses and the overall traveling mileage,improve the satisfaction so as to save operating costs,save costs and improve resource utilization.The single school bus routing problem(SBRP)has been constantly studied.Due to the complexity of school bus service and the ever-changing of real-world demands,numerous problems brought about by the SBRP for multiple schools still need to be dealt with.SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints.It is one of the branches of vehicle routing problem(VRP),well known as the combinatorial optimization problem and NP-Hard problem.The main research in this thesis is the school bus routing problem at home and abroad,especially the single school bus routing problem and the shortage of research.The main research work is as follows:(1)In order to solve the single school bus route problem,it establishes a mixed integer programming model based on multi-objective optimization by analyzing the constraint conditions and the optimization objectives.And it adds the traffic congestion factor to the real situation based on the basic ant colony algorithm.Then the two-stage optimization algorithm for single SBRP is designed: the first phase is dividing the sites into a number of smaller areas,which will be the key part of narrowing the search space;the second phase is using the ant colony algorithm to carry out route arrangement.In fact,the second stage is builds on the first stage.Finally it applies MATLAB software to stimulate to optimize the school bus route.(2)The thesis analyzes the two-stage optimization algorithm.And then it analyzes the sensitivity by changing parameters of algorithm,including the number of cycles,the number of ants,expected stimulating factor and traffic congestion.Through these analyses,this algorithm is verified to be feasible and stable.(3)A tool in MATLAB is designed for case study.The school bus planning for the NO.1 High school of Dalian is tested.The solution quality is much better than the results obtained from the solver of others.This paper provides a two-stage algorithm for solving school bus routing problem.Compared with existing algorithms,this algorithm remarkably improves the solution quality.The findings from algorithm performance analysis lay a solid foundation for designing effective SBRP solvers.