How to do a math optimization (TSP) in R, perhaps with optim()

Question

I’m working on creating a basic traveling salesman problem (TSP) in R, but I haven’t found the right resources to help me use optim() with imported data. Or perhaps optim() is not really what I am looking for. I’ll share my example and hope that you could either point me in the right direction or help with the specific problem.

There are a set of locations to which I am trying to find the shortest route. Each location needs to be visited on the route once and only once. The route needs to start and end at the Origin. The possible solutions are:

From Origin > to Location1 > to Location2 > and back to Origin or

From Origin > to Location2 > to Location1 > and back to Origin

I’ve imported the following data into R:

distances <- read.csv("distances_test.csv")

ORIGIN-----DESTINATION-----DISTANCE

Origin-----Location2-------4.161917178

Origin-----Location1-------31.16857564

Location1--Location2-------30.75861336

Location1--Origin----------31.16857564

Location2--Location1-------30.75861336

Location2--Origin----------4.161917178

Now I am trying to determine how to tell R that:

The objective function is to minimize the sum of the distances multiplied by x, where x is an assignment variable (x = 0 or 1) indicating that the specific route is chosen.

The constraints are:

(1) x is between 0 and 1, x is integer (or if there is a shortcut with optim() to indicate that x is binary). (2) sum of x over all origin indices = 1 (i.e. the truck leaves each location once) (3) sum of x over all destination indices = 1 (i.e. truck truck arrives to each location once) (4) initial origin index is the Origin (5) final destination index is the Origin

With optim(par, objective), I am not clear on what the initial parameters would be or how I would write this objective function (i.e. min sum(i=1..n)sum(j=1...n) distance(i,j) * x(i,j) )

Answer 1

R can help you if you with the solve() function if you want to solve TSP via plain simplex algorithm.You can also have a look at this website where several heuristics for this problem are implemented in R. https://operatiology.wordpress.com/2014/05/15/traveling-salesman-problem-in-r/