Genetic Algorithm for Combinatorial Path Planning: The Subtour Problem. (10th April 2011) - Giardini, Giovanni; Kalmár-Nagy, Tamás
Abstract : 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 ofn possible goals/targets, the optimal strategy is sought that connectsk ≤ 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.