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

Today, the logistics industry is developing rapidly, and the process of logistics distribution is more complex, in which the ratio of transportation cost and total cost has more than 50%. Improving the efficiency of distribution vehicle scheduling and reduce transportation cost while satisfying different needs of customers are not only have certain research value in theory, but also has a certain significance in practical application. Firstly the logistics distribution business processes and VRP were introduced in detail. An improved hybrid ant colony algorithm was proposed through the summary of previous research results and deep analysis of the advantages and disadvantages of ant colony algorithm and bacterial foraging algorithm. The main research work is as follows:(1) Through the description of VRPTW, this paper established the mathematical model of VRPTW, and increased the two constraint conditions with respect to the VRP in the model. Firstly, distribution vehicles start from the distribution center, they must return to distribution center after serving client; Secondly, each customer in the distribution task must be finished by a car with only one time service. The vehicles must serve customer within a specified time window. If early arrived, vehicles must wait.(2) Since ant colony algorithm is easy to fall into the local optimal solution of this problem, the pheromone update method was improved. When the iteration ended, all the ants constructed a solution and the pheromone matrix was updated. In order to enhance the hormone concentration of the arc belong to the optimal solution, using three different best solutions to update the pheromone.(3) Since the ant colony algorithm is prone to premature convergence and stagnation, the local search strategy was improved. Varying neighborhood search can dynamically change the size of the neighborhood space. Only accepting the best local solution until the local optimal during the local search, which improved the ability of IHACO to get rid of the local optimal and avoided computing a large number of redundant nodes. It is beneficial to improve searching speed of the algorithm, which provides the possibility to solve the large scale optimization problem quickly and effectively.(4) In the system simulation experiment, using the C++ to carry on the simulation for VRPTW through the system requirement and the system analysis. C1-01, which was one of the international common benchmark problems, was adopted as experiment data. Comparing the obtained experiment results with the best results, some solutions were improved or approached to the best result. This shows that the improved hybrid ant colony algorithm proposed in this paper is effective in solving the VRPTW.