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

• URL: http://arxiv.org/abs/2508.18105v1
• Date: Mon, 25 Aug 2025 15:10:46 GMT
• Title: Arc Routing Problems with Multiple Trucks and Drones: A Hybrid Genetic Algorithm
• Authors: Abhay Sobhanan, Hadi Charkhgard, Changhyun Kwon,
• Abstract summary: Rural Postman Problem (RPP) is a fundamental variant in which a subset of edges or arcs in a network must be traversed.<n>This paper investigates a generalized form of the RPP, called RPP-mTD, which involves a fleet of multiple trucks, each carrying multiple drones.<n>We propose a Hybrid Genetic Algorithm (HGA) that combines population-based exploration with targeted neighborhood searches.
• Score: 0.41292255339309664
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Multi-Agent Route Planning as a QUBO Problem [0.39325957466009204]
  This paper gives a formal problem definition, proves NP-hardness by reduction from the Weighted Set Packing problem, and derives a Quadratic Unconstrained Binary Optimization formulation.<n>A single penalty parameter controls the coverage-overlap trade-off.<n>Experiments on Barcelona instances with up to 10 000 vehicles reveal a clear coverage-overlap knee.
  arXiv  Detail & Related papers  (2026-02-08T11:18:45Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems.<n>We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• A Coalition Game for On-demand Multi-modal 3D Automated Delivery System [4.378407481656902]
  We introduce a coalition game for a fleet of UAVs and ADRs operating in two overlaying networks to address last-mile delivery in urban environments.<n>We investigate cooperation structures among the modes to capture how strategic collaboration can improve overall routing efficiency.<n>Several numerical experiments on last-mile delivery applications have been conducted, showing the results from the case study in the city of Mississauga.
  arXiv  Detail & Related papers  (2024-12-23T03:50:29Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks [10.18252143035175]
  We introduce the multi-agent flying sidekick traveling salesman problem (MA-FSTSP) on road networks. We propose a mixed-integer linear programming model and an efficient three-phase algorithm for this NP-hard problem. Our approach scales to more than 300 customers within a 5-minute time limit, showcasing its potential for large-scale, real-world logistics applications.
  arXiv  Detail & Related papers  (2024-08-20T20:44:18Z)
• Tiny Multi-Agent DRL for Twins Migration in UAV Metaverses: A Multi-Leader Multi-Follower Stackelberg Game Approach [57.15309977293297]
  The synergy between Unmanned Aerial Vehicles (UAVs) and metaverses is giving rise to an emerging paradigm named UAV metaverses. We propose a tiny machine learning-based Stackelberg game framework based on pruning techniques for efficient UT migration in UAV metaverses.
  arXiv  Detail & Related papers  (2024-01-18T02:14:13Z)
• Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes [0.9423257767158634]
  We develop new extensions to existing encoder-decoder attention models which allow them to handle multiple trucks and multi-leg routing requirements.<n>Our models have the advantage that they can be trained for a small number of trucks and nodes, and then embedded into a large supply chain to yield solutions for larger numbers of trucks and nodes.
  arXiv  Detail & Related papers  (2024-01-08T21:13:07Z)
• Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP [0.39373541926236766]
  This work presents a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP) The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers. The HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specifics and a local search phase.
  arXiv  Detail & Related papers  (2023-04-26T21:19:36Z)
• Optimization for Master-UAV-powered Auxiliary-Aerial-IRS-assisted IoT Networks: An Option-based Multi-agent Hierarchical Deep Reinforcement Learning Approach [56.84948632954274]
  This paper investigates a master unmanned aerial vehicle (MUAV)-powered Internet of Things (IoT) network. We propose using a rechargeable auxiliary UAV (AUAV) equipped with an intelligent reflecting surface (IRS) to enhance the communication signals from the MUAV. Under the proposed model, we investigate the optimal collaboration strategy of these energy-limited UAVs to maximize the accumulated throughput of the IoT network.
  arXiv  Detail & Related papers  (2021-12-20T15:45:28Z)
• MRDet: A Multi-Head Network for Accurate Oriented Object Detection in Aerial Images [51.227489316673484]
  We propose an arbitrary-oriented region proposal network (AO-RPN) to generate oriented proposals transformed from horizontal anchors. To obtain accurate bounding boxes, we decouple the detection task into multiple subtasks and propose a multi-head network. Each head is specially designed to learn the features optimal for the corresponding task, which allows our network to detect objects accurately.
  arXiv  Detail & Related papers  (2020-12-24T06:36:48Z)
• The two-echelon routing problem with truck and drones [0.0]
  We study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems.
  arXiv  Detail & Related papers  (2020-04-05T18:33:16Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.