On solving close enough orienteering problems with overlapped neighborhoods

Qiuchen Qian, Yanran Wang, David BoyleEur. J. Oper. Res 2024 · DOI

TL;DR

This paper introduces a new problem variant, the Close Enough Orienteering Problem with Non-uniform Neighborhoods (CEOP-N), and a novel metaheuristic, CRaSZe-AntS, to solve it. CRaSZe-AntS effectively handles overlapping service regions by discretizing them into "Steiner Zones" and then using a hybrid approach of Randomized Steiner Zone Discretization (RSZD), Particle Swarm Optimization (PSO), and Ant Colony System (ACS) to find optimal paths, significantly outperforming existing methods in terms of both solution quality and computation time.

What Problem Does This Paper Address?

The paper tackles the challenge of optimizing routes for agents (like drones or delivery vehicles) that need to collect "prizes" (e.g., deliver packages, collect data) within a certain budget (time or distance). Traditional problems like the Traveling Salesman Problem (TSP) assume agents must visit exact locations. Variants like the Close Enough Traveling Salesman Problem (CETSP) relax this by allowing agents to complete tasks within a defined neighborhood.

However, existing approaches to CETSP and its related problems often struggle with:

  • Overlapping Neighborhoods: When neighborhoods of different targets overlap, it creates complex search spaces. While some methods use "Steiner Zones" (SZs) to represent these overlaps, they can conflict with global optimization. This paper proposes to leverage these overlaps as an advantage.
  • Non-uniform Costs: In real-world scenarios, the cost of collecting a prize within a neighborhood isn't always uniform. Factors like drone flight efficiency, distance from a truck, or signal strength can vary. This paper introduces CEOP-N to account for these non-uniform costs.
  • Efficiency: Existing methods can be computationally expensive, especially for large numbers of targets or complex neighborhoods.

The authors aim to develop a more efficient and effective method for solving these "close enough" routing problems, particularly when dealing with overlapping service areas and varying costs.

Methods

The core of the paper's contribution lies in its novel algorithm, CRaSZe-AntS, which combines several techniques:

  1. Randomized Steiner Zone Discretization (RSZD): This is a new scheme to identify and define "Steiner Zones" (SZs) – regions formed by overlapping circular neighborhoods. RSZD randomly selects candidate circles and iteratively builds SZs, overcoming limitations of previous sweep-line algorithms that struggled with identifying SZ vertices and could be computationally demanding.
  2. Hybrid Optimization (PSO + ACS):
    • For uniform CEOP: CRaSZe-AntS uses the RSZD to create SZs, then applies the Ant Colony System (ACS) to solve the resulting Set Orienteering Problem (SOP). Local search operators like "arc search" are then used to refine waypoint positions.
  3. For non-uniform CEOP-N: CRaSZe-AntS employs Particle Swarm Optimization (PSO) to explore the interior of SZs and refine waypoint positions. The results from PSO are then fed into an Inherited Ant Colony System (IACS) to determine the optimal sequence of waypoints. IACS is a variant of ACS that leverages knowledge from previous iterations for faster convergence.
  4. Local Search Operators: The algorithm incorporates operators like "drop" and "add" to improve solution quality by removing less beneficial waypoints or adding new ones, and an "arc search" algorithm to optimize waypoint positions within SZs.

Datasets

The paper evaluates its approach on instances derived from CETSP instances presented in Mennell (2009), specifically the "bubbles" series. These instances are characterized by varying numbers of target circles and overlapping neighborhood structures. The authors also use instances like "concentricCircles" and "rotatingDiamonds" for specific analyses. For TDDP, instances like "team5_499" and "kroD100" are used.

Key Insights and Ideas

  • Overlaps as an Advantage: Instead of treating overlapping neighborhoods as a problem, CRaSZe-AntS leverages them by aggregating prizes within Steiner Zones, simplifying the problem and improving efficiency.
  • RSZD's Superiority: The new RSZD scheme significantly outperforms previous discretization methods (like IPD) by providing better layouts for Steiner Zones, leading to faster computation and higher solution quality.
  • Hybridization is Key: Combining metaheuristics like PSO and ACS is crucial for effectively handling the different aspects of CEOP and CEOP-N – PSO for continuous position optimization within complex regions and ACS for discrete sequence optimization.
  • CEOP-N's Real-World Relevance: The introduction of non-uniform costs makes the problem more applicable to scenarios like truck-and-drone delivery, where factors like drone efficiency and truck speed vary.

Key Results

  • Significant Speedup: CRaSZe-AntS achieved an averaged 140.44% increase in prize collection and a 55.18% reduction in algorithm execution time compared to single-neighborhood strategies for CEOP-N.
  • Discretization Improvement: RSZD, when used with ACS, was approximately 30 times faster and yielded a 24.32% prize increase compared to IPD-ACS on CEOP instances.
  • Robustness: CRaSZe-AntS demonstrated more robust performance with lower standard deviations in computation time and prize collection compared to benchmark algorithms like GRASP.
  • TDDP Performance: For TDDP, CRaSZe-AntS significantly outperformed the BE-PSO-IACS baseline, showing a marked reduction in computation time and a substantial increase in prize collection.

Limitations and Future Work

  • SZ Layout Optimization: While RSZD is effective, the paper suggests further enhancements could be made by incorporating minimum-angle strategies and decomposing high-degree SZs, as well as exploring boundary encoding for generalized Steiner Zones.
  • Computational Cost of Hybridization: Embedding ACS within PSO for CEOP-N can be computationally expensive for very large instances. Future work could explore alternative machine learning techniques like attention mechanisms or reinforcement learning.
  • Real-World Complexity: The current model is simplified. Future work could incorporate more realistic constraints, such as varying weather conditions affecting UAV flight, more complex UAV operation models, and three-dimensional coordinates.
  • Exact Methods: The paper notes that adapting exact methods like Branch-and-Bound for CEOP and CEOP-N is challenging due to the dynamic nature of solution length and remains an open research area.

Summary updated

BibTeX
@article{qian2024solving,
  author = {Qiuchen Qian and Yanran Wang and David Boyle},
  title = {{On solving close enough orienteering problems with overlapped neighborhoods}},
  journal = {Eur. J. Oper. Res.},
  year = {2024},
  doi = {10.1016/j.ejor.2024.05.032},
}
Figure