Path planning on a cuboid using genetic algorithms

The Traveling Salesman Problem (TSP) is one of the most extensively studied problems in the fields of Combinatorial Optimization and Global Search Heuristics. A variety of heuristic algorithms are available for solving Euclidean TSP, and Planar TSPs. However, optimization on a cuboid has potential applications for areas like path planning on the faces of buildings, rooms, furniture, books, and products or simulating the behaviors of insects. In this paper, we address a variant of the TSP in which all points (cities) and paths (solution) are on the faces of a cuboid. We develop an effective hybrid method based on genetic algorithms and 2-opt to adapt the Euclidean TSP to the surface of a cuboid. The method was tested on some benchmark problems from TSPLIB with satisfactory results. A web-based interactive visualization tool has also been developed using Java 3D, and optimization results for different point densities on the cuboid are presented. © 2008 Elsevier Inc. All rights reserved