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?

Answer 1

Add an edge from the end node to the start node, with 0 cost. Add edges from every other node to the start node, with very high cost. Then run the usual TSP (starting and ending at your start node). This should be equivalent to the problem you are trying to solve.