TomSym Flight Connections at a Hub

From TomWiki
Jump to navigationJump to search

Notice.png

This page is part of the TomSym Manual. See TomSym Manual.

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$
% Written Oct 7, 2005.   Last modified Apr 8, 2009.

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.
% 060113 per   Added documentation.
% 060125 per   Moved disp to end
% 060203 med   Print level updated
% 090308 med   Converted to tomSym
Problem type appears to be: mip
Time for symbolic processing: 0.019158 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license  999007. Valid to 2011-12-31
=====================================================================================
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 
Elapsed time: 0.003000 sec. 
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