Mathurin Soh ; Baudoin Nguimeya Tsofack ; Clémentin Tayou Djamegni - A Hybrid Algorithm Based on Multi-colony Ant Optimization and Lin-Kernighan for solving the Traveling Salesman Problem

arima:8660 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, October 28, 2023, Volume 35 - Special issue Data Intelligibilty, Business Intelligence and Semantic Web - 2022 - https://doi.org/10.46298/arima.8660
A Hybrid Algorithm Based on Multi-colony Ant Optimization and Lin-Kernighan for solving the Traveling Salesman ProblemArticle

Authors: Mathurin Soh 1; Baudoin Nguimeya Tsofack ; Clémentin Tayou Djamegni 2

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

In this article, a hybrid heuristic algorithm is proposed to solve the Traveling Salesman Problem (TSP). This algorithm combines two main metaheuristics: optimization of multi-colony ant colonies (MACO) and Lin-Kernighan-Helsgaun (LKH). The proposed hybrid approach (MACO-LKH) is a so-called insertion and relay hybridization. It brings two major innovations: The first consists in replacing the static visibility function used in the MACO heuristic by the dynamic visibility function used in LKH. This has the consequence of avoiding long paths and favoring the choice of the shortest paths more quickly. Hence the term insertion hybridization. The second innovation consists in modifying the pheromone update strategy of MACO by that of the dynamic λ-opt mechanisms of LKH in order to optimize the solutions generated and save in execution time, hence the relay hybridization. The significance of the hybridization, is examined and validated on benchmark instances including small, medium, and large instance problems taken from the TSPlib library. The results are compared to four other state-of-the-art metaheuristic approaches. It results in that they are significantly outperformed by the proposed algorithm in terms of the quality of solutions obtained and execution time.


Volume: Volume 35 - Special issue Data Intelligibilty, Business Intelligence and Semantic Web - 2022
Published on: October 28, 2023
Accepted on: September 29, 2022
Submitted on: November 4, 2021
Keywords: Hybridization,multi ant colony,Traveling Salesman Problem,Heuristic,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]

Consultation statistics

This page has been seen 107 times.
This article's PDF has been downloaded 116 times.