用于“近似旅行商问题”的新哈里斯鹰算法

《Intelligent Systems with Applications》：New Harris Hawks algorithms for the Close-Enough Traveling Salesman Problem

本研究首次将Harris Hawks Optimization（HHO）算法应用于Close-Enough旅行商问题（CETSP），提出并行多种群HHO-CETSP算法及新型探索-利用算子，通过OpenMP框架实现高效并行计算，在47个基准实例中找到18个新最佳解，并成功应用于汽车焊接机器人路径规划，验证了其在无人机导航、物流等领域的工业适用性。

　　这是一篇关于将哈里斯鹰优化（HHO）算法应用于接近足够旅行商问题（CETSP）的研究论文。CETSP是一种组合优化问题，其目标是通过访问特定区域而非精确坐标来完成最短路径的规划。该问题在现实世界中具有广泛的应用，例如无人机和无人驾驶飞行器的路径规划、自主车辆导航、无线传感器网络的数据收集以及物流和配送服务等。传统旅行商问题（TSP）要求旅行者必须访问每一个目标点，而CETSP允许旅行者在每个目标点周围一定范围内完成任务，这为实际应用提供了更高的灵活性和效率。

研究人员提出了新的HHO算法变体，包括一种并行多种群版本，该版本基于OpenMP框架进行设计，以提高计算效率和多样性。通过同时运行多个子种群，算法能够更好地探索解决方案空间，特别是在大规模和实时问题中表现尤为突出。此外，还引入了新的问题特定探索和利用操作符，这些操作符专门针对CETSP的几何结构，使得搜索过程能够更有效地引导到高质量的解决方案。

研究团队对47个基准实例进行了全面的实证评估，其中包括合成问题实例和一个现实世界中的汽车制造机器人焊接场景。实验结果表明，所提出的算法优于现有的最先进的技术，如遗传算法（GA）、混合遗传算法（MA-CETSP）和基于变邻域搜索（VNS）的方法，成功找到了18个新的最佳解决方案。这些结果突出了该算法的强收敛行为、在不同问题规模下的鲁棒性和实际应用价值。此外，该算法的模块化和可扩展结构为其未来适应多目标和动态版本的CETSP提供了可能，使其在学术研究和工业部署中具有广泛的适用性。

在本研究中，研究人员回顾了CETSP的相关工作，并介绍了他们提出的HHO算法。这些算法包括HHO-CETSP和多种群HHO（Multi-Pop-HHO），后者是一种并行版本，旨在提高探索和利用的平衡。通过使用多线程处理和并行计算，这些算法能够更高效地解决大规模问题。实验结果显示，Multi-Pop-HHO在多个实例中表现优于HHO-CETSP，尤其是在处理复杂和不规则几何结构的问题时。这种多种群设计增强了算法的探索能力，使其能够找到更高质量的解决方案。

研究人员还对CETSP的数学模型进行了详细介绍，包括决策变量和目标函数。该模型通过最小化总行程距离来确保每个目标点被访问，同时考虑到每个客户的服务区域。通过这种平衡，模型适用于需要灵活性和效率的现实世界应用。

在实验部分，研究团队使用了一台专门配置的工作站，其具备强大的计算能力，以处理计算密集型任务。实验涵盖了多个基准实例，包括从TSBLIB、团队优化和几何构造问题中选取的实例。实验结果表明，HHO-CETSP和Multi-Pop-HHO在不同规模的问题上都表现出良好的性能。特别是对于大规模问题，如bonus1000和team5_499，Multi-Pop-HHO能够在更长的计算时间中找到更优的解决方案。

此外，研究人员还进行了一个实际案例研究，聚焦于汽车制造中的激光焊接机器人路径规划。实验结果显示，HHO算法在所有六个测试实例中都表现最佳，表明其在工业应用中的潜力。尽管其他方法如MA-CETSP在计算时间上更快，但HHO算法在解决方案的质量上具有优势。

综上所述，这项研究为CETSP提供了一种有效的解决方案，特别是在大规模和实时问题上。HHO算法的模块化和可扩展性使其能够适应多目标和动态版本的CETSP，这为未来的进一步研究和实际应用提供了新的方向。尽管HHO算法不能保证全局最优解，但在现实世界中，它能够提供快速、可靠且接近最优的解决方案，特别是在需要高效率和灵活性的场景中。未来的研究方向包括扩展算法以解决多目标CETSP变体，集成基于学习的自适应机制，以及与其他元启发式算法进行混合以进一步提高性能。