I'm working with a travelling salesman problem using the TSP package in R, but trying to achieve a predetermined start and end point.
The package apparently allows setting the start point of the journey, as described here: How to specify a starting city using the TSP package in R
Wondering if anyone knows a way to set the end point. I understand that the TSP is inherently open-ended, so a pre-set endpoint may not be possible. In that case, I'm open to another nearest neighbour approach that would produce similar results (ordered sequence by multivariate similarity/distance with set start and end point).
Here's a quick example:
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
Unfortunately, the "nearest_insertion" method (and any other non-random methods) always return the same path, so the endpoint never changes. So I could drop the start= option, change to a random start point method, then put this within a while() loop and hope that it eventually converges on a solution:
while(tsp[1]!=startPoint | tsp[n]!=endPoint){
tsp <- solve_TSP(TSP(dist(dat[c("X","Y","Z")])), method="two_opt")
}
tsp[n]==endPoint
> TRUE
This seems to work consistently and very quickly for even large data, and I haven't come across a randomly-generated data set that hangs the loop. But it would be nice to use a more elegant (less brute force) approach. Any thoughts?