Inclusiveness Target Country Conference Grant

A Metaheuristic for the Maximum Coverage Facility Location Problem with Drone

Çağrı Koç, Social Sciences University of Ankara, Ankara, Türkiye
Y. Yankaya, Gazi University, Ankara, Türkiye
F. Altiparmak, Gazi University, Ankara, Türkiye

OR66 Annual Conference
Bangor, United Kingdom
10-12 September 2024

Grantee: Çağrı Koç, Social Sciences University of Ankara, Ankara, Türkiye
Type of publication: Abstract
Type of presentation: Oral

Start date: 2024-09-09
End date: 2024-09-13
Awarded: 2024-07-21
Report approved: 2024-08-10

Abstract

This study addresses the maximum coverage facility location problem with drone which considers the assignment of drones to predetermined facilities considering a set of demands and potential facility locations. The aim is to locate facilities to maximize the demand served by drone. In the problem, the transportation cost is not considered. If a customer demand exceeds the drone carrying capacity, multiple flights are made to fulfill the demand, and in this case, the number of flights is determined according to the drone capacity. Each drone can complete several one-to-one deliveries until the battery level is finished. The charging of drone batteries, charging cycles, weather conditions and the impact of obstacles such as tall buildings or mountains are not considered. We first model the problem as an integer linear programming formulation. We then develop a hyperheuristic based on adaptive simulated annealing algorithm. The metaheuristic starts with a greedy construction algorithm to generate the initial solution. We enhance the metaheuristic by introducing several problem specific procedures. We conduct extensive computational experiments on diverse size of benchmark instances to deeply analyze the method performance. The effectiveness of the algorithm is evaluated by comparing it with state-of-the-art methods in the literature where we observe that our algorithm outperforms them in terms of both solution time and quality. Our method yields better results up to %8.4 on maximum coverage when compared with the best-known solutions.

Publication

@inproceedings{Koc2024metaheuristic,
	address = {Bangor, United Kingdom},
	author = {Ko{\c c}, {\c C}a{\u g}r\i{}},
	booktitle = {OR66 annual conference},
	year = {2024},
	month = {9},
	pages = {198},
	title = {A metaheuristic for the maximum coverage facility location problem with drone},
}