Models Air transport

From TomWiki
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Notice.png

This page is part of TOMLAB Models. See TOMLAB Models.

Flight connections at a hub

% function Result = flightconnectionsatahubEx(PriLev)
%
% Creates a TOMLAB MIP problem for flight connections at a hub
%
% FLIGHT CONNECTIONS AT A HUB
%
% 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
%
% RESULTS
%
% for an interpretation of the results, set PriLev > 1, for example:
% flightconnectionsatahubEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 21, 2005.   Last modified Feb 3, 2006.

function Result = flightconnectionsatahubEx(PriLev)

if nargin < 1
   PriLev = 1;
end

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);

Prob = flightconnectionsatahub(origdest, idximp);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1
   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 = reshape(Result.x_k,p,p);      % reshape x_k

   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

Composing flight crews

% function Result = composingflightcrewsEx(PriLev)
%
% Creates a TOMLAB MIP problem for composing flight crews
%
% COMPOSING FLIGHT CREWS
%
% During the Second World War the Royal Air Force (RAF) had many
% foreign pilots speaking different languages and more or less
% trained on the different types of aircraft. The RAF had to form
% pilot/co-pilot pairs (‘crews’) for every plane with a compatible
% language and a sufficiently good knowledge of the aircraft type. In
% our example there are eight pilots. In the following table every
% pilot is characterized by a mark between 0 (worst) and 20 (best)
% for his language skills (in English, French, Dutch, and Norwegian),
% and for his experience with different two-seater aircraft
% (reconnaissance, transport, bomber, fighterbomber, and supply
% planes).
%
% Ratings of pilots
%
% +----------+-------------------------+--+--+--+--+--+--+--+--+
% |          |Pilot                    | 1| 2| 3| 4| 5| 6| 7| 8|
% +----------+-------------------------+--+--+--+--+--+--+--+--+
% |Language  |English                  |20|14| 0|13| 0| 0| 8| 8|
% |          |French                   |12| 0| 0|10|15|20| 8| 9|
% |          |Dutch                    | 0|20|12| 0| 8|11|14|12|
% |          |Norwegian                | 0| 0| 0| 0|17| 0| 0|16|
% +----------+-------------------------+--+--+--+--+--+--+--+--+
% |Plane type|Reconnaissance           |18|12|15| 0| 0| 0| 8| 0|
% |          |Transport                |10| 0| 9|14|15| 8|12|13|
% |          |Bomber                   | 0|17| 0|11|13|10| 0| 0|
% |          |Fighter-bomber           | 0| 0|14| 0| 0|12|16| 0|
% |          |Supply plane             | 0| 0| 0| 0|12|18| 0|18|
% +----------+-------------------------+--+--+--+--+--+--+--+--+
%
% A valid flight crew consists of two pilots that both have each at
% least 10/20 for the same language and 10/20 on the same aircraft
% type.
%
% Question 1:
% Is it possible to have all pilots fly?
%
% Subsequently, we calculate for every valid flight crew the sum of
% their scores for every aircraft type for which both pilots are
% rated at least 10/20. This allows us to define for every crew the
% maximum score among these marks. For example, pilots 5 and 6 have
% marks 13 and 10 on bombers and 12 and 18 on supply planes. The
% score for this crew is therefore max(13 + 10, 12 + 18) = 30.
%
% Question 2:
% Which is the set of crews with maximum total score?
%
% Compatibility graph for pilots
% Nodes = pilots
% Arcs  = possible combinations (with scores)
%
%   1 ----30--- 2 ----27--- 3
%
%   | \       / |         / |
%   |  24   28  |        /  |
%   |   \   /   27     26   |
%   |           |      /    |
%   |     4     |     /    30
%  25           |    /      |
%   |   /   \   |   /       |
%   |  29    21 |  /        |
%   | /       \ | /         |
%
%   5 ---30---- 6 -----28-- 7
%
%     \         |         /
%      \        |        /
%       \       |       /
%        \      36     /
%         \     |     /
%         30    |   25
%           \   |   /
%            \  |  /
%             \ | /
%
%               8
%
%
% VARIABLES
%
% scores                     Scores for language and piloting skills
% arcs_out/in                For an arc i arcs_out(i) is its starting node
%                            and arcs_in(i) ts target node
% arcs_score                 Strength of an arc
%
% RESULTS
%
% Set PriLev to 2 for an interpretation of the results
% Result     =  composingflightcrewsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 21, 2005.   Last modified Feb 3, 2006.

