Mbot at 13:33, 8 November 2011

2011-11-08T13:33:35Z

← Older revision		Revision as of 09:33, 8 November 2011
Line 166:		Line 166:
	<pre>		<pre>
	Problem type appears to be: mip		Problem type appears to be: mip
	Time for symbolic processing: 0.~~81966~~ seconds		Time for symbolic processing: 0.80909 seconds
	Starting numeric solver		Starting numeric solver
	===== * * * =================================================================== * * *		===== * * * =================================================================== * * *
Line 179:		Line 179:

	FuncEv 160 Iter 42		FuncEv 160 Iter 42
	CPU time: 0.~~140401~~ sec. Elapsed time: 0.~~046000~~ sec.		CPU time: 0.015600 sec. Elapsed time: 0.015000 sec.
	plane 3 will arrive minute 98 (on time)		plane 3 will arrive minute 98 (on time)
	plane 4 will arrive minute 106 (on time)		plane 4 will arrive minute 106 (on time)

Mbot at 21:24, 2 November 2011

2011-11-02T21:24:48Z

← Older revision		Revision as of 17:24, 2 November 2011
Line 9:		Line 9:
	Characteristics of flight time windows		Characteristics of flight time windows

			<pre>
	+-----------------+---+---+---+---+---+---+---+---+---+---+		+-----------------+---+---+---+---+---+---+---+---+---+---+
	\|Plane \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\| 10\|		\|Plane \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\| 10\|
Line 18:		Line 19:
	\|Lateness penalty \| 10\| 10\| 30\| 30\| 30\| 30\| 30\| 30\| 30\| 30\|		\|Lateness penalty \| 10\| 10\| 30\| 30\| 30\| 30\| 30\| 30\| 30\| 30\|
	+-----------------+---+---+---+---+---+---+---+---+---+---+		+-----------------+---+---+---+---+---+---+---+---+---+---+
			</pre>

	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?		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?
Line 23:		Line 25:
	Matrix of minimum intervals separating landings		Matrix of minimum intervals separating landings

			<pre>
	+--+--+--+--+--+--+--+--+--+--+--+		+--+--+--+--+--+--+--+--+--+--+--+
	\| \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\|10\|		\| \| 1\| 2\| 3\| 4\| 5\| 6\| 7\| 8\| 9\|10\|
Line 37:		Line 40:
	\|10\|15\|15\| 8\| 8\| 8\| 8\| 8\| 8\| 8\| –\|		\|10\|15\|15\| 8\| 8\| 8\| 8\| 8\| 8\| 8\| –\|
	+--+--+--+--+--+--+--+--+--+--+--+		+--+--+--+--+--+--+--+--+--+--+--+
			</pre>

	==Variables==		==Variables==

Mbot: Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== The plane movements in large airports are subject to numerous security constrai..."

2011-11-02T21:01:55Z

Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== The plane movements in large airports are subject to numerous security constrai..."

New page

{{Part Of Manual|title=the TomSym Manual|link=[[TomSym|TomSym Manual]]}}

==Problem description==

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

==Reference==

Applications of optimization... Gueret, Prins, Seveaux

<source lang="matlab">
% 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.
</source>

==Problem setup==

<source lang="matlab">
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];

p = size(costs,2);
q = p;

prec = tom('prec',p,q,'int');
land = tom('land',p,1,'int');
early = tom('early',p,1,'int');
late = tom('late',p,1,'int');

BIG = 1e4;

% All variables are integers.
bnds = {costs(1,:)' <= land <= costs(3,:)';
0 <= prec <= 1;
0 <= early <= costs(2,:)'-costs(1,:)';
0 <= late <= costs(3,:)'-costs(2,:)'
prec(1:p+1:p^2) == 0};

% q is less than p
con1 = [];
for i=2:p
con1{i-1} = {prec(i,i+1:end) == 0};
end

% Disjunctive constr 1
con2 = [];
counter = 1;
for i=1:p-1 % q is less than p
for j=i+1:q
con2{counter} = {land(i) + mintimes(i,j) <= ...
land(j) + BIG*prec(j,i)};
counter = counter + 1;
end
end

% Disjunctive constr 2
con3 = [];
counter = 1;
for j=1:p-1 % p is less than q
for i=j+1:p
con3{counter} = {land(i) + mintimes(i,j) <= ...
land(j) + BIG*(1-prec(i,j))};
counter = counter + 1;
end
end

% Landing constraint
con4 = {land == costs(2,:)' - early + late};

% Objective
objective = costs(4,:)*early + costs(5,:)*late;

constraints = {bnds, con1, con2, con3, con4};
options = struct;
options.solver = 'cplex';
options.name = 'Scheduling Flight Landings';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
planes = 10; % number of planes
[tim,idx] = sort(sol.land);
late = sol.late;
early = sol.early;
for p = 1:planes,
time = tim(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
% 090308 med Converted to tomSym
</source>

<pre>
Problem type appears to be: mip
Time for symbolic processing: 0.81966 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31
=====================================================================================
Problem: --- 1: Scheduling Flight Landings f_k 700.000000000000000000
f(x_0) 0.000000000000000000

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

FuncEv 160 Iter 42
CPU time: 0.140401 sec. Elapsed time: 0.046000 sec.
plane 3 will arrive minute 98 (on time)
plane 4 will arrive minute 106 (on time)
plane 5 will arrive minute 118 (5 minute(s) early)
plane 7 will arrive minute 126 (12 minute(s) early)
plane 6 will arrive minute 134 (1 minute(s) early)
plane 8 will arrive minute 142 (2 minute(s) late)
plane 9 will arrive minute 150 (on time)
plane 1 will arrive minute 165 (10 minute(s) late)
plane 10 will arrive minute 180 (on time)
plane 2 will arrive minute 258 (on time)

</pre>

TomSym Scheduling Flight Landings - Revision history

Mbot at 13:33, 8 November 2011

Mbot at 21:24, 2 November 2011

Mbot: Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== The plane movements in large airports are subject to numerous security constrai..."