Heuristički algoritam za raspoređivanje letova u programu obuke pilota

diplomski rad

• Naslov (engleski): A Heuristic Algorithm for Flight Scheduling in a Pilot Training Program
• Autor: Lucija Josipa Šimić
• Mentor: Lea Skorin-Kapov (mentor)
• Član povjerenstva: Lea Skorin-Kapov (predsjednik povjerenstva)
• Član povjerenstva: Nina Skorin-Kapov (član povjerenstva)
• Član povjerenstva: Mirko Sužnjević (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-02-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Kreiranje rasporeda obuke letenja je složen zadatak zbog velikog broja mogućih varijabli i traženih uvjeta. Stvaranje rasporeda koji ispunjava sve zahtjeve i ograničenja može biti izazovno, osobito kada se koriste tradicionalne, egzaktne metode. Za rješavanje ovog problema, u ovom radu koristimo heurističke metode optimizacija, kojima je cilj pronaći valjana rješenja, približna optimalnima u kratkom vremenskom rasponu.

Fokus ovog rada je razviti prilagođeni raspored obuke letenja za Španjolsku vojnu zrakoplovnu akademiju, koristeći heurističke algoritme. U ovu svrhu smo prošli srodnu literaturu i pozadinu heurističkih algoritama i razvili novi FS-LNS-SA algoritam za rješavanje ovog problema. Algoritam koristi kombinaciju algoritama pretraživanja velikog susjedstva i simuliranog kaljenja za poboljšanje početnog rješenja.

U većini slučajeva, algoritam FS-LNS-SA je uspio pronaći rješenja koja su bila blizu optimalnih generiranih cjelobrojnim linearnim programiranjem (ILP), dok je također uspio pronaći rješenja za veće instance koje se nisu mogle riješiti od strane ILP-a u razumnom vremenskom rasponu. Ovo pokazuje potencijal heurističke optimizacije za rješavanje složenih problema raspoređivanja.

Sažetak (engleski)

Flight training scheduling is a complex task due to the diverse range of variables and conditions involved. Creating a schedule that meets all requirements and constraints can be challenging, especially when using traditional, exact methods. To tackle this challenge, this thesis employs heuristic optimization methods, which aim to find feasible near-optimal solutions in a short amount of time.

The focus of this thesis is to develop a customised flight training schedule for the Spanish Air Force Academy, using heuristic algorithms. We go over related literature and heuristic algorithms background and develop a new FS-LNS-SA algorithm for solving this problem. The algorithm uses a combination of Large Neighbourhood Search and Simulated Annealing algorithms to improve the initial solution. 

In a majority of cases, the FS-LNS-SA algorithm was able to find solutions that were close to the optimal ones generated by Integer Linear Programming (ILP), while also being able to find a solution for larger instances that could not be solved by ILP in a reasonable amount of time. This demonstrates the potential of heuristic optimization for addressing complex scheduling problems.

• Ključne riječi: raspored obuke letenja; optimizacija rasporeda; heurističke metode optimizacije; heuristički algoritmi; pretraživanje velikog susjedstva; simulirano kaljenje; pretraživanje susjedstva
• Ključne riječi (engleski): Flight Training Scheduling; Scheduling Optimization; Heuristic Optimization Methods; Heuristic algorithms; Large Neighbourhood Search; Simulated Annealing; Neighbourhood Search
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:000150
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:35:23