基于大邻域搜索的旅行商问题求解

打开文本图片集

Abstract：Asaclasscal problem incombinatorial optimization，TravellingSalesman Problem（TSP）hasa widerangeof practicalapplications inlogistics，path planningandother fields.Traditional exactsolving methods facethechallngeof computational ineficiency when dealing with large-scale problems，while heuristic algorithms have become the mainstream methodsforsolving TSPproblemsdue totheirflexibilityandeficiency.Inthis paper，aTSPsolving method basedonLarge NeighborhoodSearch（LNS）isadopted，which iterativelyoptimizes thesolutionthrough destructionandrepairoperators to balance he breadth and depth of the search.Experiments are carriedoutbased on several standard instances inthe TSPLib database，andtheresultsshowthattheproposed method exhibitsexcelentsolutionperformanceondatasetsofdiferentsizes and distributional characteristics，and is able to quickly converge to high-quality solutions.

Key words：Traveling Salesman Problem;Large Neighborhood Search;destructionoperator;repairoperator;combinatorial optimization

旅行商问题（TravellingSalesmanProblem，简称TSP）是组合优化问题中一类经典的NP完备问题，具有较高搜索空间和复杂度。（剩余5875字）