Cover Image

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Hossain, Md. Sabir, Tanim, Ahsan Sadee, Choudhury, Sadman Sakib, Hayat, S. M. Afif Ibne, M. Nomani, Kabir, Islam, Mohammad Mainul
Format: Article
Language:English
Published: Politeknik Elektronika Negeri Surabaya 2019
Subjects:
QA76 Computer software
Online Access:http://umpir.ump.edu.my/id/eprint/27534/1/An%20Efficient%20Solution%20to%20Travelling%20Salesman%20Problem.pdf
http://umpir.ump.edu.my/id/eprint/27534/
https://doi.org/10.24003/emitter.v7i2.380
https://doi.org/10.24003/emitter.v7i2.380
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.ump.umpir.27534
record_format eprints
spelling my.ump.umpir.275342020-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 https://doi.org/10.24003/emitter.v7i2.380 https://doi.org/10.24003/emitter.v7i2.380
institution Universiti Malaysia Pahang
building UMP Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Pahang
content_source UMP Institutional Repository
url_provider http://umpir.ump.edu.my/
language English
topic QA76 Computer software
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
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.
format Article
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
title 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_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_sort efficient solution to travelling salesman problem using genetic algorithm with modified crossover operator
publisher Politeknik Elektronika Negeri Surabaya
publishDate 2019
url http://umpir.ump.edu.my/id/eprint/27534/1/An%20Efficient%20Solution%20to%20Travelling%20Salesman%20Problem.pdf
http://umpir.ump.edu.my/id/eprint/27534/
https://doi.org/10.24003/emitter.v7i2.380
https://doi.org/10.24003/emitter.v7i2.380
_version_ 1662754771239436288
score 13.211869

Similar Items