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 128
- Downloads 0
Classifying three Communities of Assam Based on Anthropometric Characteristics using R Programming
The study of anthropometric characteristics of different communities plays an important role in design, ergonomics and architecture. As the change of life style, nutrition and ethnic composition of different communities...
Intelligent Mobility Management Model for Heterogeneous Wireless Networks
Growing consumer demands for access of communication services in a ubiquitous environment is a driving force behind the development of new technologies. The rapid development in communication technology permits the end u...
Modified Grapheme Encoding and Phonemic Rule to Improve PNNR-Based Indonesian G2P
A grapheme-to-phoneme conversion (G2P) is very important in both speech recognition and synthesis. The existing Indonesian G2P based on pseudo nearest neighbour rule (PNNR) has two drawbacks: the grapheme encoding does n...
An Empirical Investigation on a Tool-Based Boilerplate Technique to Improve Software Requirement Specification Quality
The process of producing software requirements specification (SRS) is known to be challenging due to the amount of effort, skills and experience needed in writing good quality SRS. A tool-based boilerplate technique is i...
Performance Evaluation of Anti-Collision Algorithms for RFID System with Different Delay Requirements
The main purpose of Radio-frequency identification (RFID) implementation is to keep track of the tagged items. The basic components of an RFID system include tags and readers. Tags communicate with the reader through a s...