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

Authors

  • Daniel Karapetyan Simon Fraser University
  • Mohammad Reihaneh

Keywords:

Ant Colony Optimization, Ant Colony System, Generalized Traveling Salesman Problem

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.

Downloads

Published

2012-07-26

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

Issue

Vol. 7 No. 1 (2012)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.