基于大鄰域搜索的旅行商問題求解

打開文本圖片集

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）是組合優(yōu)化問題中一類經(jīng)典的NP完備問題，具有較高搜索空間和復(fù)雜度。（剩余5875字）