Transport
and Telecommunication Vol.
18, no. 3, 2017
Transport
and Telecommunication, 2017, volume 18, no. 3, 234–239
Transport
and Telecommunication Institute, Lomonosova 1, Riga, LV-1019, Latvia
DOI
10.1515/ttj-2017-0021
ON
THE PROBLEM OF CONSTRUCTING ROUTES, PART II: METHODOLOGY AND
NUMERICAL EXAMPLE
TRANSLATED
AND EDITED BY ILYA GERTSBAKH AND TAO LIU
V.K.
Linis, M.S. Maksim
E-mail
address: sarma.line@gmail.com
We
consider a periodic aviation schedule which is a finite collection of
flights with given arrival/departure times. For this schedule, we
solve the problem of finding the minimal number of aircrafts needed
to carry out the flights. The crucial role in solving this problem is
played by so-called deficit function (DFs) defined as the difference
between departures and arrivals on interval [0,t] for each terminal.
Keywords:
deficit function, optimal chain decomposition, minimal fleet size,
centre problem
1. Problem
Description
Let
us assume that each local civil aviation company (LCAC) has a
schedule consisting of a list of flights categorized by destinations.
This list contains the type of the aircrafts, the frequency of
carrying out the
flights
for each particular destination, and the recommended departure time
t0
for each particular flight.
When
the LCAC is composing the schedule, the main problem is to make sure
that all flights in the project could be carried out by a minimal
number of aircrafts. This will guarantee the maximal number of flight
hours per each operating aircraft. The aircraft which remain "in
spare" could be used later for servicing new routes. In
practice, it is always possible to nominate for each flight not only
its best desirable departure
time t0
, but also a tolerance interval [ t0
−∆t, t0
+∆t] within which the flight can depart without causing economic
damage. It turns out that a small shifting of the departure times
within their tolerances allows to minimize the number of aircrafts
needed to carry out the schedule. The problem can be descripted as:
Given the preliminary timetable
(schedule) for one-type aircraft together with the desirable
departure times and their tolerances, work out the final version of
the schedule that would provide (1) carrying out all flights within
their given tolerances and (2) the minimal possible number of
aircrafts in operation involved.
In addition, for each "physical"
aircraft in the schedule, there should be determined the so-called
turnover route,
i.e., the periodic sequence of flights performed by this aircraft,
providing periodic aircraft
return to its main
(base) airport.
2. Minimal
Number of Aircrafts Required to Perform the Planned Schedule
2.1.
Notations
The schedule consists of a set of
flights numbered from 1 to R
. Each flight has a departure and an arrival airport. The airports
are denoted by the letters a
, b,
c
,... Let A
be the set of all airports. Each flight is denoted by the following
four-tuple:
a
d(
r
)
,
ba(
r
)
,
t d(
r
)
,
l(
r
)
,
|
(1)
|
| where a,
b A
are airports, indices d
and |
a denote
the departure and arrival, respectively,
td
is the
|
| departure time, l
is the flight duration and r |
is
the flight number.
|
It is assumed that all flights
must be carried out during a fixed time interval T
, where this interval can be 24 hrs, or week or a month. We assume
that the following conditions are fulfilled:
| 0 t
d(
r
)
T
, l
(
r
)
T
, r
1, 2,..., R
. |
(2)
|
The
arrival time of the r
-th flight is given by
|
|
234
Unauthenticated
Download
Date | 7/1/17 11:04 AM
Transport
and Telecommunication
|
Vol. 18, no.
3, 2017
|
t
a(
r
)
|
t
d(
r
)
l(
r
)
, if
t a(
r
)
T , and
|
(3)
|
t
a(
r
)
|
t
d(
r
)
l (
r
)
T , if
t a(
r
)
T.
|
(4)
|
|
Further,
we will denote the r
-th flight by
|
|
(
r
) a
d(
r
)
, ba(
r
)
, t
d(
r
)
, l
(
r
)
.
|
(5)
|
|
It will be
assumed that there are no coincidences among the set of arrival
and departure times and
|
no
one of them is equal to 0 or T
.
|
|
|
The
upper part of Figure 1 presents a picture of a schedule. The
flight r
|
is shown by a
segment
|
with
the beginning at time td(
r
)
and the end at ta(
r
)
.
Figure
1. Upper
part: the original schedule (before shifting flight departure times);
lower
part: the corresponding characteristic functions
235
Unauthenticated
Download
Date | 7/1/17 11:04 AM
0
t
T
Transport and
Telecommunication Vol.
18, no. 3, 2017
2.2.
Fleet size formula
Let us find out what the minimal
number of aircrafts needed is so as to carry out the given set of
flights. To carry out the r
-th flight, departing from v
there should be an aircraft available at airport v
at
the instant td(
r
)
. After the departure takes place, the number of aircrafts in v
will decrease by one. This number will increase by one at the instant
of any flight arrival to v
.
Let
us construct for each airport v
its stepwise
(or characteristic)
function fv
t , v A
,
0
t
T
which is defined
for each
t
as the difference
between the number of departures from
v
and the
number of arrivals
to v
on the interval [0, t
]. See Fig. 1.
Suppose that at the moment t
0
there are Cv
aircrafts on the ground in v
. Then at time t
there will be Cv
f
v
t
aircrafts in v
. Obviously, that in order to carry out all flights departing from v
it is necessary and sufficient that the following condition should be
fulfilled:
-
This
will be satisfied if we put C
v max
f
v
t
.
To make possible all other flights, it is necessary
and sufficient to fulfil the
condition (6) for all v
A . In
addition, at t
0
some number D
of aircrafts are in the air. Taking into account that at any time the
number of aircrafts on the ground and in the air is the same, we
arrive at the following statement:
The
minimal number of aircrafts needed for carrying out the schedule
γ(1), ..., γ(R) equals
-
v
A
0 t
T
3. Constructing
Closed Flight Chains (Cyclic Diagrams)
3.1.
Assumptions
It is assumed that the collection
γ(1), ..., γ(R) has the natural "balance" property that
the number of arrivals to each airport is equal to the number of
departures from it. It means that there is no aircraft dropout from
the schedule.
3.2.
Minimal Complete Chain System
Let us call a chain
the following ordered sequence of flights z
=<
γ(l1),
γ(l2),
..., γ(ln),
having the following closure
property:
| b
l
n |
a
l1
|
,
b
l1
|
a
l
2
|
,...,
b
l
n
1
|
aln
.
|
(8)
|
a
|
d
|
a
|
d
|
a
|
d
|
|
Often,
a chain is called cyclic
diagram.
The property of a chain is that
its flights γ(1)
, ...,
γ(n)
can be performed by the same "physical" aircraft. This
aircraft will periodically circulate along this chain. The whole
schedule γ(1),
..., γ(n)
can be decomposed into nonintersecting subsets, each of which itself
is a chain. This can be easily proved by using the conditions stated
in subsection 3.1.
We will call a system (a set) of chains complete
if each of the flights γ(1),
..., γ(n)
is present in one and only one chain.
Let us consider a chain z
and denote by Lz
the number of T
periods, which a single aircraft needs to carry out the whole cycle
along this chain. Let us call Lz
the weight
of the chain z.
If Lz
equals integer
m,
and all flights of this chain are carried out during one period [0,
T ], then
m "physical"
aircrafts should
circulate along this
chain. These aircrafts should perform the same flight m
times, with time interval T.
Therefore, the sum of all the weights of all chains L=
∑
is equal to the total number of aircrafts which
carry
out the schedule. This system (set) of chains is called minimal,
if
-
236
Unauthenticated
Download
Date | 7/1/17 11:04 AM
Transport and
Telecommunication Vol.
18, no. 3, 2017
3.3.
Algorithm for Constructing the Minimal Complete Chain System
Let us describe the algorithm for
constructing the minimal
complete chain system
(MCCS). Take any flight γ(l1)
arriving at airport b
at time t1
and join to it the nearest
flight γ(l2)
departing from b
at time
td.The
"nearest" means the following: either it is the flight
whose departure from
b is
in the interval [t1,
T],
or, if such does not exist, then
it is the first departure from b
after t
= 0 on the next period. Similarly, we join the flight γ(l3)
to γ(l2),
and so on, until the chain closes, i.e. the closest departure after
arrival of γ(ln)
will
be the departure by γ(l1).
Finally, all flights of one chain
are removed from the schedule, and the similar procedure is repeated
for the remaining set of flights, until the whole schedule is
exhausted.
3.4.
Extension of the Minimal Complete Chain System
It follows from subsection 3.3
that constructing the MCCS can be made in several ways. Suppose there
are two MCCS’s, containing M1
and M2
chains, respectively, and M1<M2
It is natural to prefer the
second MCCS with the largest M
-value because this MCCS will consist of chains which, on the
average, are shorter.
4. Constructing
Closed Chains to Visit the Base Airports
Let A1⊂A
be the set of airports equipped with special facilities. We call them
base airports.
We
would like to construct a system
of chains in such a way that every chain would visit an airport
belonging to A1.
More specifically, we want to design an MCCS in which every chain
visits a base airport. Let us
present
without proof the condition guaranteeing such property.
Let
us find for each a∈A,
the time segments which are the "hollow-zones" between two
adjacent maximums of the characteristic function fa(t).
Let these zones be numbered in cyclic order as a1,
a2,
...,
am.
Suppose that there is a departure of a flight from zone
a1
which
has the arrival in some hollow zone
bj of
airport b.
Then we say that there is a transition from a1
to bj.
Let E1
be the set of all hollow-zones into which there is a transition from
a1.
Let us complement it by the set E2
of all hollow-zones into which the transition from E1
is possible, and so on. Eventually, we either will exhaust all hollow
zones, or not. In
the last case, we repeat the
similar procedure for the remaining hollow- zones. This will result
in the partition of the whole set of hollow-zones into sets B1,
B2,
..., Bs
which have the following property: the
hollow-zones within each Bj
communicate with each other, while the hollow-zones from different Bj
-s do not. Now we formulate without proof the following claim:
In order to construct a MCCS
with each chain visiting a base, it is necessary and sufficient that
each set Bj, j = 1, ..., s would contain a hollow-zone belonging to a
base airport.
5. Algorithm
for Solving the Routing Problem
The theoretical considerations
developed in the previous sections allow to propose an algorithm for
solving the problem of route construction. This solution has several
stages.
For each type of aircraft, LCAC
composes a preliminary list of daily flights L*=(γ
∗
(1), ...,
γ
∗
(R∗))
which have to be carried out in a period [0,
T]. Typically, this
period is taken as 7 days (one week).
L∗
is complemented by
non-daily flights, if there are such. These flights are
approximately
uniformly positioned
over the week period.
For each flight, the desirable
departure time is nominated. If the flight has several legs, these
times take into account the minimal time needed to stay on the
ground between the arrival and the departure.
The "ideal"
departure/arrival times are coordinated with the operation time for
each airport. These times are chosen also by taking into account the
passenger demand and passenger convenience. In addition, each
departure time t0
is supplied with a tolerance ∆t,
so that the departure can be within the interval [t0−∆t,
t0
+ ∆t].
After completing the stages b-e,
LCAC arrives at the complemented list of flights L
= (γ(1),
..., γ(R))
which contains all daily and non-daily flights, together with their
arrival/departure times. This list is
237
Unauthenticated
Download
Date | 7/1/17 11:04 AM
Transport and
Telecommunication Vol.
18, no. 3, 2017
used to determine the
characteristic
functions fa(t)
for each a∈A.
Finally, the minimal number of aircrafts Q
to carry out the schedule is determined.
The departure times of certain
flights are changed within their tolerances in order to lower
the maxima of the characteristic functions. As it follows from
Section 2, this guarantees the decrease
of Q.
It is essential that repositioning of flight departure times
involves only the flights which are
located in the
neighbourhood of fa(t)
maxima.
After the decrease of Q
by one unit has been achieved, the resulting MCCS is checked whether
it satisfies the base principle (see section 4). If yes, the stage f
can be repeated.
Using the algorithm described in
Section 3, the MCCSs are constructed and their best version,
according to the criterion of subsection 3.4,
is selected.
6. An
Example
Let us consider an example that
illustrates in somewhat simplified form of the algorithm described in
Section 5.
The schedule is presented on the
upper part of Fig. 1. It contains 22 daily flights shown by line
segments numbered from 1 to 22. All flights have their arrival and
departure times between 5 am and 24 (12 pm). The arrival/departure
airports are shown by letters at the end points of the segments. The
length of each segment represents the flight time plus the necessary
time on the ground to prepare the aircraft to the next flight and
passenger boarding. The right end of each segment has an arrow
indicating the instant when the next departure can be carried out.
All tolerances of departure times
are ±2 hrs. The earliest departure time is 5 am and the latest
arrival time is 10 pm.
The lower part of Fig. 1 shows
the characteristic functions for all five airports a,
b, d, c, e in the
schedule. It is seen that D
= 0, max f
v
t
10 .
v
A
0 t
24
Now let us modify the schedule in
order to lower the maximum areas of the characteristic functions.
First we take fc(t)
that haves the narrowest maximum areas. To "erase" the left
maximum, we
shift the first flight to the
left by half an hour (denote it as No.1
⇐
0.5hr).
The erased left maximum is shown by grey colour. To erase the second
maximum, we carry out the shifting of No.8
⇒
0.5hr.
Note that doing these shiftings results in changes of fa(t)
and fb(t)
because the shifted flights had
arrival/departure from these
airports. As the result, fa(t)
increases in the interval [5:00,
5:30] and fb(t)
increases in the interval [20:30,
21:00]. We see that this does not affect the maxima of fa
and fb.
To erase the left maximum area of
fd(t)
we shift No.14
⇒
1hr,
and to erase the right maximum
area we need three shiftings:
No.12
⇒
1hr,
No.13
⇐
0.5hr
and No.20
⇐
0.5hr.
These shiftings will cause changes of fa,
fb, fc shown by dotted
colour. The maximum zones of fa(t)
are erased by the shiftings of
No.19
⇒
1hr,
No.6
⇐
0.5hr
and
No.7
⇒
1hr.
The new positions of the shifted
flights are shown by dotted lines. After carrying out all the above
shiftings we have achieved the decrease of Q
by 3 units and now Q
= 7. This process can be continued further, and we omit the details.
Fig. 2 demonstrates the final result. Now fe(t)
= 0 because the arrival
times at e
coincide with the corresponding departure times from e.
The value of Q
is now equals to 5, a considerable
decrease comparing to
its initial value of 10.
Now let us construct the MCCS.
Start with flight No.19.
Joining the nearest departure, we obtain the chain:
No.19
→ No.17
→ No.18
→ No.3
→ No.6.
with
a weight of 1. See Fig. 2.
Starting
with flight 5, we will obtain the chain:
No.5
→No.20
→No.13
→No.12
→No.9
→No.22
→No.21
→No.15
→No.16.
Its
weight is equal to 2. The third chain, also with a weight of 2, is
the following:
No.1
→ No.2
→ No.7
→ No.4
→ No.11
→ No.14
→ No.8
→ No.10.
It can be seen now that each of
the above chains visits airport a.
If a
is a base, then we have obtained an MCCS in which all aircraft will
visit the base airport.
238
Unauthenticated
Download
Date | 7/1/17 11:04 AM
Transport and
Telecommunication Vol.
18, no. 3, 2017
Figure
2. Upper
part: final position of the flights after shifting departure times;
lower part: the corresponding characteristic functions
7. Concluding
Remark
Let us note that solving the
routing problem can be made at various levels. That is, it can be
solved for a single local airline company or simultaneously for
several local companies exploiting identical (mutually exchangeable)
aircrafts. Certainly, the efficiency of the described methodology of
this work will increase with the increase of the number of flights
and number aircrafts employed.
