Article ID: | iaor2006791 |
Country: | United Kingdom |
Volume: | 32 |
Issue: | 6 |
Start Page Number: | 1565 |
End Page Number: | 1591 |
Publication Date: | Jun 2005 |
Journal: | Computers and Operations Research |
Authors: | Blum Christian |
Keywords: | heuristics |
Ant colony optimization (ACO) is a metaheuristic approach to tackle hard combinatorial optimization problems. The basic component of ACO is a probabilistic solution construction mechanism. Due to its constructive nature, ACO can be regarded as a tree search method. Based on this observation, we hybridize the solution construction mechanism of ACO with beam search, which is a well-known tree search method. We call this approach Beam-ACO. The usefulness of Beam-ACO is demonstrated by its application to open shop scheduling (OSS). We experimentally show that Beam-ACO is a state-of-the-art method for OSS by comparing the obtained results to the best available methods on a wide range of benchmark instances.