Genetic Algorithm for Combinatorial Path Planning: The Subtour Problem
Giovanni Giardini, Tamás Kalmár-Nagy · Mathematical Problems in Engineering · 2011
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 ofnpossible goals/targets, the optimal strategy is sought that connectsk≤ngoals. 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.