| Vehicle routing problem (VRP) is a typical combinatorial optimization problem, which is a simplified form of various complex problems. Search space of VRP increases along with the increase of customers and constraint condition. It will take a long time to search the best result from a huge space. So researchers hope to adopt a method, which can shorten the solving time and obtain an approximate result with high precision, to solve this problem.Ant algorithm is a new type of swarm intelligent algorithm. It takes inspiration from the observations of ant colonies foraging behavior that ants can find the shortest paths between food sources and their nests. It is simple, common, robust, excellent in self-adjusting, easy to expand and suitable for parallel process, etc. Solving VRP with the help of ant algorithm is of practical importance. This paper adopts ant algorithm to solve vehicle routing problem. The main work is as follows:In chapter 1, based on summarizing relative references, we summarize the origin, progress, research, application and practicality of vehicle routing problem; clarify the background, reason and significance of the research; point out the research field in this thesis.In chapter 2, we introduce the basic principle, applied domain, current researches and development of ant algorithm; analyze its characteristics and theories; discuss its mathematic model, improved method and important techniques.In chapter 3, we describe the mathematics model of VRP; analyze all constraint conditions of the problem; summarize some methods for solving vehicle routing problem and their characteristics.In chapter 4, we design and realize an improved algorithm based on simple ant algorithm to solve vehicle routing problem; analyze and improve the transition rule, pheromone update formula, ending condition and adjusting parameter. Through the work done in the research, better results can be obtained. In chapter 5, we do experiments on the algorithm designed in this thesis; analyze and compare the results of experiments with those of other papers; thereby verify its feasibility and validity.In chapter 6, we point out main researcher work and innovation of the thesis; analyze the shortcomings of research on vehicle routing problem and look forward the research orientation in the future. |
