Research On Spherical Multi-Point Path Optimization Based on Simulated Annealing and Ant Colony Algorithms

Wenjun Ren; Jiarong Li; Lifei Kang

doi:10.54097/480dx617

Authors

Wenjun Ren
Jiarong Li
Lifei Kang

DOI:

https://doi.org/10.54097/480dx617

Keywords:

Spherical distance calculation, shortest path planning, Simulated Annealing algorithm, Ant Colony algorithm.

Abstract

In practical application scenarios such as logistics distribution and UAV cruise, the spherical multi-point path optimization problem has significant research value and practical significance. This research focuses on solving the spherical multi-point path optimization problem. The study first establishes a spherical distance calculation model, deriving the distance formula between any two points using spherical geometric principles. Taking eight specific points as research objects, the problem is transformed into a graph theory problem, and a single-objective linear programming model is constructed. The study employs Simulated Annealing Algorithm and Ant Colony Algorithm for comparative analysis. Through parameter optimization, the Simulated Annealing Algorithm achieved a shortest path length of 7.0381 kilometers. In comparison, the Ant Colony Algorithm obtained an optimal path (44-61-158-83-147-100-31-115) with a length of 4.0635 kilometers and a total time of 390.2 minutes, showing a 2.2% improvement in efficiency compared to the Simulated Annealing Algorithm. The results demonstrate that the Ant Colony Algorithm exhibits better performance and stability in this spherical multi-point path optimization problem.

Downloads

Download data is not yet available.

References

[1] SHADIBEKOVA D, ISMOILOV N. Development of digital logistics and transport in the process of globalization[C]//. Proceedings of the 5th International Conference on Future Networks and Distributed Systems, 2021: 688-692.

[2] VARNAVSKII V G. The global transportation and logistics infrastructure[J]. Herald of the russian academy of sciences, 2021,91: 65-72.

[3] MIR I, GUL F, MIR S, et al. A survey of trajectory planning techniques for autonomous systems[J]. Electronics, 2022,11(18): 2801.

[4] MAZAHERI H, GOLI S, NOUROLLAH A. A Survey of 3D Space Path-Planning Methods and Algorithms[J]. ACM Computing Surveys, 2024,57(1): 1-32.

[5] WU L, HUANG X, CUI J, et al. Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot[J]. Expert Systems with Applications, 2023,215: 119410.

[6] SHI K, WU W, WU Z, et al. Coverage path planning for cleaning robots based on improved simulated annealing algorithm and ant colony algorithm[J]. Signal, Image and Video Processing, 2024,18(4): 3275-3284.

[7] WANGSHENG F, CHONG W, RUHUA Z. Application of simulated annealing particle swarm optimization in complex three-dimensional path planning[C]//. Journal of Physics: Conference Series: IOP Publishing, 2021: 12077.

[8] SEYYEDABBASI A, ALIYEV R, KIANI F, et al. Hybrid algorithms based on combining reinforcement learning and metaheuristic methods to solve global optimization problems[J]. Knowledge-Based Systems, 2021,223: 107044.

[9] FRANZIN A, STÜTZLE T. A landscape-based analysis of fixed temperature and simulated annealing[J]. European Journal of Operational Research, 2023,304(2): 395-410.

[10] JIANG X, LIN Z, HE T, et al. Optimal path finding with beetle antennae search algorithm by using ant colony optimization initialization and different searching strategies[J]. IEEE Access, 2020,8: 15459-15471.