Planning Searches Using an Orienteering-based Vehicle Routing Approach
Richard Tatum, Thomas A. Wettergren · OCEANS 2022, Hampton Roads · 2022
We develop a new efficient heuristic for search-based route planning as a vehicle routing problem. Given the nondeterministic polynomial time hardness or NP-hard nature of vehicle routing problems, robust formulations are often relegated to solutions by way of heuristics or numerical approximations. While the solutions are not optimal solutions for the original problem, they are often accepted as they are close enough. However, if we want to expand these approaches beyond the standard well-established vehicle routing problems (such as the traveling salesman problem and the orienteering problem), new solutions are sought. We present a greedy heuristic that uses simple rules that expands an initial path to find solutions to vehicle routing problems of the orienteering type, particularly modified to account for search planning. The resulting algorithm provides an efficient computation of an optimized search route that can take into account both vehicle and environmental conditions.