An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem
Journal Title: Engineering, Technology & Applied Science Research - Year 2017, Vol 7, Issue 6
Abstract
The generalized traveling salesman problem (GTSP) deals with finding the minimum-cost tour in a clustered set of cities. In this problem, the traveler is interested in finding the best path that goes through all clusters. As this problem is NP-hard, implementing a metaheuristic algorithm to solve the large scale problems is inevitable. The performance of these algorithms can be intensively promoted by other heuristic algorithms. In this study, a search method is developed that improves the quality of the solutions and competition time considerably in comparison with Genetic Algorithm. In the proposed algorithm, the genetic algorithms with the Nearest Neighbor Search (NNS) are combined and a heuristic mutation operator is applied. According to the experimental results on a set of standard test problems with symmetric distances, the proposed algorithm finds the best solutions in most cases with the least computational time. The proposed algorithm is highly competitive with the published until now algorithms in both solution quality and running time.
Authors and Affiliations
H. Jafarzadeh, N. Moradinasab, M. Elyasi
Keywords
Related Articles
- EP ID EP155266
- DOI -
- Views 256
- Downloads 0
Reliability-Based Design Optimization of Trusses with Linked-Discrete Design Variables using the Improved Firefly Algorithm
In this paper, an approach for conducting a Reliability-Based Design Optimization (RBDO) of truss structures with linked-discrete design variables is proposed. The sections of the truss members are selected from the AISC...
RSW Junctions of Advanced Automotive Sheet Steel by Using Different Electrode Pressures
Based on this study, the effects of the different types of welding currents and electrode pressures on the tensile shear properties of the resistance spot welding (RSW) which are the joints of the commercial DP600 sheet...
Effect of Prepackaged Polymer on Compressive, Tensile and Flexural Strength of Mortar
Synthetic materials, like various types of polymers, are introduced as having cementitious qualities, which improve the system of pores of mortars and concretes by the formations of polymer films and thereby enhancing th...
Alkali-Aggregate Reaction: A study of the influence of the petrographic characteristics of volcanic rocks
When the rock involved in the alkali-aggregate reaction (AAR) is volcanic, the matter present in the interstices of the grains, called mesostasis is considered responsible for the expansions. Mesostasis is a residue whic...
Simulating Nonlinear Oscillations of Viscoelastically Damped Mechanical Systems
The aim of this work is to propose a mathematical model in terms of an exact analytical solution that may be used in numerical simulation and prediction of oscillatory dynamics of a one-dimensional viscoelastic system ex...