Mathurin SOH ; Baudoin Nguimeya Tsofack ; Clémentin Tayou Djamegni - A Multi Ant Colony Optimization Approach For The Traveling Salesman Problem

arima:6752 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 12 juillet 2021, Volume 34 - Numéro spécial CARI 2020 - 2021 - https://doi.org/10.46298/arima.6752
A Multi Ant Colony Optimization Approach For The Traveling Salesman ProblemArticle

Auteurs : Mathurin SOH ; Baudoin Nguimeya Tsofack 1; Clémentin Tayou Djamegni 1

  • 1 Unité de Recherche en Informatique Fondamentale, Ingénierie et Applications [Dschang]

In this paper, we propose a new approach to solving the Traveling Salesman Problem (TSP), for which no exact algorithm is known that allows to find a solution in polynomial time. The proposed approach is based on optimization by ants. It puts several colonies in competition for improved solutions (in execution time and solution quality) to large TSP instances, and allows to efficiently explore the range of possible solutions. The results of our experiments show that the approach leads to better results compared to other heuristics from the literature, especially in terms of the quality of solutions obtained and execution time.


Volume : Volume 34 - Numéro spécial CARI 2020 - 2021
Publié le : 12 juillet 2021
Accepté le : 15 janvier 2021
Soumis le : 2 septembre 2020
Mots-clés : Ants,Colony,Heuristic,Multi-colony,Traveling Salesman Problem,Ants,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]

Statistiques de consultation

Cette page a été consultée 382 fois.
Le PDF de cet article a été téléchargé 378 fois.