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 246
- Downloads 0
A Quantitative Measure For Evaluating Project Uncertainty Under Variation And Risk Effects
The effects of uncertainty on a project and the risk event as the consequence of uncertainty are analyzed. The uncertainty index is proposed as a quantitative measure for evaluating the uncertainty of a project. This is...
Interface Structure and Elements Diffusion of As-Cast and Annealed Ductile Iron/Stainless Steel Bimetal Castings
Bimetal casting is considered to a promising technique for the production of high performance function materials. Heat treatment process for bimetal castings became an essential tool for improving interface structure and...
Modeling and Control of a DFIG-Based Wind Turbine During a Grid Voltage Drop
Doubly-fed induction generators (DFIG) are widely used in wind energy generation systems. During a grid voltage drop, performance is degraded with rotor over current deteriorating the fault-ride through (FRT) capability...
Anti-Swing Fuzzy Controller Applied in a 3D Crane System
It is well known that fuzzy logic can be used in the control of complex systems described by highly nonlinear mathematical models. However, the main difficulty in the design of a fuzzy controller comes with the adjustmen...
BlindSense: An Accessibility-inclusive Universal User Interface for Blind People
A large number of blind people use smartphone-based assistive technology to perform their common activities. In order to provide a better user experience the existing user interface paradigm needs to be revisited. A new...