Dubins Team Orienteering Problem in a post-earthquake scenario
- Zusatzfeld:
The Dubins Team Orienteering Problem (DTOP) extends the Orienteering Problem (OP) by considering multiple Dubins vehicles. Dubins vehicles are curvature-constrained vehicles and can be modeled by using Dubins paths. A new integer linear program of the DTOP is formulated and solved optimally to obtain exact results. If it is necessary to provide good solutions within a low response time, heuristic solution approaches usually outperform exact approaches. Hence, in this study an adaptive large neighborhood search (ALNS) heuristic is developed to solve the DTOP. The performance of the ALNS is compared to benchmark solutions. Further, this work provides the first benchmark solutions for the DTOP case based on a heuristic solution approach and compares them with the solutions yielded by a Branch-and-Price approach. To show the relevance of the DTOP in real-world scenarios, this master thesis investigates the application of the developed ALNS in a post-earthquake scenario, where unmanned aerial vehicles (UAVs) can be applied for building damage assessment. The investigation is based on data of the heavy earthquake of Coquimbo in 2015.