Ant Colony Algorithm For Multiple-depot Vehicle Routing Problem

With the development of modern business, logistic distribution, taken as"the third Profit resource"is getting increasingly important in playing role of constructing country economy. For the core role of the logistic distribution, the research of the vehicle routing problem (VRP) has the very important significance. In nowadays, the big logistic companies not only have one depot but for the distributed depots in large area, So multiple-depot vehicle routing problem (MDVRP), will become a new important branch of vehicle routing problem. As NP-hard problem, the MDVRP can't be resolved to achieve the perfect outcome. On the basis of building the model of MDVRP,this paper studies to solve the problem with ant colony algorithm.Two types of ant colony algorithm for multiple-depot vehicle routing problem are studied in this paper. First, the algorithm for multiple-depot vehicle routing problem with shortest total distance is studied. The paper introduced a new method for solving MDVRP. Through improving Split algorithm, the method of vehicle arrangement can be got. And the network optimize is used to appoint depot. Then the step of ant colony algorithm for solving MDVRP is got. At last, computational instances are given. Second, the algorithm for multiple-depot vehicle routing problem with shortest finish time (FTMDVRP) is studied. Through dynamic programming and network optimize, FTMDVRP is changed into the problem of finding the optimal customer arrangement. Then the step of mutation ant colony algorithm for solving FTMDVRP is got. At last, computational instances are given to prove the validity of our method.