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

master's thesis

• Title (english): A Heuristic Algorithm for Flight Scheduling in a Pilot Training Program
• Author: Lucija Josipa Šimić
• Mentor: Lea Skorin-Kapov (mentor)
• Committee member: Lea Skorin-Kapov (predsjednik povjerenstva)
• Committee member: Nina Skorin-Kapov (član povjerenstva)
• Committee member: Mirko Sužnjević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-02-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: raspored obuke letenja; optimizacija rasporeda; heurističke metode optimizacije; heuristički algoritmi; pretraživanje velikog susjedstva; simulirano kaljenje; pretraživanje susjedstva
• Keywords (english): Flight Training Scheduling; Scheduling Optimization; Heuristic Optimization Methods; Heuristic algorithms; Large Neighbourhood Search; Simulated Annealing; Neighbourhood Search
• Language: english
• URN:NBN: urn:nbn:hr:168:000150
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:35:23