Abstract—The Multi-Depot Vehicle Routing Problem

(MDVRP) is a generalization of SDVRP, in which multiple vehicles start from multiple depots and return to their original depots at the end of their assigned tours. The MDVRP is NP-hard, therefore, the development of heuristic algorithms for this problem class is of primary interest. This paper solves Multi-Depot Vehicle Routing Problem with Cellular Ant Algorithm which is a new optimization method for solving real problems by using both the evolutionary rule of cellular, graph theory and the characteristics of ant colony optimization. The simulation experiment shows that the Cellular Ant Algorithm is feasible and effective for the MDVRP. The clarity and simplicity of the Cellular Ant Algorithm is greatly enhanced to ant colony optimization