Title: Multi-start constructive heuristic through descriptive statistical metrics: the Dhouib-Matrix-4 metaheuristic

Authors: Souhail Dhouib

Addresses: OLID Laboratory, Department of Industrial Management, Higher Institute of Industrial Management, University of Sfax, Sfax, Tunisia

Abstract: In this paper, we design and develop a new metaheuristic named Dhouib-Matrix-4 (DM4). This method is based on a multi-start structure, where in each start a diversification phase is ensured by a constructive heuristic entitled Dhouib-Matrix-TSP1 (DM-TSP1) and an intensification phase is guaranteed by a novel local search method named far-to-near (FtN). Several descriptive statistical metrics (range, mode, standard deviation, etc.) are used in the heuristic DM-TSP1 in order to explore different realisable solutions. Respectively, these realisable solutions are exploited as starting points by the FtN method using several perturbation techniques (insertion, exchange and 2opt). The performance of the proposed method DM4 is tested on the travelling salesman problem using the well-known TSP-LIB benchmark instances with integer and real distances. Experimental results demonstrate that our approach DM4 is very competitive compared to the last developed metaheuristics.

Keywords: operational research; combinatorial optimisation; optimisation; travelling salesman problem; TSP; metaheuristic; heuristic; Dhouib-Matrix; computer science; artificial intelligence.

DOI: 10.1504/IJOR.2024.138926

International Journal of Operational Research, 2024 Vol.50 No.2, pp.246 - 265

Received: 15 Jun 2021
Accepted: 30 Oct 2021
Published online: 04 Jun 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article