Vol 7 No 1 (2012)
Articles

An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem

Daniel Karapetyan
Simon Fraser University
Published July 26, 2012
Keywords
  • Ant Colony Optimization,
  • Ant Colony System,
  • Generalized Traveling Salesman Problem
How to Cite
Karapetyan, D., & Reihaneh, M. (2012). An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem. Algorithmic Operations Research, 7(1), Pages 22 - 29. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/19330

Abstract

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.