Models Air transport

From TomWiki

Jump to: navigation, search

Notice.png

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

Contents

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
Personal tools