Depot Location

Contents

Problem description

A large company wishes to open new depots to deliver to its sales centers. Every new set-up of a depot has a fixed cost. Goods are delivered from a depot to the sales centers close to the site. Every delivery has a cost that depends on the distance covered. The two sorts of cost are quite different: set-up costs are capital costs which may usually be written off over several years, and transport costs are operating costs. A detailed discussion of how to combine these two costs is beyond the scope of this text — we assume here that they have been put on some comparable basis, perhaps by taking the costs over a year.

There are 12 sites available for the construction of new depots and 12 sales centers need to receive deliveries from these depots.

The following table gives the costs (in thousand $) of satisfying the entire demand of each customer (sales center) from a depot (not the unit costs). So, for instance, the cost per unit of supplying customer 9 (who has a total demand of 30 tonnes according to the next table) from depot 1 is $ 60000/30t, i.e. $ 2000/t. Certain deliveries that are impossible are marked with "Inf".

Delivery costs for satisfying entire demand of customers

+-----+-----------------------------------------------+
|     |               Customer                        |
|Depot|  1   2   3   4   5   6   7   8   9  10  11  12|
+-----+---+---+---+---+---+---+---+---+---+---+---+---+
|   1 |100| 80| 50| 50| 60|100|120| 90| 60| 70| 65|110|
|   2 |120| 90| 60| 70| 65|110|140|110| 80| 80| 75|130|
|   3 |140|110| 80| 80| 75|130|160|125|100|100| 80|150|
|   4 |160|125|100|100| 80|150|190|150|130|Inf|Inf|Inf|
|   5 |190|150|130|Inf|Inf|Inf|200|180|150|Inf|Inf|Inf|
|   6 |200|180|150|Inf|Inf|Inf|100| 80| 50| 50| 60|100|
|   7 |100| 80| 50| 50| 60|100|120| 90| 60| 70| 65|110|
|   8 |120| 90| 60| 70| 65|110|140|110| 80| 80| 75|130|
|   9 |140|110| 80| 80| 75|130|160|125|100|100| 80|150|
|  10 |160|125|100|100| 80|150|190|150|130|Inf|Inf|Inf|
|  11 |190|150|130|Inf|Inf|Inf|200|180|150|Inf|Inf|Inf|
|  12 |200|180|150|Inf|Inf|Inf|100| 80| 50| 50| 60|100|
+-----+---+---+---+---+---+---+---+---+---+---+---+---+

In addition, for every depot we have the following information: the fixed cost for constructing the depot that needs to be included into the objective function and its capacity limit, all listed in the table below.

Fix costs and capacity limits of the depot locations

+------------+----+----+-----+----+----+----+----+----+----+--
|Depot       | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
+------------+----+----+-----+----+----+----+----+----+----+--
|Cost (m$)   |3.5|  9| 10|  4|  3|  9|  9|  3|  4| 10|  9|3.5|
|Capacity (t)|300|250|100|180|275|300|200|220|270|250|230|180|
+------------+----+----+-----+----+----+----+----+----+----+--

The quantities demanded by the sales centers (customers), are summarized in the following table.

Demand data

+----------+---+--+--+---+---+---+--+--+--+---+--+---+
|Customer  |  1| 2| 3|  4|  5|  6| 7| 8| 9| 10|11| 12|
+----------+---+--+--+---+---+---+--+--+--+---+--+---+
|Demand (t)|120|80|75|100|110|100|90|60|30|150|95|120|
+----------+---+--+--+---+---+---+--+--+--+---+--+---+

In every case, the demand of a customer needs to be satisfied but a sales center may be delivered to from several depots. Which depots should be opened to minimize the total cost of construction and of delivery, whilst satisfying all demands?

Variables

delcosts                   Costs to deliver to centre from depot
idxinf                     Impossible combination of centre/depot
delcosts(idxinf)           A large number < Inf
buildcosts                 Costs to build a depot=
capacity                   Capacities per potential depot
demand                     The customers demand in tonnes

Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.1.0$
% Written Oct 7, 2005.   Last modified Mar 8, 2009.