function Result = composingflightcrewsEx(PriLev)

if nargin < 1
   PriLev = 1;
end

scores       = [ 20 14  0 13  0  0  8  8;...
      12  0  0 10 15 20  8  9;...
      0 20 12  0  8 11 14 12;...
      0  0  0  0 17  0  0 16;...
      18 12 15  0  0  0  8  0;...
      10  0  9 14 15  8 12 13;...
      0 17  0 11 13 10  0  0;...
      0  0 14  0  0 12 16  0;...
      0  0  0  0 12 18  0 18];

arcs_in    = [1 1 1 2 2 2 3 3 4 4 5 5 6 6 7]';
arcs_out   = [5 4 2 4 6 3 6 7 5 6 6 8 8 7 8]';

arcs_score = [25 24 30 28 27 27 26 30 29 21 30 30 ...
      36 28 25]';

Prob = composingflightcrews(scores, arcs_in, arcs_out, arcs_score);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1
   idx        = find(Result.x_k);
   for crew = 1:idx,
      id = idx(crew);
      disp(['crew ' num2str(crew) ' has pilots ' ...
            num2str(arcs_in(id)) ' and ' num2str(arcs_out(id))])
   end
end

% MODIFICATION LOG
%
% 051021 med   Created.
% 060113 per   Added documentation.
% 060125 per   Moved disp to end
% 060203 med   Updated print level

Scheduling flight landings

% function Result = schedulingflightlandingsEx(PriLev)
%
% Creates a TOMLAB MIP problem for scheduling flight landings
%
% SCHEDULING FLIGHT LANDINGS
%
% The plane movements in large airports are subject to numerous
% security constraints. The problem presented in this section consist
% of calculating a schedule for flight landings on a single runway.
% More general problems have been studied but they are fairly
% complicated (dynamic cases, for instance through planes arriving
% late, instances with several runways, etc.).
%
% Ten planes are due to arrive. Every plane has an earliest arrival
% time (time when the plane arrives above the zone if traveling at
% maximum speed) and a latest arrival time (influenced among other
% things by its fuel supplies). Within this time window the airlines
% choose a target time, communicated to the public as the flight
% arrival time. The early or late arrival of an aircraft with respect
% to its target time leads to disruption of the airport and causes
% costs. To take into account these cost and to compare them more
% easily, a penalty per minute of early arrival and a second penalty
% per minute of late arrival are associated with every plane. The
% time windows (in minutes from the start of the day) and the
% penalties per plane are given in the following table.
%
% Characteristics of flight time windows
% +-----------------+---+---+---+---+---+---+---+---+---+---+
% |Plane            |  1|  2|  3|  4|  5|  6|  7|  8|  9| 10|
% +-----------------+---+---+---+---+---+---+---+---+---+---+
% |Earliest arrival |129|195| 89| 96|110|120|124|126|135|160|
% |Target time      |155|258| 98|106|123|135|138|140|150|180|
% |Latest Arrival   |559|744|510|521|555|576|577|573|591|657|
% |Earliness penalty| 10| 10| 30| 30| 30| 30| 30| 30| 30| 30|
% |Lateness penalty | 10| 10| 30| 30| 30| 30| 30| 30| 30| 30|
% +-----------------+---+---+---+---+---+---+---+---+---+---+
%
% Due to turbulence and the duration of the time during which a plane
% is on the runway, a security interval has to separate any two
% landings. An entry in line p of column q in the following table
% denotes the minimum time interval (in minutes) that has to lie
% between the landings of planes p and q, even if they are not
% consecutive. Which landing schedule minimizes the total penalty
% subject to arrivals within the given time windows and the required
% intervals separating any two landings?
%
% Matrix of minimum intervals separating landings
%
% +--+--+--+--+--+--+--+--+--+--+--+
% |  | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
% +--+--+--+--+--+--+--+--+--+--+--+
% | 1| –| 3|15|15|15|15|15|15|15|15|
% | 2| 3| –|15|15|15|15|15|15|15|15|
% | 3|15|15| –| 8| 8| 8| 8| 8| 8| 8|
% | 4|15|15| 8| –| 8| 8| 8| 8| 8| 8|
% | 5|15|15| 8| 8| –| 8| 8| 8| 8| 8|
% | 6|15|15| 8| 8| 8| –| 8| 8| 8| 8|
% | 7|15|15| 8| 8| 8| 8| –| 8| 8| 8|
% | 8|15|15| 8| 8| 8| 8| 8| –| 8| 8|
% | 9|15|15| 8| 8| 8| 8| 8| 8| –| 8|
% |10|15|15| 8| 8| 8| 8| 8| 8| 8| –|
% +--+--+--+--+--+--+--+--+--+--+--+
%
% VARIABLES
%
% costs                      Cost or being late
% mintimes                   Minimal intervals between landings
% var1                       30 plus
% var2                       30 minus
%
% RESULTS
%
% For an interpretation of the results, set PriLev > 1, for example:
% Result = schedulingflightlandingsEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Oct 21, 2005.   Last modified Feb 3, 2006.

