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 123
- Downloads 0
Development Process Patterns for Distributed Onshore/Offshore Software Projects
The globalisation of the commercial world, and the use of distributed working practices (Offshore/ onshore/ near-shore) has increased dramatically with the improvement of information and communication technologies. Many...
Low Complexity for Scalable Video Coding Extension of H.264 based on the Complexity of Video
Scalable Video Coding (SVC) / H.264 is one type of video compression techniques. Which provided more reality in dealing with video compression to provide an efficient video coding based on H.264/AVC. This ensures higher...
An Enhanced Automated Test Item Creation Based on Learners Preferred Concept Space
Recently, research has become increasingly inter-ested in developing tools that are able to automatically create test items out of text-based learning contents. Such tools might not only support instructors in creating t...
Ontology based Intrusion Detection System in Wireless Sensor Network for Active Attacks
WSNs are vulnerable to attacks and have deemed special attention for developing mechanism for securing against various threats that could effect the overall infrastructure. WSNs are open to miscellaneous classes of attac...
ComplexCloudSim: Towards Understanding Complexity in QoS-Aware Cloud Scheduling
The cloud is generally assumed to be homogeneous in most of the research efforts related to cloud resource management and the performance of cloud resource can be determined as it is predictable. However, a plethora of c...