Solving the Free Clustered TSP Using a Memetic Algorithm

The free clustered travelling salesman problem (FCTSP) is an extension of the classical travelling salesman problem where the set of vertices is partitioned into clusters, and the task is to find a minimum cost Hamiltonian tour such that the vertices in any cluster are visited contiguously. This paper proposes the use of a memetic algorithm (MA) that combines the global search ability of Genetic Algorithm with local search to refine solutions to the FCTSP. The effectiveness of the proposed algorithm is examined on a set of TSPLIB instances with up to 318 vertices and clusters varying between 2 and 50 clusters. Moreover, the performance of the MA is compared with a Genetic Algorithm and a GRASP with path relinking. The computational results confirm the effectiveness of the MA in terms of both solution quality and computational time.

@article{Alsheddy2017,
  title     = {Solving the Free Clustered TSP Using a Memetic Algorithm},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {8},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Abdullah Alsheddy},
  doi       = {10.14569/IJACSA.2017.080852},
  url       = {https://doi.org/10.14569/IJACSA.2017.080852}
}