EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3005. Energy-constrained multi-drone covering tour problem with visit durations

Invited abstract in session MB-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design II, stream Combinatorial Optimization.

Monday, 10:30-12:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. ÖZGE ŞATIR AKPUNAR
The Graduate School of Natural and Applied Sciences, Dokuz Eylül University
2. Şener Akpınar
Industrial Engineering, Dokuz Eylül University
3. Tolga Bektas
University of Liverpool Management School, University of Liverpool
4. Cagatay Iris
Management School, University of Liverpool
5. Grigorios Kasapidis
Operations and Supply Chain Management, University of Liverpool

Abstract

This study focuses on the deployment of a fleet of drones required to provide temporary communication during emergencies. It is assumed that drones are initially placed at a depot, while the area is divided into subregions that require continuous communication services. In addition, each drone is subject to battery limitations and thus, needs to return to the depot to recharge its battery. As emergency communication is a continuous activity, drones need to visit the subregions in a sequence. The aim here is to provide continuous coverage of the area by utilizing drones and their limited batteries efficiently. The first aspect of interest is how long a drone should hover over a subregion. Hence, it is aimed to keep each drone as much as possible over every visited subregion, to ensure maximum coverage. Decisions include the selection of visited subregions, the optimal hovering time of each drone over the subregions, and the scheduling of the subregion visit sequence, all aimed at maximizing temporal and spatial coverage. The problem is formulated as a mixed-integer linear program (MILP) resembling the covering tour problem. This mathematical model enables us to model the complex interplay between drone movements, area coverage, and battery constraints. Furthermore, a constraint programming (CP) model is proposed to solve the problem and computational experiments are conducted to assess the performance of the CP and MILP models on randomly generated large-scale instances.

Keywords

Status: accepted


Back to the list of papers