3

R で巡回セールスマンの問題をコーディングしたいと思います。最初は 3 つの都市から始めて、さらに多くの都市に拡大します。以下の距離行列は、3 つの都市間の距離を示します。目的 (誰かが知らない場合) は、セールスマンが都市から出発し、最小距離を移動する必要があるように他の 2 つの都市を訪問することです。

以下のケースでは、彼は ny または LA から出発し、次にシカゴに移動し、次に残りの都市に移動する必要があります。A_ (私の制約行列) を定義するのに助けが必要です。

私の決定変数は、距離行列と同じ次元になります。これは 1,0 行列で、1 は行名に等しい都市から列名に等しい都市への移動を表します。たとえば、セールスマンがニューヨークからシカゴに旅行する場合、行 1 の 2 番目の要素は 1 になります。私の列と行の名前は ny、chicago、LA です。

問題の解決策を見て、私の制約は次のようになると結論付けました::

彼は同じ都市から 2 回離れることはできないため、行の合計は 1 未満でなければなりません

同じ都市に 2 回入ることはできないため、列の合計は 1 未満でなければなりません

セールスマンは 2 つの都市を訪問し、2 つの都市から出発するため、行列要素の合計は 2 でなければなりません。

A_ (私の制約行列) を定義するのに助けが必要です。意思決定変数を制約に結び付けるにはどうすればよいですか?

 ny=c(999,9,20)
 chicago=c(9,999,11)
 LA=c(20,11,999)
 distances=cbind(ny,chicago,LA)


 dv=matrix(c("a11","a12","a13","a21","a22","a23","a31","a32","a33"),nrow=3,ncol=3)

 c_=c(distances[1,],distances[2,],distances[3,])
 signs = c((rep('<=', 7)))
 b=c(1,1,1,1,1,1,2)
 res = lpSolve::lp('min', c_, A_, signs, b,  all.bin = TRUE)
4

2 に答える 2

1

このパッケージを使用して、gaoptim順列/実数値の問題を解決できます。これは純粋な R であるため、それほど高速ではありません。

ユーロ ツアーの問題 (?optim を参照)

 eurodistmat = as.matrix(eurodist)

 # Fitness function (we'll perform a maximization, so invert it)
 distance = function(sq)
 {
   sq = c(sq, sq[1])
   sq2 <- embed(sq, 2)
   1/sum(eurodistmat[cbind(sq2[,2], sq2[,1])])
 }

 loc = -cmdscale(eurodist, add = TRUE)$points
 x = loc[, 1]
 y = loc[, 2]
 n = nrow(eurodistmat)

 set.seed(1)

 # solving code
 require(gaoptim)
 ga2 = GAPerm(distance, n, popSize = 100, mutRate = 0.3)
 ga2$evolve(200)
 best = ga2$bestIndividual()
 # solving code

 # just transform and plot the results
 best = c(best, best[1])
 best.dist = 1/max(ga2$bestFit())
 res = loc[best, ]
 i = 1:n

 plot(x, y, type = 'n', axes = FALSE, ylab = '', xlab = '')
 title ('Euro tour: TSP with 21 cities')
 mtext(paste('Best distance found:', best.dist))
 arrows(res[i, 1], res[i, 2], res[i + 1, 1], res[i + 1, 2], col = 'red', angle = 10)
 text(x, y, labels(eurodist), cex = 0.8, col = 'gray20')
于 2013-10-09T14:20:06.877 に答える