Genetic algorithm for combinatorial path planning: the subtour problem (Q541476)

Summary: The purpose of this paper is to present a combinatorial planner for autonomous systems. The approach is demonstrated on the so-called subtour problem, a variant of the classical traveling salesman problem (TSP): given a set of \(n\) possible goals/targets, the optimal strategy is sought that connects \(k \leq n\) goals. The proposed solution method is a genetic algorithm coupled with a heuristic local search. To validate the approach, the method has been benchmarked against TSPs and subtour problems with known optimal solutions. Numerical experiments demonstrate the success of the approach.