基于信息素矩阵优化蚁群算法求解城市建模的旅行商问题
2025-08-03刘岱张亚鸣王凯崔海青
Travelling salesman of urban modeling based on pheromone matrix optimization ant colony algorithm
Liu Daia,Zhang Yamingʰ,Wang Kaib,Cui Haiqingh† (a.EngineegnCteFlfocftoutoatoltionUsitof 300000,China)
Abstract:This paper proposedanoptimizedantcolonyalgorithm toaddressthe traveling salesman problem(TSP)inurban modeling.Thealgorithmintegratedrandomaveragingofthepheromone matrix,adaptiveperturbation,anddynamicproportional resetingstrategies tooptimizethepath search intheprocessof acquiringurban modeling materials.Aftereachroundof path selection,thealgorithmgloballyupdatedthelocalpheromonebasedonthequalityof thepathsandacceleratedconvergence through2-optoptimization.Initialy,itappliedtherandomaveraging strategy.When theoptimalpathhadnotbeenupdated formultiple iterations,thepheromoneofrandom nodes wasaveraged toavoidlocaloptima.Whenmultipleatemptsattherandomaveraging strategyproveinefective,itintroducedtheadaptiveperturbationstrategy.Thisstrategyperturbedtheperomone matrix toselectpaths,therebyreducing theriskoflocal optima.This strategyperturbedthepheromonematrix toselect paths,reducingtheriskoflocaloptima.Whenthequalityof theoptimalpathdecreases byacertain proportion,itusedthe dynamicproportionalresetingstrategytoincreasethediferencebetweenhighandlowpheromonevaluesinthematrix,further accelerating convergence.Theresultsshowthatthealgorithm efectivelyimprovesglobal search capability,acelerates the convergence process,and provides a solution to the TSP in urban modeling.
Key words:antcolonyalgorithm;traveler’ssalesmanproblem;combinatorial optimization;2-optalgorithm;urban 3D modeling
0 引言
随着城市场景丰富和城市系统扩大,城市管理进人新阶段。城市模型在规划设计[1]、交通管理[2]和应急管理[3]等领域发挥重要作用,作为数字化城市的视觉表现。其通过模拟城市空间、结构和功能,为决策者提供关键信息和可视化参考。
现有高精度城市建模方法包括:基于多数据源的人工交互建模、基于影像和激光扫描点云的半自动建模,以及倾斜摄影建模[4]。这三种建模方法的共同特点是需对物体进行完整拍摄,覆盖所有最佳拍摄点并确保每个点至少拍摄一次,最终返回初始点,构成组合优化中的经典问题—旅行商问题(trave-ling salesmanproblem,TSP)[5]。其中,文献[6\~8]完成城市建模拍摄视点规划后,分别采用随机重启的2-opt算法、改进快速随机探索树算法和改进 A* 算法进行TSP路径规划。但是这些方法仍具有一定的局限性,未能深人开发优化路径规划的潜力。为此,提出新的方法进行补充开发,以提高城市建模中TSP的优化性能。
当前求解TSP的算法主要分为精确算法和近似算法。尽管精确算法能够提供最优解,但由于其计算量庞大[9,往往无法在实际问题中实现理想效率。因此,在大多数实际应用中,近似算法通常被优先选择,作为TSP的解决方案[10]。
近似算法中,蚁群算法(antcolonyoptimization,ACO)是一种受自然界蚂蚁觅食行为启发的元启发式近似算法,自20世纪90年代提出以来,因其良好的性能和灵活性被广泛应用于TSP的求解,进而被广泛应用于物流配送[11]、印刷电路板设计[12]和网络路由[13]等领域。蚁群算法通过模拟蚂蚁在路径上释放和追踪信息素(pheromone),逐步优化路径选择[14]。……
