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 109
- Downloads 0
Proposal and Implementation of MPLS Fuzzy Traffic Monitor
Multiprotocol Label Switched Networks need highly intelligent controls to manage high volume traffic due to issues of traffic congestion and best path selection. The work demonstrated in this paper shows results from sim...
Comparative Study of Bayesian and Energy Detection Including MRC Under Fading Environment in Collaborative Cognitive Radio Network
The most important component of Cognitive Radio Network (CRN) is to sense the underutilised spectrum efficiently in fading environment for incorporating the increasing demand of wireless applications. The result of spect...
Big Data Processing for Full-Text Search and Visualization with Elasticsearch
In this paper, the task of using Big Data to identify specific individuals on the indirect grounds of their interaction with information resources is considered. Possible sources of Big Data and problems related to its p...
Verification of Statecharts Using Data Abstraction
We present an approach for verifying Statecharts including infinite data spaces. We devise a technique for checking that a formula of the universal fragment of CTL is satisfied by a specification written as a Statechart....
Detection and Classification of Mu Rhythm using Phase Synchronization for a Brain Computer Interface
Phase synchronization in a brain computer interface based on Mu rhythm is evaluated by means of phase lag index and weighted phase lag index. In order to detect and classify the important features reflected in brain sign...