Source-linked AI summary
Algorithms for Routing an Unmanned Aerial Vehicle in the presence of Refueling Depots
Kaarthik Sundar, Sivakumar Rathinam
TL;DR
The paper addresses single-UAV routing with multiple refueling depots, requiring every target to be visited without violating fuel constraints while minimizing total fuel. It develops an approximation algorithm, fast construction and improvement heuristics, and an optimality benchmark. For instances with 5 depots and 25 targets, solutions average within 1.4% of optimum and are found in under 2 seconds.
Problem
FCURP seeks a minimum-fuel UAV tour that visits every target while respecting fuel constraints and allowing refueling at multiple depots.
Method
The paper combines an approximation algorithm with construction and improvement heuristics, and formulates a mixed-integer linear program for optimal solutions.
Results
1.4% average gap from optimum was achieved for instances with 5 depots and 25 targets, with feasible solutions found in less than 2 seconds per instance.
Takeaways & Limitations
The proposed approximation and heuristic approach produces near-optimal FCURP solutions relatively quickly on the tested instances.
Abstract
from arXiv · showhide
We consider a single Unmanned Aerial Vehicle (UAV) routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total fuel required by the UAV is a minimum. We develop an approximation algorithm for the problem, and propose fast construction and improvement heuristics to solve the same. Computational results show that solutions whose costs are on an average within 1.4% of the optimum can be obtained relatively fast for the problem involving 5 depots and 25 targets.
I. INTRODUCTION
Small UAVs support monitoring missions but face fuel constraints that can require repeated depot visits. The paper studies FCURP and develops approximation, heuristic, optimization, and evaluation methods for it.
- Motivation: Small UAVs are useful for monitoring applications but have resource constraints associated with their size and limited payload.Applications include wildfire management, weather monitoring, hurricane monitoring, and pollutant estimation.
- Problem motivation: FCURP requires a UAV to visit every target while respecting fuel limits and minimizing total fuel consumed.The UAV may repeatedly return to depots for refueling before visiting all targets.
- Research context: FCURP generalizes ATSP and is NP-hard, while existing ATSP approximation factors depend on the number of targets or input data.The cited covering algorithm has approximation factor log(n).
- Related work: The paper generalizes a 2(1−a)-approximation result to the asymmetric case.The cited prior result concerns the corresponding symmetric setting.
- Contributions: The proposed contributions include an approximation algorithm, fast construction and improvement heuristics, a mixed-integer linear program, and computational comparisons.The optimization formulation provides optimal solutions for evaluating algorithmic solution quality and computation time.
II. PROBLEM STATEMENT
FCURP is modeled on a complete directed graph containing targets and depots, with fuel costs satisfying the triangle inequality. A feasible minimum-cost tour visits every target and respects fuel capacity between successive depots.
- Graph formulation: FCURP uses a complete directed graph whose vertices are targets and depots, with directed fuel costs satisfying the triangle inequality.The initial depot is denoted by s, and fij is the fuel required to travel from vertex i to vertex j.
- Assumptions: Each target must be reachable between depots under an assumed fuel bound aL, where a lies in [0, 1].For each target i, depots d1 and d2 satisfy fd1i + fid2 ≤ aL.
- Assumptions: Travel between any two depots is assumed possible without violating fuel constraints, directly or through intermediate depots.The minimum depot-to-depot fuel requirement is represented by l̄d1,d2, with β used as a data-dependent constant.
- Feasibility and objective: A feasible tour starts and ends at the initial depot, visits every target at least once, and limits fuel used between successive depots to L.The objective is to minimize the sum of fuel required by the tour’s edges.
- Approximation algorithm: The approximation algorithm first computes shortest feasible paths between targets, then uses those paths to construct a covering tour.Indirect tour edges are replaced with their corresponding shortest paths.
III. APPROXIMATION ALGORITHM
Approx constructs fuel-feasible paths between targets, uses them to build a target-covering tour, and repairs infeasible depot-to-depot strands with greedy refueling trips.
- Shortest paths: Approx finds a least-cost feasible path between targets while respecting available fuel at departure and required fuel at arrival.It uses direct travel when possible and otherwise searches an auxiliary depot-target graph with Dijkstra’s algorithm.
- Shortest paths: The auxiliary graph permits only fuel-feasible target-to-depot, depot-to-depot, and depot-to-target edges.Its edge sets enforce the vehicle’s fuel capacity and the required residual fuel at targets.
- Covering algorithm: A minimum-cost cycle cover over shortest-path costs is repeatedly processed until the covering construction yields a connected Eulerian graph spanning the targets.The minimum cycle cover can be computed with the Hungarian algorithm, and multiple cycles are reduced by selecting one vertex from each.
- Covering algorithm: The resulting Eulerian tour is expanded along target-to-target shortest paths, producing a Hamiltonian tour that visits every target and selected refueling depots.The expanded tour may still violate fuel constraints on depot-to-depot strands.
- Feasibility repair: Infeasible strands are repaired greedily by adding depot refueling trips and sequentially shortcutting trips whose removal preserves feasibility.For each target, the procedure uses a nearest terminal depot, a depot path, and a nearest starting depot before testing shortcuts.
A. Analysis of the Approximation Algorithm
Approx constructs a feasible FCURP solution by combining target-to-target paths, cycle-cover routing, and greedy refueling trips, with bounds on feasibility, cost, and running time.
- Approx always produces a feasible solution for the FCURP.
- Greedy refueling trips convert infeasible strands into feasible paths while preserving the required depot-to-depot traversal.
- The algorithm computes minimum-cost feasible paths between targets, then uses cycle covers and shortest-path replacements to construct a target-visiting tour.
- The number of refueling trips is bounded by 2cost(TOUR)/((1−a)L), using the per-target fuel bound Cx + Bx ≤ aL.
- The total refueling-trip cost is bounded by 2(1+β)a cost(TOUR)/(1−a), while cost(TOUR) is at most log(|T|) × Copt.
IV. CONSTRUCTION AND IMPROVEMENT HEURISTICS
The heuristics construct an initial feasible tour and iteratively improve it through depot-centered k-opt exchanges, while preserving fuel feasibility.
- Construction heuristic: The construction heuristic replaces Approx’s covering step with the Lin-Kernighan-Helgaun heuristic.
- Improvement heuristic: The improvement procedure combines k-opt local search with depot exchange to improve the construction heuristic’s feasible tour.
- k-opt heuristic: A k-exchange replaces k tour edges with k new edges, and an improving exchange must remain feasible and reduce travel cost.
- k-opt heuristic: The k-opt algorithm starts from an initial feasible tour and repeatedly applies the best improving exchanges until no further improvement is found.
- k-opt heuristic: The search restricts k-exchanges to depot-centered segments, where k edges are deleted and k new edges are added.
- k-opt heuristic: Each updated tour is checked to ensure that the UAV never runs out of fuel.
B. Depot Exchange Heuristic
The depot exchange heuristic tests replacements for visited refueling depots and retains feasible substitutions that reduce total tour cost.
- Depot exchange heuristic: For each depot in visit order, the heuristic considers replacing it with a possibly new refueling depot.
- Depot exchange heuristic: A replacement depot is selected by minimizing the combined travel costs from the preceding and following vertices, subject to feasibility and cost reduction.
- Depot exchange heuristic: The resulting feasible tour becomes the current solution, and depot substitutions continue until no further improvements are possible.
V. MIXED INTEGER PROGRAMMING FORMULATION
The mixed integer linear program models FCURP tours with edge-selection, degree, connectivity, flow, and fuel-capacity constraints.
- Decision variables: The formulation uses integer edge variables x_ij to represent how many times the vehicle travels from vertex i to vertex j.
- Decision variables: Triangle inequality permits restricting target-incident edge variables to binary values because an optimal solution can visit each target exactly once.
- Connectivity and flow: Flow constraints route |T| commodity units from the depot and deliver one unit to each target, enforcing paths from the depot to every target.
- Model constraints: The model includes degree constraints and capacity-and-flow constraints for the FCURP mixed integer linear program.
- Fuel feasibility: Fuel-related constraints use fuel variables and a large constant M to enforce feasible fuel transitions on selected edges.
- Model constraints: Degree equations balance each vertex’s in-degree and out-degree, while depot visits remain unrestricted for refueling.
VI. COMPUTATIONAL RESULTS
The computational study evaluates approximation and heuristic methods on Dubins-vehicle instances with multiple depots and up to 25 targets. The heuristics produce feasible solutions quickly, and improvement steps substantially enhance solution quality.
- Experimental setup: 50 instances were generated for each size from 10 to 25 targets, with 5 depots fixed in a 5000 × 5000-unit square.
- Experimental setup: The simulations use a Dubins’ vehicle with minimum turning radius 100 units and uniformly selected target approach angles.
- Computation time: Nearly 2 hours were required on average for CPLEX to find optimal solutions for instances with 25 targets and 5 depots, versus less than 2 seconds for approximation and heuristics to find feasible solutions.
- Solution quality: The improvement heuristic produces substantially better average solution quality than the construction heuristic or approximation algorithm.
- Solution quality: For 25-target, 5-depot instances, 10-second CPLEX runs initialized with heuristic solutions reached an average solution quality of 1.39%.
- Solution paths: Figure 8 presents paths found by the proposed algorithms for a Dubins’ instance with 25 nodes.
VII. CONCLUSIONS
The paper develops approximation and fast heuristic methods for a generalized single-vehicle routing problem with fuel constraints, alongside a mixed-integer linear programming formulation for optimal solutions.
- An approximation algorithm and fast heuristics address a generalization of single-vehicle routing with fuel constraints.
- A mixed-integer linear programming formulation is proposed to find optimal solutions.
- Future work includes branch-and-cut methods and routing problems with multiple heterogeneous vehicles.