Hybrid Black Widow Optimization and Variable Neighborhood Descent Algorithm for Traveling Salesman Problem

Abstract

Local search algorithms in general are better than population-based algorithms in the terms of exploitation capability in finding more local regions in the search space which provide more ability to explore search space in finding global regions. Black widow optimization (BWO) algorithm is one of the best population-based algorithms which was proposed in 2020 to solve engineering optimization problems. However, this algorithm has a limitation in the exploitation of search space and reactivate a search when stagnation occurs during the algorithm run. Thus, deep search and effectively exploring the search space are not possible during the algorithm run. To overcome these drawbacks, this study proposes two modifications to the BWO algorithm. The first modification is the integration of variable neighborhood descent used to enhance the exploitation process in finding more local regions in the neighborhood during the algorithm run. The second modification focuses on the reactive search process by integrating a new convergence indicator for the algorithm during the algorithm run and online reactive search process. Two benchmark datasets were used to evaluate the proposed modification. The minimum tour distance provided by each algorithm has been used as the performance metric in determining the credibility of the hybrid BWO algorithm and results have been compared with best-known algorithms include African buffalo optimization (ABO), ant colony optimization (ACO), artificial bee colony (ABC), particle swarm optimization (PSO) and a hybrid algorithm consisting of harmony search. particle swarm and ACO (HPSACO). The hybrid BWO algorithm has produced better minimum tour distance compared to ABO, ACO, ABC, PSO and HPSACO algorithms which demonstrate that the hybrid BWO can be applied to solve several optimization problems including vehicle routing problem, classification and clustering.