Exploring Trade-offs in Parallel Beam-ACO

The Traveling Salesman Problem is a conceptually simple problem that is computationally difficult due to the size of the search space, which grows factorially with the number of cities. Beam-ACO is an Ant Colony Optimization heuristic that combines classical ACO with beam search. Beam-ACO is quite effective at finding high quality approximate solutions but it is more computationally demanding than the more classical ACO algorithms. In this work we propose a parallel version of Beam-ACO based on work-stealing. Our parallel Beam-ACO algorithm runs both the ant search and beam evaluation and pruning in parallel. Our experiments verify both that Beam-ACO is indeed one of the most effective ACO metaheuristics and that our parallel Beam-ACO is faster than more traditional parallelization schemes such as multi-colony or ant parallel.

Automated summary

The Traveling Salesman Problem is a conceptually simple yet computationally difficult problem due to the factorial growth of the search space. Beam-ACO combines classical ACO with beam search to find high quality approximate solutions effectively, although it is more computationally demanding. The parallel Beam-ACO proposed in this study, based on work-stealing, proves to be faster than traditional parallelization schemes like multi-colony or ant parallel while maintaining effectiveness.