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

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 ve...

Full description

Saved in:
Bibliographic Details
Published in:Transportation research record 2008-01, Vol.2089 (1), p.85-92
Main Authors: Ting, Ching-Jung, Chen, Chia-Ho
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0361-1981
2169-4052
DOI:10.3141/2089-11