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 129
- Downloads 0
LPA Beamformer for Tracking Nonstationary Accelerated Near-Field Sources
In this paper, a computationally very efficient algorithm for direction of arrival (DOA) as well as range parameter estimation is proposed for near-field narrowband nonstationary accelerated moving sources. The proposed...
Efficient Load Balancing Routing Technique for Mobile Ad Hoc Networks
The mobile ad hoc network (MANET) is nothing but the wireless connection of mobile nodes which provides the communication and mobility among wireless nodes without the need of any physical infrastructure or centralized d...
A New PHP Discoverer for Modisco
MoDisco is an Eclipse Generative Modeling Technologies project (GMT Project) intended to make easier the design and building of model-based solutions that are dedicated to legacy systems Model-Driven Reverse Engineering...
A Congestion Avoidance Approach in Jumbo Frame-enabled IP Network
Jumbo frame is as an approach that allows for higher utilization of larger packet sizes on a domain-wise basis, decreasing the number of packets processed by core routers while not having any adverse impact on the...
On the Performance of the Predicted Energy Efficient Bee-Inspired Routing (PEEBR)
The Predictive Energy Efficient Bee Routing PEEBR is a swarm intelligent reactive routing algorithm inspired from the bees food search behavior. PEEBR aims to optimize path selection in the Mobile Ad-hoc Network MANET ba...