Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem

Abu Saleh Bin Shahadat, M. A. H. Akhand and Md Abdus Samad Kamal
Additional contact information
Abu Saleh Bin Shahadat: Department of Computer Science and Engineering, Khulna University of Engineering & Technology, Khulna 9203, Bangladesh
M. A. H. Akhand: Department of Computer Science and Engineering, Khulna University of Engineering & Technology, Khulna 9203, Bangladesh
Md Abdus Samad Kamal: Graduate School of Science and Technology, Gunma University, Kiryu 376-8515, Japan

Mathematics, 2022, vol. 10, issue 14, 1-24

Abstract: Ant Colony Optimization (ACO) is a practical and well-studied bio-inspired algorithm to generate feasible solutions for combinatorial optimization problems such as the Traveling Salesman Problem (TSP). ACO is inspired by the foraging behavior of ants, where an ant selects the next city to visit according to the pheromone on the trail and the visibility heuristic (inverse of distance). ACO assigns higher heuristic desirability to the nearest city without considering the issue of returning to the initial city or starting point once all the cities are visited. This study proposes an improved ACO-based method, called ACO with Adaptive Visibility (ACOAV), which intelligently adopts a generalized formula of the visibility heuristic associated with the final destination city. ACOAV uses a new distance metric that includes proximity and eventual destination to select the next city. Including the destination in the metric reduces the tour cost because such adaptation helps to avoid using longer links while returning to the starting city. In addition, partial updates of individual solutions and 3-Opt local search operations are incorporated in the proposed ACOAV. ACOAV is evaluated on a suite of 35 benchmark TSP instances and rigorously compared with ACO. ACOAV generates better solutions for TSPs than ACO, while taking less computational time; such twofold achievements indicate the proficiency of the individual adoption techniques in ACOAV, especially in AV and partial solution update. The performance of ACOAV is also compared with the other ten state-of-the-art bio-inspired methods, including several ACO-based methods. From these evaluations, ACOAV is found as the best one for 29 TSP instances out of 35 instances; among those, optimal solutions have been achieved in 22 instances. Moreover, statistical tests comparing the performance revealed the significance of the proposed ACOAV over the considered bio-inspired methods.

Keywords: ant colony optimization; adaptive visibility; traveling salesman problem; partial solution update; 3-opt local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/14/2448/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/14/2448/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:14:p:2448-:d:862089

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().