A small shopping mall has four shop locations. The walking distance, in feet, between all pairs of locations are shown below. Four shops, designated A, B, C, D, are to be assigned to the four locations in such a way that customers traveling between pairs of shops will not walk too far. We have data on the number of customers per week that travel between the shops, shown below.
Distance | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 0 | 80 | 150 | 170 |
2 | 0 | 130 | 100 | |
3 | 0 | 120 | ||
4 | 0 |
Flow | A | B | C | D |
---|---|---|---|---|
A | 0 | 5 | 2 | 7 |
B | 0 | 3 | 8 | |
C | 0 | 3 | ||
D | 0 |
using JuMP, NamedArrays, Gurobi, Cbc
S = [:A,:B,:C,:D]
L = [ 1, 2, 3, 4]
f = NamedArray([ 0 5 2 7
5 0 3 8
2 3 0 3
7 8 3 0 ], (S,S))
d = NamedArray([ 0 80 150 170
80 0 130 100
150 130 0 120
170 100 120 0 ], (L,L))
#m = Model(solver = GurobiSolver(OutputFlag=0))
m = Model(solver = CbcSolver())
@variable(m, x[S,L], Bin)
@variable(m, z[S,L,S,L], Bin)
for i in S
@constraint(m, sum( x[i,j] for j in L ) == 1) # each store is in exactly one location
end
for j in L
@constraint(m, sum( x[i,j] for i in S ) == 1) # each location has exactly one store
end
for i in S
for j in L
for k in S
for ℓ in L
@constraints(m, begin
x[i,j] >= z[i,j,k,ℓ]
x[k,ℓ] >= z[i,j,k,ℓ]
x[i,j] + x[k,ℓ] <= z[i,j,k,ℓ] + 1
end)
end
end
end
end
@objective(m, Min, 1/2*sum( f[i,k]*d[j,ℓ]*z[i,j,k,ℓ] for i in S, j in L, k in S, ℓ in L ))
solve(m)
sol = NamedArray(zeros(Int,4,4),(S,L),("store","loc"))
for i in S
for j in L
sol[i,j] = getvalue(x[i,j])
end
end
sol
4×4 Named Array{Int64,2} store ╲ loc │ 1 2 3 4 ────────────┼─────────── :A │ 1 0 0 0 :B │ 0 0 0 1 :C │ 0 0 1 0 :D │ 0 1 0 0