TomSym Airline Hub Location: Difference between revisions
No edit summary |
No edit summary |
||
Line 170: | Line 170: | ||
<pre> | <pre> | ||
Problem type appears to be: mip | Problem type appears to be: mip | ||
Time for symbolic processing: 0. | Time for symbolic processing: 0.096342 seconds | ||
Starting numeric solver | Starting numeric solver | ||
===== * * * =================================================================== * * * | ===== * * * =================================================================== * * * | ||
Line 183: | Line 183: | ||
FuncEv 154 | FuncEv 154 | ||
CPU time: 0. | CPU time: 0.015600 sec. Elapsed time: 0.017000 sec. | ||
Put hubs in | Put hubs in | ||
Bost | Bost |
Latest revision as of 09:32, 8 November 2011
This page is part of the TomSym Manual. See TomSym Manual. |
Problem description
FAL (the Flying Air Lines) specializes in freight transport. The company links the major French cities with cities in the United States, namely: Atlanta, Boston, Chicago, Marseille, Nice, and Paris. The average quantities in tonnes transported every day by this company between these cities are given in the following table.
Average quantity of freight transported between every pair of cities
+---------+-------+------+-------+---------+----+-----+ | |Atlanta|Boston|Chicago|Marseille|Nice|Paris| |Atlanta | 0 | 500 | 1000 | 300 |400 |1500 | |Boston |1500 | 0 | 250 | 630 |360 |1140 | |Chicago | 400 | 510 | 0 | 460 |320 | 490 | |Marseille| 300 | 600 | 810 | 0 |820 | 310 | |Nice | 400 | 100 | 420 | 730 | 0 | 970 | |Paris | 350 | 1020 | 260 | 580 |380 | 0 | +---------+-------+------+-------+---------+----+-----+
We shall assume that the transport cost between two cities i and j is proportional to the distance that separates them. The distances in miles are given in the next table.
Distances between pairs of cities
+---------+------+-------+---------+----+-----+ | |Boston|Chicago|Marseille|Nice|Paris| +---------+------+-------+---------+----+-----+ |Atlanta | 945 | 605 | 4667 |4749| 4394| |Boston | 866 |3726 | 3806 |3448| | |Chicago | 4471 |4541 | 4152 | | | |Marseille| 109 | 415 | | | | |Nice | 431 | | | | | +---------+------+-------+---------+----+-----+
The airline is planning to use two cities as connection platforms (hubs) to reduce the transport costs. Every city is then assigned to a single hub. The traffic between cities assigned to a given hub H1 to the cities assigned to the other hub H2 is all routed through the single connection from H1 to H2 which allows the airline to reduce the transport cost. We consider that the transport cost between the two hubs decreases by 20%. Determine the two cities to be chosen as hubs in order to minimize the transport cost.
Variables
frights Goods between cities distances Distances hubs Number of hubs
Results
The result from this example is quite hard to interpret since flows should be split into a tensor of rank 4 with the indices i, j, k and l and also into a vector of length c (number of cities). The vector indicates the hubs. For all non-zero element (i,j,k,l) in the tensor the following interpretation is possible: the route from city i to j passes through the hubs k and l.
In the example below temp(3,5,2,6) == 1 since the route from 3 (Chicago) to 5 (Nice) pass through 2 (Boston) and 6 (Paris). Also temp(4,5,6,6) == 1 since the route from 4 (Marseille) to 5 (Nice) pass through only 6 (Paris).
References
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.2.0$
% Written Nov 7, 2005. Last modified Apr 11, 2008.
Problem setup
frights = tomArray([ 0 500 1000 300 400 1500;...
1500 0 250 630 360 1140;...
400 510 0 460 320 490;...
300 600 810 0 820 310;...
400 100 420 730 0 970;...
350 1020 260 580 380 0]);
distances = tomArray([ 0 945 605 4667 4749 4394;...
945 0 866 3726 3806 3448;...
605 866 0 4471 4541 4152;...
4667 3726 4471 0 109 415;...
4749 3806 4541 109 0 431;...
4394 3448 4152 415 431 0]);
hubs = 2;
cities = size(frights,1); % city/hub i,j,k,l
i = tomArrayIdx('i',1:cities);
j = tomArrayIdx('j',1:cities);
k = tomArrayIdx('k',1:cities);
l = tomArrayIdx('l',1:cities);
flows = tom('flows',cities^4,1,'int');
flows = tomArray(flows,[cities,cities,cities,cities]);
hub = tom('hub', cities, 1, 'int');
% All variables are binary
bnds = {0 <= flows <= 1, 0 <= hub <= 1};
% Hub constraint
con1 = {sum(hub) == hubs};
% i and j constraint
con2 = {sum(sum(flows(i,j,k,l),k),l) == 1};
% Hub constraint 1 and 2
con3 = cell(cities,1);
con4 = cell(cities,1);
for iter = 1:cities
con3{iter} = {flows(i,j,iter,l) <= hub(iter)};
con4{iter} = {flows(i,j,k,iter) <= hub(iter)};
end
% Objective
objective = sum(vec(frights(i,j).*...
(distances(i,k)+distances(l,j)+distances(k,l)*.8).*...
flows(i,j,k,l)));
constraints = {bnds, con1, con2, con3, con4};
options = struct;
options.solver = 'cplex';
options.name = 'Airline Hub Location';
sol = ezsolve(objective,constraints,[],options);
PriLev = 1;
if PriLev > 0
c = 6; % number of cities
c_names = ['Atla';'Bost';'Chic';'Mars';'Nice';'Pari'];
temp = reshape(sol.flows(1:c^4),c,c,c,c);
hubs = find(sol.hub);
disp('Put hubs in ')
for h = 1: length(hubs),
disp([' ' num2str(c_names(hubs(h),:)) ])
end
% displaying the routes between cities
for i = 1:c,
for j = i+1:c,
for k = 1:c,
for l = 1:c,
if temp(i,j,k,l) == 1
% route involving one hub
if k==l & i~=k & j~=k & i~=j,
disp(['the route ' num2str([c_names(i,:),' ', ...
c_names(j,:)]) ' requires hub ' num2str(c_names(k,:))])
% route involving two hubs
elseif i~=j & i~=k & i~=l & j~=k & j~=l & k~=l,
disp(['the route ' num2str([c_names(i,:),' ', ...
c_names(j,:)]) ' requires hubs ' ...
num2str([c_names(k,:),' ', c_names(l,:)])])
% route between hubs
elseif ( (i==k & j==l) | (i==l & j==k) ) & k~=l,
disp(['the route ' num2str([c_names(i,:),' ', ...
c_names(j,:)]) ' is between hubs' ])
end
end
end
end
end
end
end
% MODIFICATION LOG
%
% 051107 med Created
% 060113 per Added documentation
% 060116 per Minor changes
% 060125 per Moved disp to end
% 060203 med Updated print level
% 090412 med Converted to tomSym
Problem type appears to be: mip Time for symbolic processing: 0.096342 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== Problem: --- 1: Airline Hub Location f_k 42153794.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 154 CPU time: 0.015600 sec. Elapsed time: 0.017000 sec. Put hubs in Bost Pari the route Atla Chic requires hub Bost the route Atla Mars requires hubs Bost Pari the route Atla Nice requires hubs Bost Pari the route Bost Pari is between hubs the route Chic Mars requires hubs Bost Pari the route Chic Nice requires hubs Bost Pari the route Mars Nice requires hub Pari