Solving the Traveling Salesman Problem Using the IDINFO Algorithm

Yichun Su

doi:10.3390/ijgi14030111

Solving the Traveling Salesman Problem Using the IDINFO Algorithm

2025-03-03

0

OA

AI

DOI：10.3390/ijgi14030111

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

combinatorial optimization problems

weighted mean of vectors algorithm

traveling salesman problem

short-distance delivery

Solving the Traveling Salesman Problem Using the IDINFO Algorithm

Abstract

Journal

Organization