factory, warehouse, sales allocation model: problem-凯发k8网页登录

this example shows how to set up and solve a mixed-integer linear programming problem. the problem is to find the optimal production and distribution levels among a set of factories, warehouses, and sales outlets. for the solver-based approach, see .

the example first generates random locations for factories, warehouses, and sales outlets. feel free to modify the scaling parameter $n$ , which scales both the size of the grid in which the production and distribution facilities reside, but also scales the number of these facilities so that the density of facilities of each type per grid area is independent of $n$ .

facility locations

for a given value of the scaling parameter $n$ , suppose that there are the following:

$⌊ f n^{2} ⌋$ factories
$⌊ w n^{2} ⌋$ warehouses
$⌊ s n^{2} ⌋$ sales outlets

these facilities are on separate integer grid points between 1 and $n$ in the $x$ and $y$ directions. in order that the facilities have separate locations, you require that $f w s \leq 1$ . in this example, take $n = 20$ , $f = 0.05$ , $w = 0.05$ , and $s = 0.1$ .

production and distribution

there are $p$ products made by the factories. take $p = 20$ .

the demand for each product $p$ in a sales outlet $s$ is $d (s, p)$ . the demand is the quantity that can be sold in a time interval. one constraint on the model is that the demand is met, meaning the system produces and distributes exactly the quantities in the demand.

there are capacity constraints on each factory and each warehouse.

the production of product $p$ at factory $f$ is less than $p c a p (f, p)$ .
the capacity of warehouse $w$ is $w c a p (w)$ .
the amount of product $p$ that can be transported from warehouse $w$ to a sales outlet in the time interval is less than $t u r n (p) * w c a p (w)$ , where $t u r n (p)$ is the turnover rate of product $p$ .

suppose that each sales outlet receives its supplies from just one warehouse. part of the problem is to determine the cheapest mapping of sales outlets to warehouses.

costs

the cost of transporting products from factory to warehouse, and from warehouse to sales outlet, depends on the distance between the facilities, and on the particular product. if $d i s t (a, b)$ is the distance between facilities $a$ and $b$ , then the cost of shipping a product $p$ between these facilities is the distance times the transportation cost $t c o s t (p)$ :

$d i s t (a, b) * t c o s t (p) .$

the distance in this example is the grid distance, also known as the $l_{1}$ distance. it is the sum of the absolute difference in $x$ coordinates and $y$ coordinates.

the cost of making a unit of product $p$ in factory $f$ is $p c o s t (f, p)$ .

optimization problem

given a set of facility locations, and the demands and capacity constraints, find:

a production level of each product at each factory
a distribution schedule for products from factories to warehouses
a distribution schedule for products from warehouses to sales outlets

these quantities must ensure that demand is satisfied and total cost is minimized. also, each sales outlet is required to receive all its products from exactly one warehouse.

variables and equations for the optimization problem

the control variables, meaning the ones you can change in the optimization, are

$x (p, f, w)$ = the amount of product $p$ that is transported from factory $f$ to warehouse $w$
$y (s, w)$ = a binary variable taking value 1 when sales outlet $s$ is associated with warehouse $w$

the objective function to minimize is

$\sum_{f} \sum_{p} \sum_{w} x (p, f, w) \cdot (p c o s t (f, p) t c o s t (p) \cdot d i s t (f, w))$

$\sum_{s} \sum_{w} \sum_{p} (d (s, p) \cdot t c o s t (p) \cdot d i s t (s, w) \cdot y (s, w)) .$

the constraints are

$\sum_{w} x (p, f, w) \leq p c a p (f, p)$ (capacity of factory).

$\sum_{f} x (p, f, w) = \sum_{s} (d (s, p) \cdot y (s, w))$ (demand is met).

$\sum_{p} \sum_{s} \frac{d (s, p)}{t u r n (p)} \cdot y (s, w) \leq w c a p (w)$ (capacity of warehouse).

