A genetic algorithm to solve 3D traveling salesman problem with initial population based on a GRASP algorithm
Issue title: Selected papers from the ISCA International Conference on Software Engineering and Data Engineering, and the ISCA International Conference on Computer Applications in Industry and Engineering, 2015, and Invited Papers
Guest editors: Takaaki Goto and Narayan C. Debnath
Affiliations: Department of Engineering, Pontificia Universidad Catolica del Peru Lima, Lima, Peru
Correspondence:
[*]
Corresponding author: Manuel Tupia, Department of Engineering, Pontificia Universidad Catolica del Peru Lima, Lima 32, Peru. E-mail:tupia.mf@pucp.edu.pe
Abstract: In this paper, the problem of obtaining optimal routes on tridimensional
environments is discussed. This scenario is called as Traveler Salesman
Problem (TSP 3D-variation). As is widely known, TSP has NP-complexity so is
necessary to apply techniques to solve it approximately (no exacts solutions
available). The purpose of this research is to present a genetic algorithm
to solve 3D-TSP variation. These kind of evolutionary algorithms are ideal
for solving complex problems where necessary rearrangements and route
optimization. In case of genetic algorithms, optimal solutions appear faster
depending on the quality of initial population, so theory recommends using
metaheuristics for generating this population. In this study, it has used a
metaheuristic GRASP algorithm to generate the initial population and, over
it, apply the genetic operators proposed for optimizing individuals
obtained. The results have optimal routes of movement and displacement and
are directly applicable in the storage industry.
