Heuristički algoritam za raspoređivanje zračnih resursa tijekom gašenja šumskih požara velikih razmjera

diplomski rad

• Naslov (engleski): A Heuristic Algorithm for Scheduling Aerial Resources for the Extinction of Large-Scale Wildfires
• Autor: Luka Mesarić
• Mentor: Lea Skorin-Kapov (mentor)
• Član povjerenstva: Lea Skorin-Kapov (predsjednik povjerenstva)
• Član povjerenstva: Marko Čupić (član povjerenstva)
• Član povjerenstva: Nina Skorin-Kapov (č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: 2022-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Pri gašenju šumskih požara velikih razmjera ključno je kvalitetno i brzo raspoređivanje zračnih resursa. U ovom radu predložen je heuristički algoritam za planiranje rasporeda letova. Algoritam se temelji na postojećem cjelobrojnom linearnom modelu usklađenom sa španjolskim zakonima o zračnom prometu. Heuristički algoritam implementiran je u programskom jeziku C++ i uspoređen s modelom izrađenim korištenjem cjelobrojnog linearnog programiranja (ILP). Iako ILP može pronaći optimalna rješenja, nije skalabilan za korištenje na velikim problemima. Heuristički algoritam pronalazi optimalna ili gotovo optimalna rješenja za male probleme, a za velike probleme konzistentno nadmašuje ILP rješenja pronađena unutar dva sata. Nadalje, heuristički algoritam iznimno je skalabilan i izvodi se u manje od pet minuta za sve probleme, zbog čega bi bio odlično primjenjiv u dinamičnom okruženju tijekom suzbijanja požara.

Sažetak (engleski)

Expeditiously scheduling aerial resources is of vital importance when it comes to fighting large-scale wildfires. In this thesis, a heuristic search algorithm is proposed to solve the resource scheduling and assignment problem, based on an existing integer linear model which meets Spanish aviation regulations. The heuristic algorithm is implemented in software using the C++ programming language. A comparison is made between the proposed algorithm and the integer linear programming (ILP) model. Although the ILP gives optimal solutions, it is not scalable to larger instances. Results show that the heuristic algorithm obtains optimal or near-optimal solutions for smaller instances, and consistently outperforms ILP solutions obtained after two hours of execution time for larger instances. Furthermore, the heuristic is highly scalable, running in under five minutes for all cases, making it quite applicable in a dynamic firefighting environment.

• Ključne riječi: gašenje požara iz zraka; šumski požar; raspoređivanje; heuristički algoritam; kombinatorička optimizacija; GRASP; pretraživanje velikih susjedstva; simulirano kaljenje
• Ključne riječi (engleski): aerial firefighting; wildfire; scheduling; heuristic algorithm; combinatorial optimization; GRASP; large neighborhood search; simulated annealing
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:346028
• 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-01-14 09:31:33