A Two-Stage Approach for Routing Multiple Unmanned Aerial Vehicles with Stochastic Fuel Consumption

Saravanan Venkatachalam, Kaarthik Sundar, Sivakumar RathinamSensors 2018 · DOI

TL;DR

This paper tackles the complex problem of routing multiple Unmanned Aerial Vehicles (UAVs) for missions where fuel consumption is uncertain. They propose a novel two-stage stochastic optimization model and develop a computationally efficient tabu search heuristic to find near-optimal solutions, crucial for real-world applications like surveillance and delivery.

What Problem Does This Paper Address?

The increasing use of small UAVs in various applications, from environmental monitoring to disaster response and package delivery, is often limited by their fuel constraints. Routing these UAVs to complete missions, especially when multiple vehicles are involved, becomes challenging when the exact fuel needed for each leg of the journey is unpredictable. This uncertainty arises from factors like wind, payload variations, and operational conditions. Traditional routing methods often assume deterministic fuel consumption, which can lead to infeasible plans or inefficient refueling strategies. This paper addresses the need for a robust routing approach that explicitly accounts for this stochastic fuel consumption in multi-UAV missions, aiming to minimize overall fuel usage and ensure mission completion.

Methods

The core of the paper is a two-stage stochastic optimization model for the Fuel-Constrained Multiple-UAV Routing Problem (FCMURP).

  • First Stage: This stage determines the initial routes for the UAVs, aiming to minimize travel costs while ensuring that, based on nominal fuel consumption, each target is visited and no UAV runs out of fuel. These are the "here-and-now" decisions.
  • Second Stage: This stage deals with the uncertainty. For a given realization of fuel consumption (a "scenario"), it determines the necessary additional refueling trips to ensure the mission is completed. These are the "recourse actions." The objective is to minimize the sum of first-stage costs and the expected second-stage recourse costs.

To solve this complex model, they employ:

  • Sample Average Approximation (SAA): This is a standard technique for stochastic programming where the expected value is approximated by averaging over a finite number of sampled scenarios. While SAA provides statistical estimates of optimal solutions, it can be computationally prohibitive for larger problem instances.
  • Tabu Search Heuristic: To overcome the computational burden of SAA, they develop a heuristic. This heuristic has two phases:
  • Construction Heuristic: This phase builds an initial feasible solution by solving multiple deterministic FCMURP instances for different scenarios and combining their results.
  • Improvement Heuristic (Tabu Search): This phase iteratively refines the initial solution using a tabu search algorithm, which explores the solution space dynamically and allows for moves that might temporarily degrade the objective function to escape local optima.

Datasets

The paper uses randomly generated test instances for evaluation.

  • Small-scale instances: 5 instances with 10 targets.
  • Large-scale instances: 120 instances with either 20 or 30 targets.

For these instances, they fixed the locations of depots and refueling sites and varied parameters like the number of vehicles and fuel capacity. The fuel consumption uncertainty was modeled using a gamma distribution, with the mean fuel consumption for an edge being its Euclidean distance. They also introduced realistic correlations by designating quadrants as "congested," "sparse," or "mean" to influence edge fuel consumption in scenarios.

Key Insights and Ideas

  • The value of stochastic modeling: The results clearly demonstrate that accounting for fuel consumption uncertainty (using the two-stage model and heuristic) leads to significantly better solutions (lower expected costs) compared to deterministic approaches (like the Expected Value Problem). This highlights that ignoring uncertainty can be costly.
  • SAA's computational challenge: Even for relatively small instances (10 targets), solving SAA problems to optimality can take hours, underscoring the need for efficient heuristics for practical applications.
  • Heuristic effectiveness: The proposed tabu search heuristic is shown to be computationally efficient and produces solutions that are very close to the SAA upper bounds, making it a viable alternative for large-scale problems.
  • Realistic scenario generation: The method for generating scenarios, incorporating factors like congested/sparse areas, adds a layer of realism that is crucial for testing the robustness of routing strategies.

Key Results

  • The heuristic consistently provides solutions with lower expected costs than the deterministic Expected Value Problem (EEV).
  • For large-scale instances, the heuristic solutions are very close to the SAA upper bounds, with an average Value of Stochastic Solution (VSS) of 6.4% and a maximum of 29.69%, indicating substantial gains from using the stochastic approach.
  • The tabu search heuristic is computationally efficient, with run times for large-scale instances generally under six minutes.
  • For small-scale instances, solving SAA problems to optimality could take up to three hours, confirming the computational burden.

Limitations and Future Work

  • Computational scalability of SAA: The paper acknowledges that SAA remains computationally expensive for large-scale problems, necessitating the heuristic approach.
  • Focus on fuel consumption uncertainty: The model primarily addresses uncertainty in fuel consumption.
  • Future Work: The authors suggest several avenues for future research:
  • Incorporating uncertainty in UAV availability for missions.
  • Extending the two-stage model to a risk-averse framework, where additional weights are added to the recourse objective function to penalize higher risks.
  • Exploring other scenario generation techniques or uncertainty modeling approaches.

Summary updated

BibTeX
@article{venkatachalam2018two,
  author = {Saravanan Venkatachalam and Kaarthik Sundar and Sivakumar Rathinam},
  title = {{A Two-Stage Approach for Routing Multiple Unmanned Aerial Vehicles with Stochastic Fuel Consumption}},
  journal = {Sensors},
  year = {2018},
  doi = {10.3390/s18113756},
}
Figure