Improved Ant Colony Optimization For Solving Multi Objective Vehicle Routing Problem

With the development of social economy in our country, school bus service for the primary and secondary school students to become education departments and schools faces new problems. School bus route planning is an important part in the school bus operation management, but the path planning involved in the school, student, fleet and transportation network, is an extremely difficult task. Is closely related to the school bus route planning of the school bus routing problem(SBRP) are of satisfying all constraint conditions under the premise of transportation service for students, to seek the optimal bus route scheme, the students from the site by bus to the school, as part of the service quality goals and the operational efficiency of the school bus.For more than an area school bus route planning problem, usually single school SBRP will SBRP decomposition and school bus scheduling problem(SBSP) to find the solution, respectively. Based on the single school SBRP and SBSP mathematical model is established on the basis of the improved ant colony optimization(ACO) algorithm respectively, and use the benchmark case data sets to test performance of the algorithm. Mainly finished the following work:(1) single school SBRP and SBSP mathematical model is established.Because the SBRP belongs to the category of vehicle routing problem(VRP), based on single school SBRP open VRP integer linear programming mathematics model is established. SBSP mixed plastic programming mathematical model is established.(2) in view of the single, each school SBRP and SBSP ACS algorithm and MMAS algorithm is designed.According to the characteristics of single SBRP school, and students in the school bus capacity to time constraints, will reduce the number of paths as the first goal, to reduce the total length of path for the second goal. Drawn up in accordance with the optimization goal, and emphatically discusses the using improved ACS algorithm for the school bus route constructors, associated with the optimization target of pheromone update strategy and local search path improvement; This article will list the school SBRP generated each path into virtual site, converts SBSP to the vehicle routing problem with time Windows(VRPTW), at the same time set up in order to reduce the number of vehicles as the main target simultaneously to reduce the total mileage of the vehicle as the optimization goal. On the basis of the optimization goal, in the MMAS and local search strategy, on the basis of design for SBSP improved MMAS.(3) using the benchmark case data sets, ACS is tested and analyzed the performance of the algorithm and MMAS algorithm.Using the results of the improved ACS to solve SBRP compared with can accurate algorithm results show that the can get the optimal path in the number of cases, improved ACS algorithm can also get the same number of paths, and aimed at mass case can only obtain the feasible solution, the ACS algorithm in solving path number and calculation efficiency has obvious advantages; Using the results of the improved MMAS solving SBSP compared with 41 reports the results of the literature shows that the Park Heuristic can obtain the optimal bus number of cases, improved MMAS algorithm can obtain the same bus number; And in view of the Park Heuristic cannot obtain the optimal bus number of cases, improved MMAS algorithm has advantages in solving the bus number.(4) the school bus route optimization case study.Will improve the ACS algorithm, improved MMAS algorithm, under the framework of ArcGIS Geoprossing, through the Python language, algorithm and the integration of GIS platform. Using data of henan gongyi city junior high school, the school bus route optimization case study.In this paper, the main research conclusions are as follows:(1) in this study for SBRP open VRP integer linear programming mathematics model is established to evaluate, through actual case studies, showed that the model in the actual application has a strong practical, accord with the reality; For SBSP mixed plastic programming mathematical model is established to solve, the experiments show that this model can express SBSP very good.(2) using the improved single school SBRP ACS algorithm is feasible, in the design process of the algorithm, based on the characteristics of multi-objective combinatorial optimization, using two phase structure, at the same time to join point insertion and two exchange such as local search strategy, results and can use the results of the precise algorithm has certain advantages, shows that this algorithm has better performance, more press close to practical problems;(3) with the improved MMAS algorithm is effective, in the design process of the algorithm, using the maximum minimum pheromone strategy, pheromone update strategy associated with the optimization goal, at the same time introduce point insertion and two exchange such as local search strategy, the experimental results compared with the literature reported the results of the 41 has certain advantages, show that the algorithm in solving multi-objective combinatorial optimization problems has the stronger performance, has better practical application value.(4) under the framework of ArcGIS Geoprocessing, using the Python scripting language, has realized the algorithm and the integration of GIS platform, good played a GIS platform in the powerful features of the spatial data management and spatial visualization, but also for the school bus management solution, provides the theoretical and practical basis.