# Airline Hub Location

## Contents

## 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 distance Distances hubs Number of hubs

## Results

The result from this example is quite hard to interpret since flow 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]); distance = 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); flow = tom('flow',cities^4,1,'int'); flow = tomArray(flow,[cities,cities,cities,cities]); hub = tom('hub', cities, 1, 'int'); % All variables are binary bnds = {0 <= flow <= 1, 0 <= hub <= 1}; % Hub constraint con1 = {sum(hub) == hubs}; % i and j constraint con2 = {sum(sum(flow(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} = {flow(i,j,iter,l) <= hub(iter)}; con4{iter} = {flow(i,j,k,iter) <= hub(iter)}; end % Objective objective = sum(vec(frights(i,j).*... (distance(i,k)+distance(l,j)+distance(k,l)*.8).*... flow(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.flow(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 Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05 ===================================================================================== 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.046875 sec. Elapsed time: 0.047000 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