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 262
- Downloads 0
The Effectiveness of High Quality Supplementary Cementitious Materials for Mitigating ASR Expansion in Concrete with High Alkali Content
Alkali silica reaction (ASR) is influenced by external factors such as the surrounding environment of high alkalinity. Countries with cold climate have a high probability to be exposed to high concentrations of NaCl solu...
A Cluster-based Approach Towards Detecting and Modeling Network Dictionary Attacks
In this paper, we provide an approach to detect network dictionary attacks using a data set collected as flows based on which a clustered graph is resulted. These flows provide an aggregated view of the network traffic i...
Biodiesel Production Potential from Native Tehran Oil Crops Using GIS
One of the main factors in the alternative fuel economy is the primary raw materials. Importing raw materials and preparation conditions for cultivation of non-native species require high expenditure. Therefore, using na...
Modeling of Fatigue Crack Propagation in Aluminum Alloys Using an Energy Based Approach
Materials fatigue is a particularly serious and unsafe kind of material destruction. Investigations of the fatigue crack growth rate and fatigue life constitute very important and complex problems in mechanics. The under...
Implementation of MPPT Algorithm and Supervision of Shading on Photovoltaic Module
This paper presents an implementation of MPPT (maximum power point tracking) algorithm based on real-time measurements and on model-based simulation. For the supervision of a photovoltaic module, different cases of shadi...