原文链接：http://tecdat.cn/?p=6551
罕用术语中的旅行推销员问题（TSP）是最简单的问题之一，归结为组合优化。旅行到 n 个城市（顶点）须要查看（n-1）！可能性。3,000 个地点有 4 * 10 ^ 9131 个可能的解决方案。
本文考察了 R 包的性能：TSP 和 tspmeta。后果对我的应用十分称心。
以下代码输入您的 TSP225.csv 文件并输入您的解决方案和可视化。生成的 ’tour’ 对象是一类 TOUR 和整数; 它蕴含您的解决方案。
coords.df <- data.frame(long=TSP225$Long, lat=TSP225$Lat)coords.mx <- as.matrix(coords.df)# Compute distance matrixdist.mx <- dist(coords.mx)# Construct a TSP objecttsp.ins <- tsp_instance(coords.mx, dist.mx)#tour <- run_solver(tsp.ins, method="2-opt")#Plotautoplot(tsp.ins, tour)
比拟解决方案：下图显示了 7 种启发式解决方案的最佳游览长度和协和式的确切解决方案。对于协和解决方案，我应用了在 UW-Madison 主持的 NEOS-Server。
methods <- c("nearest_insertion" "2-opt")tours <- sapply(methods simplify = FALSE)dotchart(),)
在 2D 中的#2 3000 个随机顶点
显然，随着顶点数量的增长，准确解和其余启发式解决方案之间的差别显着减少。2-opt 解决方案最靠近最优。反复的 2 -opt 解决方案和筛选最小的值让我十分靠近于确切的解决方案。