cw

1. “HEARTFIELD-JACKSON” ORO UOSTO APTARNAVIMO PRIORITETAS

Rimantas Bosikis

2. Problema

Atlantos „Hartsfield-Jackson“ oro uostas kasdien priima šimtus
skrydžių, dalis jų vėluoja, tai sukelia:
• Spūstis
• Keleiviai praleidžia jungiamuosius skrydžius
• Dispečeriai turi galvoti kuriuos lėktuvus aptarnauti pirmiausiai
Tikslas
Sukurti sistemą kuri tvarko vėluojančius skrydžius pagal prioritetą,
Tai reiškia labiausiai vėluojantys skrydis aptarnaujamas
pirmiausia.

3. Duomenys

Naudojami JAV „Bureau of Transportation Statistics“ skrydžių
duomenys (filtruoti tik ATL atvykimai, 1 diena):
• Oro linija
• Lėktuvo registracijos numeris
• Atvykimo laikas
• Atvykimo vėlavimas minutėmis

4. ADT pasirinkimas

Problemai spręsti pasirinkau Priority Queue ADT,
naudodamas Max Heap struktūrą.
Kodėl?
Nes leidžia nustatyti prioritetą kurį lėktuvą
aptarnauti pirmiausia.
Struktūra
Įterpimas
Max išėmimas
Max peržiūra
List
O(1)
O(n)
O(n)
Queue
O(1)
Netinkamas (FIFO)
Netinkamas (FIFO)
Stack
O(1)
Netinkamas (LIFO)
Netinkamas (LIFO)
Max Heap
O(log n)
O(log n)
O(1)

5. Programos veikimas

Vėlavo Linija
Reg Nr
Uostas
Laikas
Vėlavo Linija
Reg Nr
Uostas
Laikas
132
DL
N904DN
ATL
00:05
133
DL
N904DN
ATL
00:05
73
UA
N69847
ATL
00:04
81
NK
N613NK
ATL
00:42
79
WN
N8769Q
ATL
00:08
80
WN
N8769Q
ATL
00:08
43
UA
N76514
ATL
00:23
74
UA
N69847
ATL
00:04
28
NK
N677NK
ATL
00:25
29
NK
N677NK
ATL
00:25
15
F9
N376FR
ATL
00:30
16
F9
N376FR
ATL
00:30
11
MQ
N209NN
ATL
00:41
12
MQ
N209NN
ATL
00:41
44
UA
N76514
ATL
00:23
+1min
+
81
NK
N613NK
ATL
00:42

6. Programos veikimas

7. Programos veikimas

Kiekvieną minutę sistema patikrina ar atvyko nauji skrydžiai ir
įterpia juos į Heap. Jau laukiantiems skrydžiams vėlavimas
padidinamas 1 minute, taip ilgiau laukiantys skrydžiai tampa
prioritetiniai.
Kiekvienos valandos pabaigoje sistema aptarnauja dalį labiausiai
vėluojančių skrydžių.

8. Išvados

• MaxHeap struktūra efektyviai sprendžia aptarnavimo
prioretizavimo problemą.
• Labiausiai vėluojantis visada aptarnaujamas pirmiausia
• Įterpimas ir išėmimas O(log n) leidžia sistemai veikti greitai su
dideliais kiekiais skrydžių.
Tobulinimo galimybės
• Prioritetą nustatyti panaudojant papildomai kitas reikšmes
(keleivių skaičius ir vėlavimas)

9. “HEARTFIELD-JACKSON” ORO UOSTO APTARNAVIMO PRIORITETAS

Rimantas Bosikis