Hybrid Ant Colony Optimization Algorithm For Two Echelon Vehicle Routing Problem

NP problem is common in the nature, for combinatorial explosion of solution space is met in the search for objective solutions to these problems, that solving the large scale NP problems has become one of bottleneck in the field of computer science, artificial intelligence, etc. On the other way, the vehicle routing problem which is proposed in this article is one of typical NP problem. There are many cases in real life that can be abstracted as this problem, such as vehicle scheduling in logistics distribution, bus routing, mail or newspaper delivery, airline or railway timetabling, waste collection and school bus routing. Therefore, it makes sense to study heuristics for solving the vehicle routing problem from the aspect of both theory and practice. At present, the exact optimization method based on discovering the optimal solution is powerless in solving large-scale NP problem, but the heuristic algorithm based on discovering acceptable conditions (such as time) become a powerful tool to solve such problem, and the latter one also become a hot topic of applications and research in scientific community.As one swarm intelligence heuristic algorithm, ant colony optimization algorithm own the characteristic of positive feedback which can ensure find a good solution quickly, small coupling which suitable for distributed computing and can escape premature convergence, and the heuristic search based on greedy which can help to find feasible solution at an early stage. So it is widely used in solving NP problems, and it also have more complete theoretical basic.Several heuristics and their applications in some variants of the vehicle routing problem are studied in this thesis. Hybrid heuristic ant colony optimization algorithm are proposed by combing heuristic algorithm which is good at discovering the optimal solution region and neighborhood search algorithm which is good at discovering better solution in a region, and applied to the capacitated vehicle routing problem and the two echelon vehicle routing problem which is proposed recently in academia. The proposed algorithm is tested in different size benchmark, the result show that our methods have a good performance in some cases and it prove the validity of our algorithm.There are several achievements in our research:First, we improve the ant colony optimition algorithm according to the characteristic of vehicle routing problem, and the experimental results show our method has better performance. Second, we propose one new local search algorithm, called multiple neighborhood descent, base on variable neighborhood search, and it has better search efficiency. Third, we propose the more efficiency threshold-based local search algorithm in two echelon vehicle routing problem. Fourth, combine greedy algorithm, ant colony algorithm and variety of neighborhood search, we propose an hybrid aco algorithm based on threshold for solving the two echelon vehicle routing problem. It takes advantage of the speediness of traditional heuristic algorithm, the search diversity of aco and the strong local searching capability. The experimental results show our method improve the quality of solution and the convergence.