Drone Arc Routing Problems with multiple depots and other variants

• Autores: Teresa Corberan Fabra
• Directores de la Tesis: Isaac Plana Andani (dir. tes.) , José María Sanchís Llopis (codir. tes.) , Teresa León (tut. tes.)
• Lectura: En la Universitat de València ( España ) en 2026
• Idioma: inglés
• Número de páginas: 183
• Tribunal Calificador de la Tesis: Rafael Martí Cunquero (presid.) , Mercedes Landete Ruiz (secret.) , Maria Cândida Mourão (voc.)
• Programa de doctorado: Programa de Doctorado en Estadística y Optimización por la Universitat de València (Estudi General) y la Universitat Politècnica de València
• Menciones:
  • Internacional
• Calificación: Sobresaliente Cum Laude
• Enlaces
  • Tesis en acceso abierto en:  TESEO  RODERIC 
• Resumen

  • The rapid development of unmanned aerial vehicles (drones) has created new opportunities for inspection, monitoring, and service operations along linear infrastructures such as power lines, pipelines, railway tracks, and road networks. These applications naturally lead to arc routing problems in which drones must traverse and service network elements. Unlike classical arc routing problems involving ground vehicles, drone-based routing allows vehicles to move freely in space and to enter and exit required lines at arbitrary points, which results in continuous optimization problems with an infinite set of feasible solutions.Solving such continuous problems directly is computationally challenging. A common approach consists of discretizing the continuous network by approximating each line with a polygonal chain and restricting drone entry and exit to a finite set of points, thus transforming the original problem into a large but finite combinatorial optimization problem. If the discretization is sufficiently fine, high-quality approximations of the continuous optimal solutions can be obtained.Within this setting, this thesis studies several arc routing problems motivated by drone inspection and service applications. The problems considered combine features of classical arc routing and general routing problems with multiple depots, location decisions, and multiple trips, while explicitly incorporating drone-specific constraints such as limited flight duration and capacity. Although the original problems are continuous in nature, the thesis focuses on discrete formulations for which exact and heuristic methods are developed.The first problem addressed is the Multi-Depot drone General Routing Problem with duration and capacity constraints (MDdGRP). A discrete formulation, the MDGRP, is proposed and strengthened through valid inequalities. An exact branch-and-cut algorithm is developed, together with two matheuristics for the continuous problem.The thesis then considers the Min Max Multi-Trip drone Location Arc Routing Problem (MM-MT-dLARP), which explicitly models the interaction between drones and ground support vehicles. A discretized version of the problem, the MM-MT-LARP, is formulated and studied from a polyhedral perspective, leading to an exact branch-and-cut algorithm and a matheuristic method.Finally, a generalized version of the MM-MT-LARP is addressed using a branch-and-price approach. This method avoids imposing predefined limits on the number of drone trips and significantly improves the computational performance, enabling the solution of instances that can not be solved with branch-and-cut algorithms.