Subtour elimination constraints

Specific Domains Optimization (Mathematical)
, ,
11

I don’t understand what the y and z variables are doing, but this should point you in the right direction. (Assuming k is the different busses, that each must do a tour?)

using JuMP, Gurobi
c = [
    0.0 3.16 1.41 1.0 2.24
    3.16 0.0 4.0 3.61 4.12
    1.41 4.0 0.0 2.24 1.0
    1.0 3.61 2.24 0.0 3.16
    2.24 4.12 1.0 3.16 0.0
]
s = [
    0 0 0 0 0 0 0 0 0 0
    0 0 1 1 1 0 0 0 1 0
    0 0 0 1 0 0 1 1 0 1
    1 0 1 0 0 0 0 1 1 0
    0 1 0 0 0 1 1 1 0 0
]
V = 1:size(c, 1)
C, S, n = 10, 1:size(s, 2), length(V)
model = Model(Gurobi.Optimizer)
@variables(model, begin
    x[i in V, j in V, k in 1:n], Bin
    y[i in V, k in 1:n], Bin
    z[i in V, l in S, k in 1:n], Bin
    2 <= u[i in V, k in 1:n] <= length(V)
end) 
fix.(u[1, :], 1; force = true)
@objective(
    model,
    Min,
    sum(c[i, j] * x[i, j, k] for i in V, j in V, k in 1:n),
)
@constraints(model, begin
    # For all nodes and routes, flow out == flow in
    [i in V, k in 1:n], sum(x[i, :, k]) == sum(x[:, i, k])
    # Flow in and out of other nodes is 1
    [i in V; i != 1], sum(x[i, :, :]) == 1
    [i in V; i != 1], sum(x[:, i, :]) == 1
    # MTZ constraints
    [i in V, j in V, k in 1:n; i != 1 && j != 1],
        u[i, k] - u[j, k] + 1 <= (n - 1) * (1 - x[i, j, k])
    # y[i, k] is 1 if node i is in route k
    [i in V, k in 1:n], sum(x[i, :, k]) == y[i, k]
    # each node can be in at most one route, except node 1, which is in every 
    # route
    [i in V; i != 1], sum(y[i, :]) <= 1
    # I don't understand these constraints
    [i in V, l in S], sum(z[i, l, :]) <= s[i, l]
    [k in 1:n], sum(z[:, :, k]) <= C
    [i in V, l in S, k in 1:n], z[i, l, k] <= y[i, k]
    [l in S], sum(z[:, l, :]) == 1
end)
optimize!(model)
for k in 1:n
    print("Route $k: 1")
    i = 1
    while true
        for j in V
            if value(x[i, j, k]) > 0.5
                print(" => $j")
                i = j
                break
            end
        end
        if i == 1
            println()
            break
        end
    end
end
1 Like