Problem setup

delcosts     = [ 100  80  50  50  60 100 120  90  60  70  65 110;...
    120  90  60  70  65 110 140 110  80  80  75 130;...
    140 110  80  80  75 130 160 125 100 100  80 150;...
    160 125 100 100  80 150 190 150 130 inf inf inf;...
    190 150 130 inf inf inf 200 180 150 inf inf inf;...
    200 180 150 inf inf inf 100  80  50  50  60 100;...
    100  80  50  50  60 100 120  90  60  70  65 110;...
    120  90  60  70  65 110 140 110  80  80  75 130;...
    140 110  80  80  75 130 160 125 100 100  80 150;...
    160 125 100 100  80 150 190 150 130 inf inf inf;...
    190 150 130 inf inf inf 200 180 150 inf inf inf;...
    200 180 150 inf inf inf 100  80  50  50  60 100];

idxinf = find(delcosts == inf);
delcosts(idxinf) = 1e6;

buildcosts   = [3500 9000 10000 4000 3000 9000 9000 3000 4000 10000 9000 3500]';
capacity     = [ 300  250   100  180  275  300  200  220  270   250  230  180]';
demand       = [ 120   80    75  100  110  100   90   60   30   150   95  120]';

d = length(buildcosts); % DEPOTS
c = length(demand);     % CUSTOMERS

fflow = tom('fflow',d,c);
build = tom('build',d,1,'int');

% Bounds
bnds1 = {0 <= build <= 1};
bnds2 = {0 <= fflow <= 1, fflow(idxinf) <= 0};

% Customer constraint.
con1 = {sum(fflow,1) == 1};

% Capacity constraint.
con2 = {(demand'*fflow')' <= capacity.*build};

% Objective
objective = sum(sum(delcosts.*fflow)) + buildcosts'*build;

constraints = {bnds1, bnds2, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Depot Location';
sol = ezsolve(objective,constraints,[],options);

f_k = subs(objective,sol);
PriLev = 1;
if PriLev > 0
    build   = find(sol.build)'; % the depots to build
    deliver = sol.fflow';
    deliver = deliver(:,build);
    deliver(find(deliver<0.001)) = 0;
    disp(['minimal total cost = ' num2str(f_k) ])
    disp(['build the depots     ' num2str(build)      ])
    [jj,ii] = size(deliver);                 % ii = depots, jj = customers
    for j = 1:jj,
        disp(['let customer ' num2str(j) ' get '])
        for i = 1:ii,
            if deliver(j,i) ~= 0,
                if deliver(j,i) == 1,
                    disp(['   all of its demand from depot ' num2str(build(i)) ])
                else
                    disp(['   ' num2str(deliver(j,i)) ...
                        ' of its demand from depot ' num2str(build(i)) ])
                end
            end
        end
    end
end

% MODIFICATION LOG
%
% 051019 med   Created
% 060112 per   Added documentation
% 060125 per   Moved disp to end
% 090308 med   Converted to tomSym
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Depot Location                 f_k   18103.041666666668000000
                                       sum(|constr|)      0.000000000000014442
                              f(x_k) + sum(|constr|)  18103.041666666668000000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv   78 
minimal total cost = 18103.0417
build the depots     1   5   8   9  12
let customer 1 get 
   all of its demand from depot 5
let customer 2 get 
   0.0625 of its demand from depot 1
   0.5 of its demand from depot 5
   0.4375 of its demand from depot 8
let customer 3 get 
   all of its demand from depot 1
let customer 4 get 
   all of its demand from depot 1
let customer 5 get 
   all of its demand from depot 9
let customer 6 get 
   all of its demand from depot 8
let customer 7 get 
   all of its demand from depot 12
let customer 8 get 
   all of its demand from depot 12
let customer 9 get 
   all of its demand from depot 12
let customer 10 get 
   0.56667 of its demand from depot 8
   0.43333 of its demand from depot 9
let customer 11 get 
   all of its demand from depot 9
let customer 12 get 
   all of its demand from depot 1