# Flight Connections at a Hub

## Problem description

The airline SafeFlight uses the airport Roissy-Charles-de-Gaulle as a hub to minimize the number of flight connections to European destinations. Six Fokker 100 airplanes of this airline from Bordeaux, Clermont-Ferrand, Marseille, Nantes, Nice, and Toulouse are landing between 11am and 12:30pm. These aircraft leave for Berlin, Bern, Brussels, London, Rome, and Vienna between 12:30 pm and 13:30 pm. The numbers of passengers transferring from the incoming flights to one of the outgoing flights are listed in the table below.

Numbers of passengers transferring between the different flights

```+----------------+---------------------------------------+
|Origins         |          Destinations                 |
|                +------+----+--------+------+----+------+
|                |Berlin|Bern|Brussels|London|Rome|Vienna|
+----------------+------+----+--------+------+----+------+
|Bordeaux        |  35  | 12 |   16   |   38 |  5 |   2  |
|Clermont-Ferrand|  25  |  8 |    9   |   24 |  6 |   8  |
|Marseille       |  12  |  8 |   11   |   27 |  3 |   2  |
|Nantes          |  38  | 15 |   14   |   30 |  2 |   9  |
|Nice            |   –  |  9 |    8   |   25 | 10 |   5  |
|Toulouse        |   –  |  – |    –   |   14 |  6 |   7  |
+----------------+------+----+--------+------+----+------+```

For example, if the flight incoming from Bordeaux continues on to Berlin, 35 passengers and their luggage may stay on board during the stop at Paris. The flight from Nice arrives too late to be re-used on the connection to Berlin, the same is true for the flight from Toulouse that cannot be used for the destinations Berlin, Bern and Brussels (the corresponding entries in the table are marked with '–').

How should the arriving planes be re-used for the departing flights to minimize the number of passengers who have to change planes at Roissy?

## Variables

```origdest                   People remaining in plane at transfer
idximp                     Impossible combinations```

## 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.2.0\$
```

## Problem setup

```origdest = [ 35 12 16 38  5  2;...
25  8  9 24  6  8;...
12  8 11 27  3  2;...
38 15 14 30  2  9;...
0  9  8 25 10  5;...
0  0  0 14  6  7];

idximp = find(origdest == 0);

n = size(origdest,1);

cont = tom('cont',n,n,'int');

% All variables are integers.
bnds = {0 <= cont <= 1, cont(idximp) == 0};

% Orig constr.
con1 = {sum(cont,1) == 1};

% Dest constr.
con2 = {sum(cont,2) == 1};

% Objective
objective = -sum(sum(origdest.*cont));

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Flight Connections at a Hub';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
p         = 6;                            % the number of planes
in_names  = ['Bord';'Cler';'Mars';...     % city names in
'Nant'; 'Nice'; 'Toul'];
out_names = ['Berl';'Bern';'Brus';...     % city names out
'Lond';'Rome';'Vien'];
transfers = sol.cont;

for i = 1:p,      % in  city has number i
for o = 1:p,    % out city has number o
if transfers(i,o) == 1,
disp(['plane from '     in_names(i,:)  ...
' continues to ' out_names(o,:) ])
end
end
end
end

% MODIFICATION LOG
%
% 051021 med   Created.
% 060125 per   Moved disp to end
% 060203 med   Print level updated
% 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: Flight Connections at a Hub    f_k    -112.000000000000000000
f(x_0)      0.000000000000000000

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

FuncEv   15
plane from Bord continues to Lond
plane from Cler continues to Bern
plane from Mars continues to Brus
plane from Nant continues to Berl
plane from Nice continues to Rome
plane from Toul continues to Vien
```