Solving the Free Clustered TSP Using a Memetic Algorithm
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 8
Abstract
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.
Authors and Affiliations
Abdullah Alsheddy
Keywords
Related Articles
- EP ID EP260639
- DOI 10.14569/IJACSA.2017.080852
- Views 113
- Downloads 0
Stable Haptic Rendering For Physics Engines Using Inter-Process Communication and Remote Virtual Coupling
Availability of physics engines has significantly reduced the effort required to develop interactive applications concerning the simulation of physical world. However, it becomes a problem when kinesthetic feedback is ne...
Sentiment Analysis and Classification of Photos for 2-Generation Conversation in China
Appropriate photos can help the Chinese empty-nest elderly and young volunteers find common topics to promote communication. However, there are little researches on such photo in China. This paper used 40 online photos w...
Secure Steganography for Digital Images
The degree of imperceptibility of hidden image in the ‘Digital Image Steganography’ is mostly defined in relation to the limitation of Human Visual System (HVS), its chances of detection using statistical methods and its...
Mobile Data Collector Routing Protocol Scheme for Scalable Dense Wireless Sensor Network to Optimize Node’s Life
Wireless Sensor Networks (WSN) is a special kind of network communication architecture which has a very wide range of application and the cost-effectiveness of this architecture boosts its adaptability and usability. The...
Extending Unified Modeling Language to Support Aspect-Oriented Software Development
Aspect-Oriented Software Development (AOSD) is continuously gaining more importance as the complexity of software systems increases and requirement changes are high- rated. A smart way for making reuse of functionality w...