Solving the Traveling Salesman Problem Using the IDINFO Algorithm
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 convergenc...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2220-9964/14/3/111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849342974217945088 |
|---|---|
| author | Yichun Su Yunbo Ran Zhao Yan Yunfei Zhang Xue Yang |
| author_facet | Yichun Su Yunbo Ran Zhao Yan Yunfei Zhang Xue Yang |
| author_sort | Yichun Su |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3b68f8dc1f564e4b8af2ed1af1c6edfd |
| institution | Kabale University |
| issn | 2220-9964 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj-art-3b68f8dc1f564e4b8af2ed1af1c6edfd2025-08-20T03:43:11ZengMDPI AGISPRS International Journal of Geo-Information2220-99642025-03-0114311110.3390/ijgi14030111Solving the Traveling Salesman Problem Using the IDINFO AlgorithmYichun Su0Yunbo Ran1Zhao Yan2Yunfei Zhang3Xue Yang4School of Geography and Information Engineering, China University of Geosciences, Wuhan 430074, ChinaSchool of Geography and Information Engineering, China University of Geosciences, Wuhan 430074, ChinaNational Engineering Research Center of Geographic Information System, Wuhan 430074, ChinaSchool of Traffic & Transportation Engineering, Changsha University of Science & Technology, Changsha 410114, ChinaSchool of Geography and Information Engineering, China University of Geosciences, Wuhan 430074, ChinaThe 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.https://www.mdpi.com/2220-9964/14/3/111combinatorial optimization problemsweighted mean of vectors algorithmtraveling salesman problemshort-distance delivery |
| spellingShingle | Yichun Su Yunbo Ran Zhao Yan Yunfei Zhang Xue Yang Solving the Traveling Salesman Problem Using the IDINFO Algorithm ISPRS International Journal of Geo-Information combinatorial optimization problems weighted mean of vectors algorithm traveling salesman problem short-distance delivery |
| title | Solving the Traveling Salesman Problem Using the IDINFO Algorithm |
| title_full | Solving the Traveling Salesman Problem Using the IDINFO Algorithm |
| title_fullStr | Solving the Traveling Salesman Problem Using the IDINFO Algorithm |
| title_full_unstemmed | Solving the Traveling Salesman Problem Using the IDINFO Algorithm |
| title_short | Solving the Traveling Salesman Problem Using the IDINFO Algorithm |
| title_sort | solving the traveling salesman problem using the idinfo algorithm |
| topic | combinatorial optimization problems weighted mean of vectors algorithm traveling salesman problem short-distance delivery |
| url | https://www.mdpi.com/2220-9964/14/3/111 |
| work_keys_str_mv | AT yichunsu solvingthetravelingsalesmanproblemusingtheidinfoalgorithm AT yunboran solvingthetravelingsalesmanproblemusingtheidinfoalgorithm AT zhaoyan solvingthetravelingsalesmanproblemusingtheidinfoalgorithm AT yunfeizhang solvingthetravelingsalesmanproblemusingtheidinfoalgorithm AT xueyang solvingthetravelingsalesmanproblemusingtheidinfoalgorithm |