Let's suppose I have the following cost matrix, and I would like the path (and total cost) starting from node 20 from the perspective of Traveling salesman problem via nearest insertion method.
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))
ds.ex
2 13 14 17 20
2 0.0 Inf Inf 1.9 1.7
13 Inf 0.0 7.3 7.4 7.2
14 Inf 7.3 0.0 7.7 7.8
17 1.9 7.4 7.7 0.0 9.2
20 1.7 7.2 7.8 9.2 0.0
I am using TSP package to solve:
ds.ex.tsp <- as.TSP(ds.ex)
(a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start=5))
object of class ‘TOUR’
result of method ‘nearest_insertion’ for 5 cities
tour length: 25.8
Can I get the path from:
`attr(a, "names")
[1] "20" "2" "17" "14" "13"
?
If that is really the path, why isn't the path 20-2-17-13-14 the result? Once after having nodes 20, 2 and 17 visited, the one with smaller cost is the 13 and not 14.
Thanks in advance!
We can use labels.TSP, i.e.
library(TSP)
ds.ex.tsp <- as.TSP(ds.ex)
a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start = 5)
labels(a)
#[1] "20" "13" "14" "17" "2"
Note that in the nearest insertion heuristic you add cities to a route based on its minimal distance to all the cities that are already in the route. A city is chosen at random if there are two cities that have the same distance. So solve_TSP may return different optimal paths upon replication. This seems to be the case in the example you give.
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))