Genetic Algorithm for Combinatorial Path Planning : The Subtour Problem

Abstract EN

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≤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.