EURO 2025 Leeds
Abstract Submission

1138. On the drone general routing problem with load-dependent costs

Invited abstract in session MD-17: Drone Routing, stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: Esther Simpson 2.08

Authors (first author is the speaker)

1. Paula Segura
Mathematics for Economics and Business, Universitat de València
2. Isaac Plana
Matemáticas para la Economía y la Empresa, University of Valencia
3. Jose Maria Sanchis
Departamento de Matematica Aplicada, Universidad Politecnica de Valencia

Abstract

Recent advances in drone technology have made it possible for drones to have the capability of capturing images and making deliveries during the same flight. This capability can be very useful, for example, in humanitarian emergencies, where drones can deliver medicine to difficult-to-reach areas and take pictures of disaster-affected zones. However, the payload capacity of drones is still quite limited, and the weight of the cargo being carried significantly affects flight times.
In this talk, we present the drone general routing problem with load-dependent costs, where a drone must traverse a set of edges and make a series of deliveries at some vertices of a graph, and both the edge traversal and delivery times depend on the total weight of the drone at that moment. Each time the drone makes a delivery, its weight decreases and, consequently, the traversal time of subsequent edges is reduced. Thus, it may be interesting to serve a vertex with high demand first even if it is far away. The goal here is to minimize the total duration of the drone tour. We propose a formulation for the problem and analyze the associated polyhedron of solutions while introducing families of valid inequalities to strengthen the formulation. We design a branch-and-cut algorithm to solve the problem and perform extensive computational tests on instances with a maximum of 7 deliveries and 96 edges to be traversed.

Keywords

Status: accepted

Back to the list of papers