This thesis explores the use of a column generation method, a subgradient method, and a logic-based Benders decomposition method on a minimized makespan K-rural postman problem. The K-rural postman problem here describes a search and rescue mission using multiple identical unmanned aerial vehicles (UAVs) to cover an area, represented as a complete graph. Each decomposition method has a separate problem for each UAV. In the subgradient and column generation case, a heuristic is used to find an improved upper bound for the makespan. This upper bound can in turn be used to decrease the feasible regions of the subproblems. Moreover, because the subproblems are slow to solve, a maximum calculation time is used, resulting in a feasible solution and a lower bound for each subproblem. These two modifications to the decomposition methods result in a non-standard behaviour. Multiple fictional problem instances of different sizes and numbers of UAVs were generated and used for evaluating the methods. A maximal time limit is used in these instances. We conclude that solving the original, non-decomposed, problem for smaller instances with a standard solver is faster and gives better results than the decomposition methods. For larger instances, solving the non-decomposed model led to memory issues on several occasions. However, the suggested subgradient and column generation methods can solve every problem. The logic-based Benders decomposition method performed best on instances with multiple UAVs, but had issues when fewer UAVs are utilized. / Den här masteruppsatsen utforskar användningen av en kolumngenereringsmetod, en subgradientmetod och en logikbaserad Benders dekompositionsmetod på en variant av lantbrevbärarproblemet. Vårat brevbärarprolem beskriver sök- och räddningsuppdrag där $K$ drönare används för att avsöka ett område med målfunktionen att minimera flygtiden för den långsammaste drönaren. Varje dekompositionsmetod använder sig av ett problem för varje drönare. I subgradient- och kolumngenereringsmetoden användes en heuristik för att hitta en bättre övre begränsning till drönarnas flygtid. Den förbättrade övre begränsningen kunde sedan användas för att minska det tillåtna området för de mindre problemen. Eftersom de mindre problem var svårlösta, användes en maximal beräkningstid vilket resulterade i att en tillåten lösning och undre gräns gavs för varje mindre problem. Dessa två modifikationer resulterade i icke typiska beteenden. Metoderna utvärderades på flera fiktiva testinstanser av olika storlekar där antalet drönare varierar. En tidsbegränsning används på varje probleminstans. Slutsatserna från uppsatsen är de original brevbärare problemet ger bäst lösning och snabbast lösningstid i de mindre instanserna. Vid lösning av större probleminstanser, gav original problemet flerfaldiga gånger minnesproblem. Subgradient- och kolumngenereringsmetoden kunde däremot lösa varje probleminstans inom tidsbegränsningen, vilket gjorde de mer pålitliga. Logikbaserade Benders dekompositionsmetoden presterade bättre i instanser med flera drönare, men stötte på problem i instanser med färre drönare.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-205109 |
| Date | January 2024 |
| Creators | Tondel, Gero Kristoffer |
| Publisher | Linköpings universitet, Tillämpad matematik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds