Mothership and multi-drone routing for spatial marine management

Technical Summary: Mothership and Multi-Drone Routing for Spatial Marine Management

Problem Definition
This research addresses a novel routing problem in continuous, road-free marine environments, specifically motivated by the logistical challenges of large-scale coral seeding for reef restoration. The problem involves coordinating a primary vessel (the "mothership") and a fleet of homogeneous satellite vessels (referred to as "drones," though they are surface vessels) to service a set of geographically dispersed deployment nodes.

Unlike traditional Vehicle Routing Problems (VRP) or even existing "Flying Sidekick" formulations that rely on road networks or predefined customer locations, this problem operates in a continuous two-dimensional domain. The core challenge is to minimize the total weighted travel distance of the fleet by simultaneously optimizing four interdependent decisions:

1. Clustering: Partitioning the deployment nodes into $n_c$ equal-sized clusters.
2. Waypoint Selection: Determining the optimal launch and rendezvous waypoints for each cluster. These waypoints are continuous decision variables, not restricted to a predefined grid or node set.
3. Sortie Assignment: Assigning nodes within each cluster to specific drone sorties.
4. Sequencing: Determining the order in which drones visit nodes within a sortie.

The problem assumes a "mobile depot" model where the mothership travels between clusters, launching all drones for a specific cluster from a single waypoint and retrieving them at a subsequent waypoint. Drones must complete their sorties and rendezvous with the mothership before the fleet proceeds to the next cluster. The objective function minimizes a weighted sum of the mothership's travel distance and the cumulative drone travel distance, controlled by a weighting parameter $\gamma$.

Methodology
The authors propose a dual approach to solving this problem: an exact Mixed-Integer Linear Programming (MILP) formulation and a metaheuristic algorithm.

• MILP Formulation: To obtain exact solutions for benchmarking, the authors discretize the continuous spatial domain into a finite grid of candidate waypoints. The formulation uses binary variables to define the mothership tour and drone sorties, along with auxiliary variables to prevent subtours (using Miller-Tucker-Zemlin constraints). This approach is computationally tractable only for small instances (e.g., up to 12 nodes) due to the exponential growth of the solution space and memory requirements.
• Metaheuristic (Simulated Annealing): To address practical-scale instances where the MILP fails, the authors develop a Simulated Annealing (SA) metaheuristic. The solution representation consists of node-to-cluster and node-to-sortie assignments. The algorithm employs:
  • Initial Solution Construction: A sequential process involving random node clustering, nearest-neighbor sequencing of clusters for the mothership, and nearest-neighbor routing for drone sorties.
  • Perturbation Operators: Three distinct operators modify the solution: intra-cluster node swaps, inter-cluster node swaps, and inter-cluster sortie swaps.
  • Local Search: A 2-opt heuristic is applied to drone sorties, and a continuous-space waypoint heuristic (based on weighted combinations of cluster centroids and previous waypoints) is used to dynamically calculate mothership waypoints.
  • Waypoint Heuristic: A specific contribution of the methodology is the continuous-space waypoint calculation (Equations 23–25), which determines launch and rendezvous points based on a scaling factor $\theta$ that biases the location toward the mothership's current position or the cluster centroid.

Key Results

• Computational Efficiency: The metaheuristic demonstrates significant computational advantages over the exact MILP. On 8-node instances, the metaheuristic achieved solutions within 2.1% of the MILP optimum while reducing computation time by two orders of magnitude. On 12-node instances, where the MILP often ran out of memory or failed to find optimal solutions within reasonable timeframes, the metaheuristic produced solutions within 2% of the best-known MILP results in approximately 3–6 seconds (a reduction of up to four orders of magnitude).
• Solution Stability: Across 1,000 stochastic runs on a 48-node instance, the algorithm produced a multi-modal distribution of objective values. The best solution ($z^* = 494.62$) was found with a standard deviation of 0.82% across runs, indicating that while the algorithm converges to local minima, the variance is relatively low.
• Sensitivity Analysis:
  • Cluster Configuration: Increasing the number of clusters reduced the total weighted distance by creating more geographically concentrated clusters, which lowered drone travel distances despite increasing the mothership's travel distance.
  • Fleet Composition: Increasing drone capacity (nodes per sortie) significantly reduced total weighted distance by reducing the number of required sorties. However, drone fleet composition had negligible impact on the mothership's routing path.
  • Vessel Weighting ($\gamma$): The weighting parameter fundamentally alters the routing strategy. As $\gamma$ increases (mothership cost becomes dominant), the solution shifts toward a "fixed depot" Vehicle Routing Problem structure where the mothership stays near the origin. As $\gamma$ decreases, the mothership acts as a "mobile depot," moving to minimize drone travel, approaching a mobile-depot routing regime.

Significance and Claims
The paper claims to fill a critical gap in the coordinated fleet routing literature by integrating three features that have previously been studied in isolation:

1. A mothership operating in continuous, road-free space rather than on a network.
2. Multiple drones capable of multiple deliveries per sortie.
3. Dynamic launch and rendezvous locations selected freely in continuous space, rather than being restricted to a predefined set of candidate locations.

The authors assert that their framework provides a flexible and computationally effective foundation for large-scale marine logistics, such as reef restoration and offshore windfarm servicing. They emphasize that the continuous-space waypoint heuristic and the ability to handle multi-delivery sorties in a road-free environment distinguish this work from existing terrestrial truck-drone formulations. The study concludes that while the model simplifies certain operational realities (e.g., assuming homogeneous fleets and ignoring environmental constraints like bathymetry), it offers a robust baseline for optimizing resource deployment in spatially dispersed marine environments.