Warehouse location problem
Brief description
A company considers opening warehouses at some candidate locations with each of them having a maintenance cost if it is open.
The company controls a set of given stores and each of them needs to take supplies to one of the warehouses, but depending on the warehouse chosen, there will be an additional supply cost.
The objective is to choose which warehouse to open and to divide the stores among the open warehouses in order to minimize the total cost of supply and maintenance costs.
CFN model
We create Boolean variables for the warehouses (i.e., open or not) and integer variables for the stores, with domain size the number of warehouses to represent to which warehouse the store will take supplies.
Hard binary constraints represent that a store cannot take supplies from a closed warehouse. Soft unary constraints represent the maintenance cost of the warehouses. Soft unary constraints represent the store’s cost regarding which warehouse to take supplies from.
Data
Original data files can be download from the cost function library warehouses. Their format is described here.
Python model solver
The following code uses the pytoulbar2 module to generate the cost function network and solve it (e.g. “python3 warehouse.py cap44.txt 1” found an optimum value equal to 10349757). Other instances are available here in cfn format.
import sys
import pytoulbar2
f = open(sys.argv[1], 'r').readlines()
precision = int(sys.argv[2]) # in [0,9], used to convert cost values from float to integer (by 10**precision)
tokens = []
for l in f:
tokens += l.split()
pos = 0
def token():
global pos, tokens
if pos == len(tokens):
return None
s = tokens[pos]
pos += 1
return s
N = int(token()) # number of warehouses
M = int(token()) # number of stores
top = 1 # sum of all costs plus one
CostW = [] # maintenance cost of warehouses
Capacity = [] # capacity limit of warehouses (not used)
for i in range(N):
Capacity.append(token())
CostW.append(int(float(token()) * 10.**precision))
top += sum(CostW)
Demand = [] # demand for each store
CostS = [[] for i in range(M)] # supply cost matrix
for j in range(M):
Demand.append(int(token()))
for i in range(N):
CostS[j].append(int(float(token()) * 10.**precision))
top += sum(CostS[j])
# create a new empty cost function network
Problem = pytoulbar2.CFN(top)
# add warehouse variables
for i in range(N):
Problem.AddVariable('w' + str(i), range(2))
# add store variables
for j in range(M):
Problem.AddVariable('s' + str(j), range(N))
# add maintenance costs
for i in range(N):
Problem.AddFunction([i], [0, CostW[i]])
# add supply costs for each store
for j in range(M):
Problem.AddFunction([N+j], CostS[j])
# add channeling constraints between warehouses and stores
for i in range(N):
for j in range(M):
Constraint = []
for a in range(2):
for b in range(N):
if a == 0 and b == i:
Constraint.append(top)
else:
Constraint.append(0)
Problem.AddFunction([i, N+j], Constraint)
#Problem.Dump('warehouse.cfn')
Problem.Solve(showSolutions=3)