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

master's thesis

• Title (english): A Heuristic Algorithm for Scheduling Aerial Resources for the Extinction of Large-Scale Wildfires
• Author: Luka Mesarić
• 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

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.

Abstract (english)

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.

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