路径规划是实现机器人智能高效工作的关键性能指标之一。为了提高机器人的移动效率,本文基于传统的模拟退火算法（SA）提出了近傍测度-模拟退火算法(N-SA)模型来求解TSP。本文利用近傍测度去评估解的质量,有利于加快传统模拟退火算法收敛速度。研究中,将近傍测度与遗传算法（GA）、粒子群优化算法（PSO）等算法相结合,同样可以加快收敛速度,验证了近傍测度具有较高的鲁棒性。本文采用TSPLIB数据集进行实验,核心完成模拟退火算法与近傍测度结合。实验结果表明,利用近傍测度对模拟退火算法生成的解进行优化,能有效解决路径交叉问题。同时,解的质量快速收敛到95%以上。该模型具有速度快、计算量小、通用性强等特点,可为机器人的高效移动提供一定的研究价值。

路径规划；近傍测度；模拟退火算法；优化算法

[1]洪莉. 改进的鲸鱼优化算法及其在车辆路径问题中的应用[D].河南大学,2021.DOI:10.27114/d.cnki.ghnau.2021.000258. [2] Dong X, Xu M, Lin Q, et al. ITÖ algorithm with local search for large scale multiple balanced traveling salesmen problem[J]. Knowledge-Based Systems, 2021, 229: 107330. [3] Gunduz M, Aslan M. DJAYA: A discrete Jaya algorithm for solving traveling salesman problem[J]. Applied Soft Computing, 2021, 105: 107275. [4]程亚南,王晓峰,刘凇佐等.一种求解TSP问题的海鸥算法[J].现代电子技术,2022,45(07):112-116.DOI:10.16652/j.issn.1004-373x.2022.07.021. [5]吴剑杰.改进的人工鱼群算法求解TSP问题的研究[J].科技通报,2021,37(08):66-70.DOI:10.13774/j.cnki.kjtb.2021.08.012. [6] Manthey B, van Rhijn J. Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP[J]. arXiv preprint arXiv:2208.11444, 2022. [7] Cherabli M, Ourbih-Tari M, Boubalou M. Refined descriptive sampling simulated annealing algorithm for solving the traveling salesman problem[J]. Monte Carlo Methods and Applications, 2022, 28(2): 175-188. [8] Zhang Y, Han X, Dong Y, et al. A novel state transition simulated annealing algorithm for the multiple traveling salesmen problem[J]. The Journal of Supercomputing, 2021, 77: 11827-11852. [9]钱叶霞,陈子敬.基于改进模拟退火算法的配送路径优化研究[J].中国商论,2023,No.879(08):86-89.DOI:10.19699/j.cnki.issn2096-0298.2023.08.086. [10]翟昌宇,李德祯,刘博.并行模拟退火算法在智能调度中的应用[J].智能制造,2023,No.315(01):63-66. [11]]Tong B, Wang J, Wang X, et al. Optimal Route Planning for Truck–Drone Delivery Using Variable Neighborhood Tabu Search Algorithm[J]. Applied sciences, 2022, 12(1): 529. [12]Zhou Y, Xu W, Fu Z H, et al. Multi - neighborhood simulated annealing-based iterated local search for colored traveling salesman problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(9): 16072-16082. [13]Karakostas P, Sifaleras A. A double-adaptive general variable neighborhood search algorithm for the solution of the traveling salesman problem[J]. Applied Soft Computing, 2022, 121: 108746. [14]周昇.一种TSP的新算法:智能邻近点算法[J].南通职业大学学报,2017,31(03):72-76+81. [15]Yang S, Huang J, Li W, et al. A Novel Discrete Group Teaching Optimization Algorithm for TSP Path Planning with Unmanned Surface Vehicles[J]. Journal of Marine Science and Engineering, 2022, 10(9): 1305. [16]赵媛.改进的生成树算法求解旅行商问题[J].兰州大学学报(自然科学版),2008(S1):164-165+168.DOI:10.13885/j.issn.0455-2059.2008.s1.054.[17]Reinelt, G. TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing, 3, 376-384.http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.

DOI： 10.62639/sspis12.20240101

Published： 2024