function Result = schedulingflightlandingsEx(PriLev)

if nargin < 1
   PriLev = 1;
end

costs       = [ 129 195  89  96 110 120 124 126 135 160;...
      155 258  98 106 123 135 138 140 150 180;...
      559 744 510 521 555 576 577 573 591 657;...
      10  10  30*ones(1,8);...
      10  10  30*ones(1,8)];

mintimes    = [  0  3 15 15 15 15 15 15 15 15;...
      3  0 15 15 15 15 15 15 15 15;...
      15 15  0  8  8  8  8  8  8  8;...
      15 15  8  0  8  8  8  8  8  8;...
      15 15  8  8  0  8  8  8  8  8;...
      15 15  8  8  8  0  8  8  8  8;...
      15 15  8  8  8  8  0  8  8  8;...
      15 15  8  8  8  8  8  0  8  8;...
      15 15  8  8  8  8  8  8  0  8;...
      15 15  8  8  8  8  8  8  8  0];

Prob = schedulingflightlandings(costs, mintimes);
Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1
   planes       = 10; % number of planes
   [times,idx]  = sort(Result.x_k(1:planes));
   late         = Result.x_k(planes*planes+2*planes+1:planes*planes+3*planes);
   early        = Result.x_k(planes*planes+1*planes+1:planes*planes+2*planes);
   for p = 1:planes,
      time  = times(p);
      plane = idx(p);
      if (late(plane) > 0.5),
         disp(['plane ' num2str(plane) ' will arrive minute ' ...
               num2str(time) ' (' num2str(late(plane)) ' minute(s) late)'])
      elseif (early(plane) > 0.5),
         disp(['plane ' num2str(plane) ' will arrive minute ' ...
               num2str(time) ' (' num2str(early(plane)) ' minute(s) early)'])
      else
         disp(['plane ' num2str(plane) ' will arrive minute ' ...
               num2str(time) ' (on time)' ])
      end
   end
end

% MODIFICATION LOG
%
% 051021 med   Created.
% 060113 per   Added documentation
% 060125 per   Moved disp to end
% 060203 med   Print level updated

Airline hub location

% function Result = airlinehublocationEx(PriLev)
%
% Creates a TOMLAB MIP problem for airline hub location
%
% AIRLINE HUB LOCATION
%
% 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
% Result.x_k 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
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2006 by Tomlab Optimization Inc., $Release: 5.1.0$
% Written Nov 7, 2005.   Last modified Feb 3, 2006.

function Result = airlinehublocationEx(PriLev)

if nargin < 1
   PriLev = 1;
end