$\sum_{w} y (s, w) = 1$ (each sales outlet associates to one warehouse).

$x (p, f, w) \geq 0$ (nonnegative production).

$y (s, w) ϵ {0, 1}$ (binary $y$ ).

the variables $x$ and $y$ appear in the objective and constraint functions linearly. because $y$ is restricted to integer values, the problem is a mixed-integer linear program (milp).

generate a random problem: facility locations

set the values of the $n$ , $f$ , $w$ , and $s$ parameters, and generate the facility locations.

rng(1) % for reproducibility
n = 20; % n from 10 to 30 seems to work. choose large values with caution.
n2 = n*n;
f = 0.05; % density of factories
w = 0.05; % density of warehouses
s = 0.1; % density of sales outlets
f = floor(f*n2); % number of factories
w = floor(w*n2); % number of warehouses
s = floor(s*n2); % number of sales outlets
xyloc = randperm(n2,f w s); % unique locations of facilities
[xloc,yloc] = ind2sub([n n],xyloc);

of course, it is not realistic to take random locations for facilities. this example is intended to show solution techniques, not how to generate good facility locations.

plot the facilities. facilities 1 through f are factories, f 1 through f w are warehouses, and f w 1 through f w s are sales outlets.

h = figure;
plot(xloc(1:f),yloc(1:f),'rs',xloc(f 1:f w),yloc(f 1:f w),'k*',...
    xloc(f w 1:f w s),yloc(f w 1:f w s),'bo');
lgnd = legend('factory','warehouse','sales outlet','location','eastoutside');
lgnd.autoupdate = 'off';
xlim([0 n 1]);ylim([0 n 1])

figure contains an axes object. the axes object contains 3 objects of type line. one or more of the lines displays its values using only markers these objects represent factory, warehouse, sales outlet.

generate random capacities, costs, and demands

generate random production costs, capacities, turnover rates, and demands.

p = 20; % 20 products
% production costs between 20 and 100
pcost = 80*rand(f,p)   20;
% production capacity between 500 and 1500 for each product/factory
pcap = 1000*rand(f,p)   500;
% warehouse capacity between p*400 and p*800 for each product/warehouse
wcap = p*400*rand(w,1)   p*400;
% product turnover rate between 1 and 3 for each product
turn = 2*rand(1,p)   1;
% product transport cost per distance between 5 and 10 for each product
tcost = 5*rand(1,p)   5;
% product demand by sales outlet between 200 and 500 for each
% product/outlet
d = 300*rand(s,p)   200;

these random demands and capacities can lead to infeasible problems. in other words, sometimes the demand exceeds the production and warehouse capacity constraints. if you alter some parameters and get an infeasible problem, during solution you will get an exitflag of -2.

generate variables and constraints

to begin specifying the problem, generate the distance arrays distfw(i,j) and distsw(i,j).

distfw = zeros(f,w); % allocate matrix for factory-warehouse distances
for ii = 1:f
    for jj = 1:w
        distfw(ii,jj) = abs(xloc(ii) - xloc(f   jj))   abs(yloc(ii) ...
            - yloc(f   jj));
    end
end
distsw = zeros(s,w); % allocate matrix for sales outlet-warehouse distances
for ii = 1:s
    for jj = 1:w
        distsw(ii,jj) = abs(xloc(f   w   ii) - xloc(f   jj)) ...
              abs(yloc(f   w   ii) - yloc(f   jj));
    end
end

create variables for the optimization problem. x represents the production, a continuous variable, with dimension p-by-f-by-w. y represents the binary allocation of sales outlet to warehouse, an s-by-w variable.

x = optimvar('x',p,f,w,'lowerbound',0);
y = optimvar('y',s,w,'type','integer','lowerbound',0,'upperbound',1);

now create the constraints. the first constraint is a capacity constraint on production.

capconstr = sum(x,3) <= pcap';

the next constraint is that the demand is met at each sales outlet.

demconstr = squeeze(sum(x,2)) == d'*y;

