Application Research On Improved Ant Colony Algorithms For Cvrp And Mobile Robot Path Planning

Capacitated Vehicle Routing Problem(CVRP) and the path planning of mobile robot are famous combination and optimization questions. In reality many questions are abstracted to the two problems. There are a lot of solutions to them , which have still many problems such as wasting much time, badly effectively executing. Ant colony algorithms is found in the 1990's, which puts the widespread application into many domains and obtains good results. To compare with other algorithms, it has many typical characters such as positive-feedback, inspiration, synchronization. Two improved ant colony algorithms are proposed for CVRP and the path planning of mobile robot. And a lots of simulation experiences are made. The experiments results show that the proposed improved methods have good performance. The main contents of this thesis are as follows:Four improved methods are proposed for CVRP that are based on ant colony algorithm. Firstly, in the course of initialization ants are put on the distribution center and select their initial client according to the method of route selection of ACS, increasing the possibility of obtaining the optimal path and accelerating convergence of the solution. Secondly, when ants select the next client, the method of ACS, heuristic information of saving and the method of small window which can limit the number of candidate client,are used. They can enhance the correct of selection, accelerate convergence of the solution. Thirdly, the method of local and global dynamic phenomenon update is used, which adjust the distribution of phenomenon according to ants'routes .Fourthly, the 2-opt is used in the course of local search, adding insertion and exchange operation, which enhance the diversity of the search and accelerate convergence of the solution.An improved ant colony algorithm is proposed for robot path planning under a static environment. Grid method is used to establish workspace model of the robot. By simulating the foraging behavior of ant colony, search for optimal path is completed with the way of fold-back iterating between the start and target point for ants, and diversity of the search is enhanced. "Inertia principle" and the strategy of the most pheromone search are used to make ants more sensitive to the optimal path during the searching process. Meanwhile, according to the features of the pheromone strewing in the grids, a new strewing method and updating strategy of pheromone is reconstructed to accelerate convergence of the solution. Validity of the proposed algorithm, with which optimal path can be planned rapidly even in the geographic conditions with obstacles exceedingly complicated, is demonstrated by the simulation results.