frights       = [   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      = [   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;

Prob = airlinehublocation(frights, distance, hubs);

Result = tomRun('cplex', Prob, PriLev);

if PriLev > 1
   c       = 6;   % number of cities
   c_names = ['Atla';'Bost';'Chic';'Mars';'Nice';'Pari'];
   temp    = reshape(Result.x_k(1:c^4),c,c,c,c);
   hubs    = find(Result.x_k(c^4+1:c^4+c));

   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

Planning a flight tour

% function Result = planningaflighttourEx(PriLev)
%
% Creates a TOMLAB MIP problem for planning a flight tour
%
% PLANNING A FLIGHT TOUR
%
% A country in south-east Asia is experiencing widespread flooding.
% The government, with international help, decides to establish a
% system of supply by air. Unfortunately, only seven runways are
% still in a usable state, among which is the one in the capital.
%
% The government decides to make the planes leave from the capital,
% have them visit all the other six airports and then come back to
% the capital. The following table lists the distances between the
% airports. Airport A1 is the one in the capital. In which order
% should the airports be visited to minimize the total distance
% covered?
%
% Distance matrix between airports (in km)
%
% +--+---+---+---+---+---+---+
% |  | A2| A3| A4| A5| A6| A7|
% +--+---+---+---+---+---+---+
% |A1|786|549|657|331|559|250|
% |A2|668|979|593|224|905|   |
% |A3|316|607|472|467|   |   |
% |A4|890|769|400|   |   |   |
% |A5|386|559|   |   |   |   |
% |A6|681|   |   |   |   |   |
% +--+---+---+---+---+---+---+
%
% VARIABLES
%
% distance                   The distance matrix
%
% RESULTS
%
% For an interpretation of the results set PriLev > 1, for example:
% Result = planningaflighttourEx(2);
%
% REFERENCES
%
% Applications of optimization... Gueret, Prins, Seveaux
% http://web.univ-ubs.fr/lester/~sevaux/pl/index.php
%
% INPUT PARAMETERS
% PriLev       Print Level
%
% OUTPUT PARAMETERS
% Result       Result structure.

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2005 by Tomlab Optimization Inc., $Release: 5.0.0$
% Written Nov 7, 2005.   Last modified Nov 7, 2005.

function Result = planningaflighttourEx(PriLev)

if nargin < 1
   PriLev = 1;
end

distance      = [   0   786   549    657    331    559   250;...
      786     0   668    979    593    224   905;...
      549   668     0    316    607    472   467;...
      657   979   316      0    890    769   400;...
      331   593   607    890      0    386   559;...
      559   224   472    769    386      0   681;...
      250   905   467    400    559    681     0];

Prob = planningaflighttour(distance);

stop = 0;
n = size(distance,1);
while stop<100
   Result = tomRun('cplex', Prob, PriLev);
   % Find a subtour
   idx = zeros(n,n);
   idx(1,1:n) = [1:7];
   for i=1:n
      for j=2:n
         idx(j,i) = find(Result.x_k( (idx(j-1,i)-1)*n+1: idx(j-1,i)*n) ~= 0);
         if idx(j,i) == i
            break
         end
      end
   end
   shortmat = spones(idx);
   len = full(sum(shortmat,1));
   [val, idx2] = min(len);
   idx3 = idx(1:val, idx2);

   Aextra = zeros(1,Prob.N);
   for k=1:val-1
      Aextra(1,idx3(k)+n*(idx3(k+1)-1)) = 1;
   end

   Prob.A = [Prob.A;Aextra];
   Prob.b_L = [Prob.b_L;-inf];
   Prob.b_U = [Prob.b_U;1];
   Prob.mLin = Prob.mLin+1;
   Result.tour = idx(:,1);
   if val == n
      break
   end
   stop = stop + 1;
end

if PriLev > 1,
   a              =  7;                           % number of airports
   temp           = reshape(Result.x_k,a,a);      % reshape results
   not_home_again = true;                         % help to loop
   current_pos    = 1;                            % we start in 1
   route          = [];                           % initially empty
   route          = [route current_pos];          % add position
   while not_home_again,                          % loop if not home
      current_pos = find(temp(current_pos,:));    % go to next pos
      route = [route current_pos];                % add to route
      if current_pos == 1,                        % if home:
         not_home_again = false;                  %  stop loop
      end
   end
   disp(['Shortest route is: ' num2str(route)])
   disp(['               or: ' num2str(route(end:-1:1))])

end

% MODIFICATION LOG
%
% 051107 med   Created.
% 060116 per   Added documentation.
% 060125 per   Moved disp to end