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 137
- Downloads 0
Pattern Discovery using Fuzzy FP-growth Algorithm from Gene Expression Data
The goal of microarray experiments is to identify genes that are differentially transcribed with respect to different biological conditions of cell cultures and samples. Hence, method of data analysis needs to be c...
Cookies and Sessions: A Study of what they are, how they can be Stolen and a Discussion on Security
Cookies and sessions are common and vital to a person’s experience on the Internet. The use of cookies was originally used to overcome a memoryless protocol while using a tiny amount of the system’s resources. Cookies ma...
Features Management and Middleware of Hybrid Cloud Infrastructures
The wide spread of cloud computing has identified the need to develop specialized approaches to the design, management and programming for cloud infrastructures. In the article were reviewed the peculiarities of th...
Analytical and Numerical Study of the Onset of Electroconvection in a Dielectric Nanofluid Saturated a Rotating Darcy Porous Medium
The simultaneous effect of rotation and a vertical AC electric field on the onset of electroconvection in a horizontal dielectric nanofluid layer saturated a Darcy porous medium is investigated. The boundaries of the die...
Fault Tolerant Platform for Application Mobility across devices
In the mobile era, users started using Smartphone’s, tablets and other handheld devices, The advances in telecom technologies like 3G accelerates the migration towards smart phones. But still battery power and fre...