Julia 中的广义旅行商问题

Question

我正在开展一个项目，我必须解决 GTSP。 该项目是关于一位总理必须访问每个选区（集群）中的一个城市，并且必须从城市 1 开始和结束。

我有 17 个不同的城市和 5 个集群（没有城市 1）。 截至目前，我已经在 Julia 中编写了以下内容，但它似乎没有给我一个正确的答案，因为我从边缘 1 开始到边缘 1..（参见底部的输出）

我知道我缺少一些限制，但到目前为止，我觉得我已经尝试了一切，但似乎不起作用。对于缺少约束，您有什么建议吗？

using JuMP
using GLPK

m = Model(GLPK.Optimizer)
n=17
cost = [0   506 635 91  385 155 110 130 490 368 154 68  610 641 471 265 255;
    506 0   355 415 585 475 480 500 605 320 380 440 360 235 81  480 440;
    635 355 0   602 390 495 560 531 295 675 640 575 705 585 435 420 755;
    91  415 602 0   347 118 75  94  457 280 63  27  520 550 380 232 235;
    385 585 390 347 0   240 305 276 120 590 410 320 835 745 575 125 582;
    155 475 495 118 240 0   65  36  350 365 181 91  605 610 440 125 353;
    110 480 560 75  305 65  0   29  415 348 138 48  590 625 455 190 310;
    130 500 531 94  276 36  29  0   386 367 157 67  610 635 465 161 329;
    490 605 295 457 120 350 415 386 0   625 520 430 865 770 600 230 680;
    368 320 675 280 590 365 348 367 625 0   240 300 250 285 245 475 150;
    154 380 640 63  410 181 138 157 520 240 0   90  480 515 345 295 175;
    68  440 575 27  320 91  48  67  430 300 90  0   545 577 407 205 262;
    610 360 705 520 835 605 590 610 865 250 480 545 0   190 295 715 400;
    641 235 585 550 745 610 625 635 770 285 515 577 190 0   170 645 435;
    471 81  435 380 575 440 455 465 600 245 345 407 295 170 0   475 385;
    265 480 420 232 125 125 190 161 230 475 295 205 715 645 475 0   467;
    255 440 755 235 582 353 310 329 680 150 175 262 400 435 385 467 0]

c1 = [13,14]
c2 = [5,9,16]
c3 = [4,6,7,8,11,12,17]
c4 = [3]
c5 = [2, 10, 15]

c = [c1, c2, c3, c4, c5]

#variable definition
@variable(m, x[1:n,1:n], Bin)
@variable(m, u[1:n])
@variable(m, z[1:n], Bin)

#objective function
@objective(m, Min, sum(cost[i, j] * x[i,j] for i = 1:n for j = 1:n))

# constraints - flow out of node
@constraint(m, sum(x[i,j] for j =1:n for i=1) == 1 )
@constraint(m, sum(x[i,j] for j in c5 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c1 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c2 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c3 for i =1:n) == 1)
@constraint(m, sum(x[i,j] for j in c4 for i =1:n) == 1)

#float into cluster
@constraint(m, sum(x[i,j] for j =1 for i = 1:n) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c1) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c2) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c3) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c4) == 1)
@constraint(m, sum(x[i,j] for j=1:n for i =c5) == 1)


# constraints - node order
for i=1:n, j=1:n
    if i != 1 && j!=1
        @constraint(m, u[i]-u[j]+(n-1)*x[i,j] <= (n-2))
    end 
end

# constraints - bounds on u
@constraint(m, u[1]==1)
@constraint(m, oneposl[i=2:n], u[i]>=2)
@constraint(m, oneposu[i=2:n], u[i]<=n)
optimize!(m)

println("Objective Value: ", JuMP.objective_value(m))
for i=1:n, j=1:n
   if JuMP.value(x[i,j]) > 1-1e-6
      println("Edge ", i, "-", j, " ", JuMP.value(x[i,j]))
      #println("x:", )
   end
end

我尝试了一些不同的约束，但我可以看到我需要对进出每个集群的顺序进行一些约束。

Answer 1

尝试添加：

for i=1:n
    @constraint(m, sum(x[i,j]-x[j,i] for j=1:n) == 0)
end

这些约束确保每个节点（不是集群）的入边和出边数量相同。 如果没有这个约束，循环可能会在一个节点进入集群并从另一个节点退出。