Mathematical Problems in Engineering
Volume 2011 (2011), Article ID 483643, 31 pages
http://dx.doi.org/10.1155/2011/483643
Research Article

Genetic Algorithm for Combinatorial Path Planning: The Subtour Problem

Department of Aerospace Engineering, College Station, Texas A&M University, TX 77843, USA

Received 2 May 2010; Revised 21 October 2010; Accepted 24 February 2011

Academic Editor: Dane Quinn

Copyright © 2011 Giovanni Giardini and Tamás Kalmár-Nagy. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 of 𝑛 possible goals/targets, the optimal strategy is sought that connects 𝑘 𝑛 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.