Publication:
Exploration of a disrupted road network after a disaster with an online routing algorithm

Date

2020

Authors

Voegl, Jana
Rest, Klaus‑Dieter
Hirsch, Patrick

Director

Publisher

Springer
Acceso abierto / Sarbide irekia
Artículo / Artikulua
Versión publicada / Argitaratu den bertsioa

Project identifier

AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-109984RB-C43/ES/recolecta

Abstract

This paper considers the problem of supporting immediate response operations after a disaster with information about the available road network to reach certain locations. We propose an online algorithm that aims to minimize the route length required by an unmanned aerial vehicle (UAV) to explore the road accessibility of potential victim locations. It is assumed that no information about disruptions in the road network is available at the start of the exploration. The online algorithm applies two movement and three orientation strategies. Additionally, a cutting strategy is used to restrict the search space after new information about the state of single roads is obtained. We consider a road and an aerial network for the movements of the UAV, since it is not necessary to follow the route of a road any longer, if it can be marked as disrupted. In extensive numerical studies with artificial and real-world test instances, it is evaluated for different disruption levels, which combinations of movement and orientation strategies perform best. Additionally, we propose different refuelling strategies for the UAV and present how they differ in the number of refuelling operations and the required additional route length. The results show that an efficient online algorithm can save valuable exploration time.

Description

Keywords

Aerial vehicles for humanitarian operations, Disaster management, Disrupted road network, Immediate response operations, Online algorithm, Online exploration strategies

Department

Institute of Smart Cities - ISC

Faculty/School

Degree

Doctorate program

item.page.cita

item.page.rights

© The Author(s) 2020. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

Los documentos de Academica-e están protegidos por derechos de autor con todos los derechos reservados, a no ser que se indique lo contrario.