Solving the TSP of the Obstacle Grid Map with SGP Vertex Extraction and Filtering Algorithm
Preprint
- 30 May 2025
- preprint
- Published by MDPI AG in Preprints.org
Abstract
In the obstacle grid map, due to the limited search directions of classical path algorithms and meta-heuristic algorithms, the shortest paths they solve are not true shortest paths (TSP), but rather shortest grid paths (SGP). In this paper, a SGP vertex extraction and filtering algorithm is proposed to extract and filter the key nodes in the SGP path, so as to obtain the TSP path under the same conditions. Experimental validation shows that the shortest path lengths found by the proposed SGP vertex extraction and filtering algorithm are shorter than those obtained by heuristic path algorithms, and it also outperforms recent new algorithms in comparative experiments. As the map scale increases and the obstacle rate rises, the advantages of this path algorithm become more pronounced.Keywords
All Related Versions
- Version 1, 2025-05-30, Preprints
- Published version: Algorithms, 18 (7), 400.
This publication has 15 references indexed in Scilit:
- A comprehensive survey on the generalized traveling salesman problemEuropean Journal of Operational Research, 2023
- Path planning optimization in unmanned aerial vehicles using meta-heuristic algorithms: a systematic reviewEnvironmental Monitoring and Assessment, 2022
- An Effective Genetic Algorithm for Solving the Clustered Shortest-Path Tree ProblemIEEE Access, 2021
- An improved distance‐based ant colony optimization routing for vehicular ad hoc networksInternational Journal of Communication Systems, 2020
- A novel swarm intelligence optimization approach: sparrow search algorithmSystems Science & Control Engineering, 2020
- Metaheuristic research: a comprehensive surveyArtificial Intelligence Review, 2018
- The vehicle routing problem: State of the art classification and reviewComputers & Industrial Engineering, 2016
- Particle swarm optimization2014
- Landscapes, operators and heuristic searchAnnals of Operations Research, 1999
- Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous SpacesJournal of Global Optimization, 1997