TomSym Depot Location - Revision history

Mbot at 13:33, 8 November 2011

2011-11-08T13:33:22Z

← Older revision		Revision as of 09:33, 8 November 2011
Line 162:		Line 162:
	<pre>		<pre>
	Problem type appears to be: mip		Problem type appears to be: mip
	Time for symbolic processing: 0.~~027717~~ seconds		Time for symbolic processing: 0.027411 seconds
	Starting numeric solver		Starting numeric solver
	===== * * * =================================================================== * * *		===== * * * =================================================================== * * *
Line 177:		Line 177:

	FuncEv 139 Iter 2		FuncEv 139 Iter 2
	CPU time: 0.~~031200~~ sec. Elapsed time: 0.~~011000~~ sec.		CPU time: 0.015600 sec. Elapsed time: 0.013000 sec.
	minimal total cost = 18103.0417		minimal total cost = 18103.0417
	build the depots 1 5 8 9 12		build the depots 1 5 8 9 12

Mbot at 21:24, 2 November 2011

2011-11-02T21:24:33Z

← Older revision		Revision as of 17:24, 2 November 2011
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==

Mbot: 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..."

2011-11-02T21:01:40Z

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..."

New page

{{Part Of Manual|title=the TomSym Manual|link=[[TomSym|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

<source lang="matlab">
% 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.
</source>

==Problem setup==

<source lang="matlab">
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
</source>

<pre>
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

</pre>