Combination of Multiple Ant Colony System and Simulated Annealing for the Multidepot Vehicle-Routing Problem with Time Windows

Abstract

The vehicle-routing problem (VRP) is an important management problem in the field of physical distribution and logistics. In practice, the logistics system usually includes more than one depot, and the start of the service at each customer must be within a given time window. Hence, the multidepot vehicle-routing problem with time windows (MDVRPTW) is an important variant of the VRP. The MDVRPTW is a difficult combinatorial optimization problem due to the many complex constraints involved. The research presented in this paper proposes a multiple ant colony system (MACS) to solve the problem. In addition, two hybrid algorithms, which combine the strengths of MACS and simulated annealing, are developed to improve solution quality. The performance of the proposed algorithms is tested on several benchmark instances and compared with that of other algorithms in the literature. The results indicate that the proposed algorithms are effective in solving the MDVRPTW, and six new best solutions are found.