A multiple ant colony optimization algorithm for the capacitated location routing problem

The success of a logistics system may depend on the decisions of the depot locations and vehicle routings. The location routing problem (LRP) simultaneously tackles both location and routing decisions to minimize the total system cost. In this paper a multiple ant colony optimization algorithm (MACO) is developed to solve the LRP with capacity constraints (CLRP) on depots and routes. We decompose the CLRP into facility location problem (FLP) and multiple depot vehicle routing problem (MDVRP), where the latter one is treated as a sub problem within the first problem. The MACO algorithm applies a hierarchical ant colony structure that is designed to optimize different subproblems: location selection, customer assignment, and vehicle routing problem, in which the last two are the decisions for the MDVRP. Cooperation between colonies is performed by exchanging information through pheromone updating between the location selection and customer assignment. The proposed algorithm is evaluated on four different sets of benchmark instances and compared with other algorithms from the literature. The computational results indicate that MACO is competitive with other well-known algorithms, being able to obtain numerous new best solutions.