TomSym Depot Location: Difference between revisions
(Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== A large company wishes to open new depots to deliver to its sales centers. Ever...") |
No edit summary |
||
Line 11: | Line 11: | ||
Delivery costs for satisfying entire demand of customers | Delivery costs for satisfying entire demand of customers | ||
<pre> | |||
+-----+-----------------------------------------------+ | +-----+-----------------------------------------------+ | ||
| | Customer | | | | Customer | | ||
Line 28: | Line 29: | ||
| 12 |200|180|150|Inf|Inf|Inf|100| 80| 50| 50| 60|100| | | 12 |200|180|150|Inf|Inf|Inf|100| 80| 50| 50| 60|100| | ||
+-----+---+---+---+---+---+---+---+---+---+---+---+---+ | +-----+---+---+---+---+---+---+---+---+---+---+---+---+ | ||
</pre> | |||
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. | 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. | ||
Line 33: | Line 35: | ||
Fix costs and capacity limits of the depot locations | Fix costs and capacity limits of the depot locations | ||
<pre> | |||
+------------+----+----+-----+----+----+----+----+----+----+-- | +------------+----+----+-----+----+----+----+----+----+----+-- | ||
|Depot | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| | |Depot | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| | ||
Line 39: | Line 42: | ||
|Capacity (t)|300|250|100|180|275|300|200|220|270|250|230|180| | |Capacity (t)|300|250|100|180|275|300|200|220|270|250|230|180| | ||
+------------+----+----+-----+----+----+----+----+----+----+-- | +------------+----+----+-----+----+----+----+----+----+----+-- | ||
</pre> | |||
The quantities demanded by the sales centers (customers), are summarized in the following table. | The quantities demanded by the sales centers (customers), are summarized in the following table. | ||
Line 44: | Line 48: | ||
Demand data | Demand data | ||
<pre> | |||
+----------+---+--+--+---+---+---+--+--+--+---+--+---+ | +----------+---+--+--+---+---+---+--+--+--+---+--+---+ | ||
|Customer | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|11| 12| | |Customer | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|11| 12| | ||
Line 49: | Line 54: | ||
|Demand (t)|120|80|75|100|110|100|90|60|30|150|95|120| | |Demand (t)|120|80|75|100|110|100|90|60|30|150|95|120| | ||
+----------+---+--+--+---+---+---+--+--+--+---+--+---+ | +----------+---+--+--+---+---+---+--+--+--+---+--+---+ | ||
</pre> | |||
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? | 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? | ||
Line 54: | Line 60: | ||
==Variables== | ==Variables== | ||
<pre> | |||
delcosts Costs to deliver to centre from depot | delcosts Costs to deliver to centre from depot | ||
idxinf Impossible combination of centre/depot | idxinf Impossible combination of centre/depot | ||
Line 60: | Line 67: | ||
capacity Capacities per potential depot | capacity Capacities per potential depot | ||
demand The customers demand in tonnes | demand The customers demand in tonnes | ||
</pre> | |||
==Reference== | ==Reference== |
Revision as of 17:24, 2 November 2011
This page is part of the TomSym Manual. See TomSym Manual. |
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 Time for symbolic processing: 0.027717 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== Problem: --- 1: Depot Location f_k 18103.041666666668000000 sum(|constr|) 0.000000000000014211 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 139 Iter 2 CPU time: 0.031200 sec. Elapsed time: 0.011000 sec. 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