Traveling salesman (TSP) with set start and end point

Question

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?

Traveling salesman (TSP) with set start and end point

1 Answers