我正在使用 R 中的 TSP 包解决旅行推销员问题,但试图实现预定的起点和终点。
该软件包显然允许设置旅程的起点,如下所述: How to specify a starting city using the TSP package in R
想知道是否有人知道设置终点的方法。我了解 TSP 本质上是开放式的,因此可能无法预设端点。在这种情况下,我愿意接受另一种最近邻方法,该方法会产生类似的结果(通过多元相似性/距离设置起点和终点的有序序列)。
这是一个简单的示例:
dat <- data.frame(X=sample(0:100,n)/100,Y=sample(0:100,n)/100,Z=sample(0:100,n)/100)
dat$SUM <- rowSums(dat)
startPoint <- which.min(dat$SUM) # Lowest sum
endPoint <- which.max(dat$SUM) # Highest sum
tsp <- solve_TSP(TSP(ddat), method="nearest_insertion", start=startPoint)
tsp[1]==startPoint
> TRUE
tsp[n]==endPoint
> FALSE
不幸的是,“nearest_insertion”方法(以及任何其他非随机方法)始终返回相同的路径,因此端点永远不会改变。因此,我可以删除 start= 选项,更改为随机起点方法,然后将其放入 while() 循环中,并希望它最终收敛到一个解决方案:
while(tsp[1]!=startPoint | tsp[n]!=endPoint){
tsp <- solve_TSP(TSP(dist(dat[c("X","Y","Z")])), method="two_opt")
}
tsp[n]==endPoint
> TRUE
即使对于大数据,这似乎也能一致且非常快速地工作,而且我还没有遇到过挂起循环的随机生成的数据集。但最好使用更优雅(更少暴力)的方法。有什么想法吗?
最佳答案
从结束节点到起始节点添加一条边,成本为 0。将每个其他节点的边添加到起始节点,成本非常高。然后运行通常的 TSP(在起始节点开始和结束)。这应该等同于您正在尝试解决的问题。
关于r - 具有设定起点和终点的旅行推销员 (TSP),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36086406/