Ant Colony Algorithm And Its Application In The Vehicle Routing Problem Research

As the intensifying of market competition in the world, logistics has become an important mean to enhance the core and market competitiveness.In all costs,transport costs account for a large proportion.Through the design of routes,with meeting the service demands in the same time, the vehicle routing problem will minimize the total costs. Based on the capacity or type of vehicles, there are various types of vehicle routing problem, in this thesis, two issues were discussed: the multi-depots vehicle routing problem with time windows and the vehicle routing problem with simultaneous pick-up and delivery and time windows.VRP has been proved to be NP-hard(Non-deterministic Polynomial), most of its algorithms concentrated on the heuristic algorithm, ant algorithm was emerged in recent years. In this thesis, both the mathematical model and the ant algorithm of the two problems are given.This thesis mainly includes the next contents :1.To the question of ant colony algorithm easy to get into local optimum,this thesis propesed two improvement inculding the adjustment of initial search and the exchange of pheromone. Expriments on the benchmark showed that the resultswere better and the target of iterations required for less.2.The mathematical model of MDVRPTW was presented,Combining with the holistic method,the algorithm looked a number of customs as a virtual node,each search selected a real node from the virtual as a start depot, and with the Nearest Neighbor algorithm by Solomon, the ant colony algrithm was presented.3.For VRPSDPTW, a variable was introduced to solve the problem of the vehicles'capacity.A heuristic function including the remaining capacity and the time windows was given.With this,the ant colony optimization algorithm and the mathematical model was presented.4.C++ programs for the above two issues was presented and Simulational experiments were done on the benchemark problem from VRP web. The experimental results show that the algorithm proposed in this thesis is better,and the actual significance is strong,the computation time required is also reasonable.