Research On The Vehicle Routing Problem Based On Ant Colony Algorithm

The vehicle routing problem(VRP) is a key link in the process of modern logistics distribution,and it has been widely used in many fields. Therefore, it has attracted much attention from experts and managers of different disciplines. At present, VRP has become a hot research. But how to find an efficient algorithm to get satisfactory global solution in a relatively short time is still the focus of study. This paper mainly expounds from the following several aspects.(1)Introduce detailedly and analyze comparatively the domestic and international VRP issues of the research status and methods, expound the working principle and mathematical model of the basic Ant System algorithm(AS), implement the solution of Traveling Salesman Problem(TSP),summarize the complexity and characteristics of the ant colony algorithm along with the influence of the setting of the important parameters on the performance of the algorithm. However, the main content of this paper is how to transform it into a suitable solution to the VRP problem, which can be solved in two different directions: direct method and transformation method.(2)At first, we propose two improved technologies of ant colony algorithm based on direct method in this paper. The first technology scheme by using the preliminary modified ant colony algorithm firstly gets a feasible VRP solution, then separates this solution into many segments by means of ant colony TSP algorithm to improve current VRP solution. The second technology scheme not only makes a full use of ant colony algorithm, but also uses twice ant colony algorithms. The external ant colony algorithm is only to get a variety of different groups, and the internal ant colony algorithm is to plan a shorter route and guide the ants to walk on this route. After that, the third new improved technology scheme is put forward from the transformation method, which increased mutation operator in the sequential scan algorithm to ensure the VRP solution is still feasible and different groups distance are close. Once configured this way, you can get many more reasonable groups and in each group achieve curb order reoptimization to get optimal solution of the vehicle routing problem in the end.(3)Use matlab on the VRPLIB data set to carry out the simulation test, and record the optimal objective function value and running time on three kinds of improved algorithm,compare and analyze the simulation results, verify and evaluate the rationality and effectiveness of these improvements.