کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
394789 | 665842 | 2008 | 13 صفحه PDF | دانلود رایگان |
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.
Journal: Information Sciences - Volume 178, Issue 16, 15 August 2008, Pages 3275–3287