Approche Heuristique Multi Colonie Des
Fourmis Pour La Résolution du Problème de
Voyageur de Commerce

Mathurin Soh, Baudouin Nguimeya Tsofack, Clémentin Tayou Djamegni
Research Unit in Fundamental Informatics, Engineering and Applications
University of Dschang
P.O. Box 67 Dschang, Cameroon

RÉSUMÉ. Dans ce papier, nous proposons une nouvelle approche de solution approchée au problème de voyageur de commerce (Travelling Salesman Problem in english), dont on ne connait pas d’algorithme exact permettant de trouver une solution en un temps polynomial. L’approche proposée est basée sur l’optimisation par des fourmis. Elle met plusieurs colonies en compétition pour la
recherche des solutions améliorées (en temps d’exécution et en qualité de la solution) aux instances de TSP de grandes tailles, et permet d’explorer plus efficacement les plages de solutions possibles.
Les résultats issus de nos expériences nous montrent, que l’approche permet de déterminer des résultats meilleurs par rapport aux autres heuristiques (ACS-LKH, et AG-LKH), issues de la littérature, notamment en qualité des solutions obtenues et en temps d’exécution.
ABSTRACT. In this paper, we propose a new approach to solving the Travelling 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.

MOTS-CLÉS : Colonie, Fourmis, Heuristique Multi-colonie, Problème du Voyageur de Commerce

KEYWORDS : Ants, Colony, Heuristic, Multi-colony, Travelling Salesman Problem

Video short presentation

Authors said: The Short and extended videos of our presentation have too big sizes
to be attached here. Its have been deposited on Drive.

You can download  them at the following links:

pres_final.trec
<https://drive.google.com/file/d/1m_GuT4n6UrEAEXtEJenMOnMQ4jKHtH5Q/view?usp=drive_web>

 resume_final.trec
<https://drive.google.com/file/d/1jozIMCNRF3wh_uD4UUSKWwddpej5BiRg/view?usp=drive_web>