ARTÍCULO
TITULO

An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator

Md. Sabir Hossain    
Ahsan Sadee Tanim    
Sadman Sakib Choudhury    
S. M. Afif Ibne Hayat    
Muhammad Nomani Kabir    
Mohammad Mainul Islam    

Resumen

The traveling salesman problem (TSP) is a famous NP-hard problem in the area of combinatorial optimization. It is utilized to locate the shortest possible route that visits every city precisely once and comes back to the beginning point from a given set of cities and distance. This paper proposes an efficient and effective solution for solving such a query. A modified crossover method using Minimal Weight Variable, Order Selection Crossover operator, a modified mutation using local optimization and a modified selection method using KMST is proposed. The crossover operator (MWVOSX) chooses a particular order from multiple orders which have the minimum cost and takes the remaining from the other parent in backward and forward order. Then it creates two new offspring. Further, it selects the least weight new offspring from those two offspring. The efficiency of the proposed algorithm is compared to the classical genetic algorithm. Comparisons show that our proposed algorithm provides much efficient results than the existing classical genetic algorithm.

 Artículos similares

       
 
Ravi U Kalkundri, Rajashri Khanai, Kalkundri Praveen     Pág. 30 - 37
With the increase in population, there is an increase in the number of car users drastically. Around the world, either millions of people die due to car accidents or they are severely injured by the accident. Most of the accidents occur due to lack of co... ver más

 
Edilson Marcelino Silva, Thais Destefani Ribeiro Furtado, Ariana Campos Frühauf, Joel Augusto Muniz, Tales Jesus Fernandes     Pág. e46893
Zinc uptake is essential for crop development; thus, knowledge about soil zinc availability is fundamental for fertilization in periods of higher crop demand. A nonlinear first-order kinetic model has been employed to evaluate zinc availability. Studies ... ver más

 
Elias Munapo     Pág. 6 - 10
The paper presents a new method for solving the 0?1 linear programming problems (LPs). The general 0?1 LPs are believed to be NP-hard and a consistent, efficient general-purpose algorithm for these models has not been found so far. Cutting planes an... ver más

 
?lena Kovalenko,Viktoriia Novoseltseva,Oleh Vasyliv,Olena Liapina,Olga Beregova     Pág. 14 - 25
Effective purification of natural and wastewater from heavy metals is a relevant environmental and national-economic problem. It can be solved by using plant-waste-derived biosorbents in water treatment technologies. They are formed in large quantities b... ver más

 
Oleh Pihnastyi,Daria Yemelianova,Dmytro Lysytsia     Pág. 54 - 60
Two classes of models for describing production flow lines are analyzed. The use of models of these classes for the design of highly efficient control systems of production lines, the technological route of which consists of a large number of technologic... ver más