Research On Vehicle Routing Problem With Time Windows Based On Improved Ant Colony Optimization Algorithm

In recent years,the rapid rise of the e-commerce industry has promoted the continuous expansion of the service scope of the logistics industry.As an important part of logistics,the cost of distribution accounts for more than 50% of the total cost of social logistics.It is an effective way to improve the competitiveness of enterprises to use scientific and effective methods to guide and optimize the vehicle distribution path so as to reduce the cost of logistics distribution.As a hot issue of distribution service industry,vehicle routing problem(VRP)has been widely concerned.Traditional vehicle routing problem has been derived a variety of variants in practical applications.Compared with the basic vehicle routing problem with only vehicle load constraints,vehicle routing problem with time windows(VRPTW)can better reflect the actual application situation.Combined with the actual situation of logistics distribution,this paper studies the vehicle routing problem of three types of time windows.According to the characteristics of the three types of time windows,the mathematical models with the vehicle distribution cost as the objective function are established.Vehicle routing problem with time windows belongs to complex combinatorial optimization problem,which has been proved to be NP-hard problem.Based on the study of the basic principle and advantages and disadvantages of ant colony optimization algorithm(ACO),this paper improves ant colony optimization algorithm effectively and uses it to solve the model in this paper.The main contents of this paper are as follows:(1)Construct vehicle routing problem models with different time windows typesBased on the practical application,the vehicle routing problem with hard time window constraint,soft time window constraint and fuzzy time window constraint is studied.Based on the comprehensive analysis of the characteristics of the three types of time windows,the penalty functions of time windows are constructed respectively,and the vehicle routing problem models with the minimum cost of vehicle distribution as the objective function are established respectively.(2)Study on the algorithm for solving vehicle routing problem with time windowsAfter deeply studying the basic principle,advantages and disadvantages of the ant colony optimization algorithm,it is concluded that the algorithm has weak early search ability,easy to fall into local optimization and other defects.In order to solve the vehicle routing problem with time window,the ant colony optimization algorithm is optimized by improving the ant state transition probability formula and pheromone update rules,embedding variable neighborhood local search algorithm and other measures.(3)Verify the effectiveness of the algorithm and solve the modelFirstly,parameter experiments are carried out to determine the optimal parameters of the algorithm.Then,the effectiveness of the proposed algorithm is verified by the example of Solomon standard test set.The solution results of the same example solved by the unimproved ant colony optimization algorithm and improved ant colony optimization algorithm are compared and analyzed,which proves that the algorithm has significant improvement effect.Finally,the algorithm is applied to solve the three problem models established in this paper,and the results are compared and analyzed.