A branch-and-price algorithm for a team orienteering problem with fixed-wing drones

Kaarthik Sundar, Sujeevraja Sanjeevi, Christopher MontezEuro J. Transp. Logist 2022 · DOI

TL;DR

This paper tackles the complex problem of optimizing flight paths for multiple fixed-wing drones performing tasks like surveillance or mapping. They introduce a novel "branch-and-price" algorithm that accounts for the unique kinematic constraints of fixed-wing drones (like minimum turn radius), which traditional algorithms often ignore. This new approach allows for optimal solutions to these drone routing problems, outperforming previous methods.

What Problem Does This Paper Address?

Vehicle Routing Problems (VRPs) are a well-studied area in logistics and operations research, with many applications in drone operations, from delivery to surveillance. However, most existing VRP solutions for drones either assume simple point-to-point travel or focus on rotary-wing drones, which have more maneuverability. Fixed-wing drones, on the other hand, have significant kinematic constraints, most notably a minimum turn radius, which means they cannot change direction instantaneously. This constraint fundamentally alters the shortest path between two points, making it dependent on the drone's departure and arrival angles.

The authors address the "Team Orienteering Problem" (TOP) specifically for fixed-wing drones. In the TOP, multiple agents (drones in this case) must visit a set of targets to collect scores, aiming to maximize the total score within a given time or distance limit. The challenge is to integrate the fixed-wing drone's kinematic constraints into an exact optimization framework for this multi-drone scenario, which is computationally demanding. Previous work has either ignored these constraints, used heuristics, or focused on single-drone problems. This paper aims to fill this gap by developing an exact algorithm for the multi-drone TOP with kinematic constraints.

Methods

The core of the paper is the development of a branch-and-price (B&P) algorithm to solve the "Dubins Team Orienteering Problem" (DTOP), which is the TOP with fixed-wing drone kinematic constraints.

Here's a breakdown of their approach:

  • Problem Formulation: They first discretize the possible heading angles at each target. This transforms the continuous problem into a graph-based problem where each target is represented by multiple vertices, each corresponding to a specific heading angle. This allows them to formulate the problem as a set-packing problem.
  • Branch-and-Price Algorithm: This is a powerful exact optimization technique that combines branch-and-bound with column generation.
  • Master Problem (MP): The MP is a linear relaxation of the set-packing formulation, which has an exponentially large number of potential routes (columns).
  • Pricing Sub-problem: To efficiently generate new routes (columns) for the MP, they solve a "pricing problem." This is framed as a resource-constrained elementary shortest path problem (RCESPP).
  • Decremental State Space Relaxation (DSSR): To solve the RCESPP efficiently, they employ a DSSR algorithm. This technique uses bi-directional search and relaxes the "elementarity" constraint (ensuring no repeated vertices) for non-critical targets, significantly speeding up the search.
  • Branching Scheme: When the MP yields a fractional solution (meaning a route is not fully selected or rejected), they use a branching scheme. This involves creating new sub-problems by either enforcing or forbidding visits to specific targets or connections between targets. This scheme is specifically designed to handle the discrete nature of the target vertices introduced by heading angle discretization.
  • Concurrent Implementation: A key contribution is the development of a multi-threaded concurrent B&P algorithm. This allows multiple nodes in the branch-and-bound tree to be processed simultaneously, leveraging modern multi-core processors for significant speedups.

Datasets

The authors tested their algorithm on benchmark instances for the standard Team Orienteering Problem (TOP). They generated 801 instances for their DTOP by taking existing TOP instances (up to 66 targets) and creating three variants for each based on the number of heading angle discretizations (2, 4, and 6). The heading angles were uniformly discretized within [0, 2π).

Key Insights and Ideas

  • Kinematic Constraints Matter: The paper strongly demonstrates that ignoring the kinematic constraints of fixed-wing drones can lead to infeasible solutions or suboptimal paths. Their results show instances where paths that would be valid without constraints become impossible when turn radii are considered.
  • Discretization as a Bridge: Discretizing heading angles is a crucial step that transforms a complex continuous optimization problem into a tractable graph-based problem, enabling the application of exact methods like B&P.
  • DSSR's Effectiveness: The use of DSSR significantly accelerates the pricing sub-problem, which is often the bottleneck in B&P algorithms. This highlights the power of specialized relaxation techniques for specific problem structures.
  • Concurrency is Key for Performance: The multi-threaded implementation of their B&P algorithm provides substantial speedups, making it practical to solve larger and more complex instances within reasonable time limits. This underscores the importance of parallel computing for modern optimization challenges.

Key Results

  • The proposed branch-and-price algorithm successfully solved 801 instances of the Dubins Team Orienteering Problem to optimality within a 1-hour time limit, with only 80 instances timing out.
  • Increasing the number of heading angle discretizations generally led to a decrease in instances with zero objective value (meaning no targets visited), suggesting better feasibility and higher scores. However, this also increased computation times.
  • The multi-threaded concurrent B&P algorithm showed significant improvements over its single-threaded counterpart. For instances that took longer than 5 seconds, the concurrent version achieved an average computational gain of 44.24% and a maximum gain of 84.24%.

Limitations and Future Work

  • Discretization Trade-off: While discretization of heading angles is effective, it introduces a trade-off between solution accuracy and computational cost. A finer discretization leads to more accurate solutions but significantly increases the problem size and computation time.
  • Fixed Parameters: The current model assumes a constant speed and a fixed turn radius for all drones. Future work could explore scenarios with variable speeds or different turn radii for different drones.
  • Generalization: The authors suggest extending their approach to a wider class of vehicle routing problems involving fixed-wing drones, potentially incorporating other constraints like time windows or refueling stops.
  • Heuristic Integration: While the paper focuses on exact methods, exploring hybrid approaches that combine their exact B&P algorithm with heuristics could be beneficial for even larger-scale problems.

Summary updated

BibTeX
@article{sundar2022branch,
  author = {Kaarthik Sundar and Sujeevraja Sanjeevi and Christopher Montez},
  title = {{A branch-and-price algorithm for a team orienteering problem with fixed-wing drones}},
  journal = {Euro J. Transp. Logist},
  year = {2022},
  doi = {10.1016/j.ejtl.2021.100070},
}
Figure