The Generalized Traveling Salesman Problem solved with Ant Algorithms

Abstract

A well known N P-hard problem called the Generalized Traveling Salesman Problem (GTSP) is considered. In GTSP the nodes of a complete undirected graph are partitioned into clusters. The objective is to find a minimum cost tour passing through exactly one node from each cluster. An exact exponential time algorithm and an effective meta-heuristic algorithm for the problem are presented. The meta-heuristic proposed is a modified Ant Colony System (ACS) algorithm called Reinforcing Ant Colony System (RACS) which introduces new correction rules in the ACS algorithm. Computational results are reported for many standard test problems. The proposed algorithm is competitive with the other already proposed heuristics for the GTSP in both solution quality and computational time.

indexed in Scopus, ORCID

Cited by in corpus (9)

• Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem
• Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem
• Robot Path Planning by Traveling Salesman Problem with Circle Neighborhood: modeling, algorithm, and applications
• Towards Social Autonomous Vehicles: Efficient Collision Avoidance Scheme Using Richardson's Arms Race Model
• An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem
• Relating complexities for the reflexive study of complex systems
• A Carbon Aware Ant Colony System (CAACS)
• Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms
• Traveling salesman problem across dense cities