Genetic Algorithm for Combinatorial Path Planning: The Subtour Problem. (10th April 2011)

• Record Type: Journal Article
• Authors: Giardini, Giovanni; Kalmár-Nagy, Tamás
• Other Names: Quinn Dane Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2011(2011)
• Publication Date: 2011-04-10
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2011/483643
• Languages: English
• ISSNs: 1024-123X

Abstract

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.