there is a capacity constraint at each warehouse.

warecap = sum(diag(1./turn)*(d'*y),1) <= wcap';

finally, there is a requirement that each sales outlet connects to exactly one warehouse.

salesware = sum(y,2) == ones(s,1);

create problem and objective

create an optimization problem.

factoryprob = optimproblem;

the objective function has three parts. the first part is the sum of the production costs.

objfun1 = sum(sum(sum(x,3).*(pcost'),2),1);

the second part is the sum of the transportation costs from factories to warehouses.

objfun2 = 0;
for p = 1:p
    objfun2 = objfun2   tcost(p)*sum(sum(squeeze(x(p,:,:)).*distfw));
end

the third part is the sum of the transportation costs from warehouses to sales outlets.

r = sum(distsw.*y,2); % r is a length s vector
v = d*(tcost(:));
objfun3 = sum(v.*r);

the objective function to minimize is the sum of the three parts.

factoryprob.objective = objfun1   objfun2   objfun3;

include the constraints in the problem.

factoryprob.constraints.capconstr = capconstr;
factoryprob.constraints.demconstr = demconstr;
factoryprob.constraints.warecap = warecap;
factoryprob.constraints.salesware = salesware;

solve the problem

turn off iterative display so that you don't get hundreds of lines of output. include a plot function to monitor the solution progress.

opts = optimoptions('intlinprog','display','off','plotfcn',@optimplotmilp);

call the solver to find the solution.

[sol,fval,exitflag,output] = solve(factoryprob,'options',opts);

figure optimization plot function contains an axes object. the axes object with title best objective: 3.0952e 07, relative gap: 0., xlabel number of nodes, ylabel objective value contains 4 objects of type line. one or more of the lines displays its values using only markers these objects represent root lb, cuts lb, heuristics ub, new solution.

if isempty(sol) % if the problem is infeasible or you stopped early with no solution
    disp('the solver did not return a solution.')
    return % stop the script because there is nothing to examine
end

examine the solution

examine the exit flag and the infeasibility of the solution.

exitflag

exitflag = 
    optimalsolution

infeas1 = max(max(infeasibility(capconstr,sol)))

infeas1 = 2.3647e-11

infeas2 = max(max(infeasibility(demconstr,sol)))

infeas2 = 2.2737e-13

infeas3 = max(infeasibility(warecap,sol))

infeas3 = 0

infeas4 = max(infeasibility(salesware,sol))

infeas4 = 8.8818e-16

round the y portion of the solution to be exactly integer-valued. to understand why these variables might not be exactly integers, see some “integer” solutions are not integers.

sol.y = round(sol.y); % get integer solutions

how many sales outlets are associated with each warehouse? notice that, in this case, some warehouses have 0 associated outlets, meaning the warehouses are not in use in the optimal solution.

outlets = sum(sol.y,1)

outlets = 1×20
     3     0     3     2     2     2     3     2     3     1     1     0     0     3     4     3     2     3     2     1

plot the connection between each sales outlet and its warehouse.

figure(h);
hold on
for ii = 1:s
    jj = find(sol.y(ii,:)); % index of warehouse associated with ii
    xsales = xloc(f w ii); ysales = yloc(f w ii);
    xwarehouse = xloc(f jj); ywarehouse = yloc(f jj);
    if rand(1) < .5 % draw y direction first half the time
        plot([xsales,xsales,xwarehouse],[ysales,ywarehouse,ywarehouse],'g--')
    else % draw x direction first the rest of the time
        plot([xsales,xwarehouse,xwarehouse],[ysales,ysales,ywarehouse],'g--')
    end
end
hold off
title('mapping of sales outlets to warehouses')

figure contains an axes object. the axes object with title mapping of sales outlets to warehouses contains 43 objects of type line. one or more of the lines displays its values using only markers these objects represent factory, warehouse, sales outlet.

the black * with no green lines represent the unused warehouses.