Solving the Traveling Salesman Problem Using the IDINFO Algorithm

Abstract

The Traveling Salesman Problem (TSP) is a classical discrete combinatorial optimization problem that is widely applied in various domains, including robotics, transportation, networking, etc. Although existing studies have provided extensive discussions of the TSP, the issues of improving convergence and optimization capability are still open. In this study, we aim to address this issue by proposing a new algorithm named IDINFO (Improved version of the discretized INFO). The proposed IDINFO is an extension of the INFO (weighted mean of vectors) algorithm in discrete space with optimized searching strategies. It applies the multi-strategy search and a threshold-based 2-opt and 3-opt local search to improve the local searching ability and avoid the issue of local optima of the discretized INFO. We use the TSPLIB library to estimate the performance of the IDINFO for the TSP. Our algorithm outperforms the existing representative algorithms (e.g., PSM, GWO, DSMO, DJAYA, AGA, CNO_PSO, Neural-3-OPT, and LIH) when tested against multiple benchmark sets. Its effectiveness was also verified in the real world in solving the TSP in short-distance delivery.