r - 设定起点和终点的旅行推销员(TSP)

我正在使用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(在您的起始节点处开始和结束)。这应该等效于您要解决的问题。