# Arc Routing Problems with Multiple Trucks and Drones: A Hybrid Genetic Algorithm

arXiv: https://arxiv.org/abs/2508.18105 · HTML: https://mlsanity.com/paper/2508.18105/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2025.

## Built on by (most cited first, 1 of 1)

- [Drive, Pack, Fly: The Travelling Thief Problem with Drone](https://mlsanity.com/paper/2608.16435/) (2026)

## Abstract (arXiv)

Arc-routing problems underpin numerous critical field operations, including power-line inspection, urban police patrolling, and traffic monitoring. In this domain, the Rural Postman Problem (RPP) is a fundamental variant in which a prescribed subset of edges or arcs in a network must be traversed. This paper investigates a generalized form of the RPP, called RPP-mTD, which involves a fleet of multiple trucks, each carrying multiple drones. The trucks act as mobile depots traversing a road network, from which drones are launched to execute simultaneous service, with the objective of minimizing the overall makespan. Given the combinatorial complexity of RPP-mTD, we propose a Hybrid Genetic Algorithm (HGA) that combines population-based exploration with targeted neighborhood searches. Solutions are encoded using a two-layer chromosome that represents: (i) an ordered, directed sequence of required edges, and (ii) their assignment to vehicles. A tailored segment-preserving crossover operator is introduced, along with multiple local search techniques to intensify the optimization. We benchmark the proposed HGA against established single truck-and-drone instances, demonstrating competitive performance. Additionally, we conduct extensive evaluations on new, larger-scale instances to demonstrate scalability. Our findings highlight the operational benefits of closely integrated truck-drone fleets, affirming the HGA's practical effectiveness as a decision-support tool in advanced mixed-fleet logistics.