Introduction
In logistics and telecommunications, the Orienteering Problem (OP) involves finding a path that maximizes the total prize collected within a fixed budget (e.g., time or distance). The Close Enough Orienteering Problem (CEOP) extends this by allowing an agent to collect a prize simply by entering a circular neighborhood around a target, rather than visiting an exact point. This model is particularly relevant for Unmanned Aerial Vehicle (UAV) missions and sensor data collection.
Traditional approaches often treat these target neighborhoods as isolated entities. However, in dense environments, these circles frequently overlap. This paper introduces a novel framework, CRaSZe-AntS (Randomized Steiner Zone Discretization - Ant Colony System), which treats these overlaps as strategic assets rather than geometric constraints.
Problem Formulation and the Steiner Zone Concept
The core innovation of this research is the exploitation of Steiner Zones (SZs)—the convex regions formed by the intersection of multiple target circles. By visiting a single point within a Steiner Zone, an agent can collect prizes from all overlapping circles simultaneously, significantly increasing efficiency.
As shown in Figure 1, the Steiner Zone $\Omega$ is bounded by circular arcs. The algorithm discretizes the continuous search space by focusing on these zones and their vertices ($v'_1, v'_2, v'_3$), transforming a complex continuous optimization problem into a more manageable discrete one.
Methodology: The CRaSZe-AntS Framework
The CRaSZe-AntS algorithm employs a multi-stage approach to solve the CEOP:
- Randomized Steiner Zone Discretization (RSZD): Unlike traditional sweep-line algorithms, RSZD uses a randomized approach to rapidly identify Steiner Zones and their vertices. This significantly reduces the computational overhead of map discretization.
- Hybrid Metaheuristics:
- Ant Colony System (ACS): Determines the optimal sequence of Steiner Zones to visit.
- Particle Swarm Optimization (PSO): Used for the non-uniform variant (CEOP-N), where collection costs vary within a neighborhood (e.g., signal strength degradation). PSO fine-tunes the exact coordinates within a zone to minimize these costs.
- Inherited Ant Colony System (IACS): A novel mechanism where the pheromone trails of the "ants" are updated based on knowledge inherited from previous PSO iterations, accelerating convergence.
- Arc Search Algorithm: A local search operator that optimizes the path by sliding waypoints along the circular boundaries of the Steiner Zones to minimize travel distance.
Experimental Evaluation
The framework was tested against standard benchmark instances (e.g., bubbles, kroD100, dsj1000) and a specific Truck-and-Drone Delivery Problem (TDDP) model.
Key Results:
- Prize Maximization: In TDDP scenarios, the Steiner Zone strategy led to a 140.44% increase in prize collection compared to methods that ignore overlaps.
- Computational Efficiency: The RSZD scheme proved to be 30 times faster than state-of-the-art Internal Point Discretization (IPD) while improving solution quality by approximately 24%.
- Non-Uniform Performance: In scenarios with variable collection costs, the algorithm reduced execution time by an average of 55.18%.
Conclusion
By shifting the focus from individual targets to overlapping Steiner Zones, the CRaSZe-AntS framework provides a robust and efficient solution for the Close Enough Orienteering Problem. This approach not only maximizes prize collection but also scales effectively to large-scale instances with up to 1,000 targets. Future work will explore the application of deep reinforcement learning and extending the model to 3D environments for more complex UAV mission planning.
Summary updated