MAX-MIN Ant System and local search for the traveling salesman problem

TLDR

Ant System is a general‑purpose algorithm inspired by ant colony behavior and based on cooperative search for combinatorial optimization. The study introduces MAX‑MIN Ant System, an improved variant of basic Ant System, and applies it to both symmetric and asymmetric traveling salesman problem instances. The method augments Ant System with MAX‑MIN pheromone bounds and integrates local search heuristics to refine tours. Experiments demonstrate that MAX‑MIN Ant System effectively guides local search toward promising regions, yielding high‑quality initial tours and improved performance on TSP instances.

Abstract

Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution of combinatorial optimization problems. We introduce MAX-MIN Ant System, an improved version of basic Ant System, and report our results for its application to symmetric and asymmetric instances of the well known traveling salesman problem. We show how MAX-MIN Ant System can be significantly improved, extending it with local search heuristics. Our results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.