Primjena metaheurističkih algoritama za probleme raspoređivanja letova

master's thesis

• Title (english): Application of Metaheuristic Algorithms for Flight Scheduling Problems
• Author: Izabela Šimić
• Mentor: Lea Skorin-Kapov (mentor)
• Committee member: Lea Skorin-Kapov (predsjednik povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Committee member: Nina Skorin-Kapov (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-06-28, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem raspoređivanja letova za treniranje sadrži mnoga ograničenja koja otežavaju pronalazak optimalnih rješenja. Dosada, većinski fokus prilikom rješavanja ovog problema je bio na egzaktnim metodama koje, iako garantiraju optimalno rješenje, ne garantiraju da će se uopće izvršiti do kraja i pronaći rješenje kod većih i kompleksnijih scenarija. Ovaj rad prikazuje pokušaj rješavanja jednog takvog problema koristeći heurističke metode. Odabrane metode su algoritmi simultanog kaljenja, lokalne pretrage te multi start nasumični pohlepni algoritam. U ovisnosti o pojedinom scenariju, rješenja dobivena kroz algoritme su ispala dovoljno dobra, no u mnogo kraćem vremenu nego što bi trebalo egzaktnim metodama. Algoritmi se također mogu primijeniti na veće instance koje egzaktni algoritmi ne mogu ni riješiti.

Abstract (english)

The Flight Training Scheduling problem is a heavily constrained problem that schedulers of different Flight Training institutions deal with every day. In order to automatize the problem-solving process, most of the research turned to exact methods such as Linear Programming in order to solve it. Even though the exact methods guarantee optimal solutions if they manage to solve the problems, for heavily constrained and big instances they usually cannot even solve them in a reasonable amount of time. For that reason, the focus of this Master Thesis was the heuristic approach to FTSP. The chosen algorithms were Simulated Annealing, Neighborhood Search, and Multi-start Randomized Greedy Algorithm. Depending on the instance, the results obtained were close enough to the results of the exact method while also being obtained much faster. The algorithms can also be applicable to bigger, more realistic instances that the ILP method did not manage to solve.

• Keywords: Problem raspoređivanja letova za treniranje; heurističke metode; heuristike; simultano kaljenje; pohlepni algoritam; GRASP; pretraživanje susjedstva
• Keywords (english): Simulated Annealing; Neighborhood Search; GRASP; Greedy Algorithm; Flight Training Scheduling Problem; Flight Scheduling Problem; heuristics; heuristic methods
• Language: english
• URN:NBN: urn:nbn:hr:168:792062
• 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-01-14 21:46:40