A parallel improved ant colony optimization for multi-depot vehicle routing problem

Abstract

This paper presents a method for solving multi-depot vehicle routing problem (MDVRP). First, a virtual central depot is added to transfer MDVRP to the multi-depot vehicle routing problem with the virtual central depot (V-MDVRP), which is similar to a vehicle routing problem (VRP) with the virtual central depot as the origin. An improved ant colony optimization with coarse-grain parallel strategy, ant-weight strategy and mutation operation, is presented for the V-MDVRP. The computational results for 23 benchmark problems are reported and compared to those of other ant colony optimizations.