An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator
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...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Politeknik Elektronika Negeri Surabaya
2019
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/27534/1/An%20Efficient%20Solution%20to%20Travelling%20Salesman%20Problem.pdf |
| _version_ | 1796993895295352832 |
|---|---|
| author | Hossain, Md. Sabir Tanim, Ahsan Sadee Choudhury, Sadman Sakib Hayat, S. M. Afif Ibne M. Nomani, Kabir Islam, Mohammad Mainul |
| author_facet | Hossain, Md. Sabir Tanim, Ahsan Sadee Choudhury, Sadman Sakib Hayat, S. M. Afif Ibne M. Nomani, Kabir Islam, Mohammad Mainul |
| author_sort | Hossain, Md. Sabir |
| collection | UMP |
| description | 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. |
| first_indexed | 2024-03-06T12:40:17Z |
| format | Article |
| id | UMPir27534 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2024-03-06T12:40:17Z |
| publishDate | 2019 |
| publisher | Politeknik Elektronika Negeri Surabaya |
| record_format | dspace |
| spelling | UMPir275342020-03-30T00:07:46Z http://umpir.ump.edu.my/id/eprint/27534/ An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator Hossain, Md. Sabir Tanim, Ahsan Sadee Choudhury, Sadman Sakib Hayat, S. M. Afif Ibne M. Nomani, Kabir Islam, Mohammad Mainul QA76 Computer software 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. Politeknik Elektronika Negeri Surabaya 2019-12-31 Article PeerReviewed pdf en cc_by_nc_sa_4 http://umpir.ump.edu.my/id/eprint/27534/1/An%20Efficient%20Solution%20to%20Travelling%20Salesman%20Problem.pdf Hossain, Md. Sabir and Tanim, Ahsan Sadee and Choudhury, Sadman Sakib and Hayat, S. M. Afif Ibne and M. Nomani, Kabir and Islam, Mohammad Mainul (2019) An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator. EMITTER International Journal of Engineering Technology, 7 (2). pp. 480-493. ISSN 2355-391X. (Published) https://doi.org/10.24003/emitter.v7i2.380 https://doi.org/10.24003/emitter.v7i2.380 |
| spellingShingle | QA76 Computer software Hossain, Md. Sabir Tanim, Ahsan Sadee Choudhury, Sadman Sakib Hayat, S. M. Afif Ibne M. Nomani, Kabir Islam, Mohammad Mainul An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title | An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title_full | An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title_fullStr | An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title_full_unstemmed | An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title_short | An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator |
| title_sort | efficient solution to travelling salesman problem using genetic algorithm with modified crossover operator |
| topic | QA76 Computer software |
| url | http://umpir.ump.edu.my/id/eprint/27534/1/An%20Efficient%20Solution%20to%20Travelling%20Salesman%20Problem.pdf |
| work_keys_str_mv | AT hossainmdsabir anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT tanimahsansadee anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT choudhurysadmansakib anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT hayatsmafifibne anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT mnomanikabir anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT islammohammadmainul anefficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT hossainmdsabir efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT tanimahsansadee efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT choudhurysadmansakib efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT hayatsmafifibne efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT mnomanikabir efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator AT islammohammadmainul efficientsolutiontotravellingsalesmanproblemusinggeneticalgorithmwithmodifiedcrossoveroperator |