Home   >   CSC-OpenAccess Library   >    Manuscript Information
Genetic Algorithm For The Travelling Salesman Problem using Enhanced Sequential Constructive Crossover Operator
Hachemi Bennaceur, Entesar Alanzi
Pages - 42 - 52     |    Revised - 31-05-2017     |    Published - 30-06-2017
Volume - 11   Issue - 3    |    Publication Date - June 2017  Table of Contents
MORE INFORMATION
KEYWORDS
Traveling Salesman Problem, Optimization Problem, Genetic Algorithm, Sequential Constructive Crossover.
ABSTRACT
Traveling Salesman Problem (TSP) is one of the most important combinatorial optimization problems. There are many researches to improve the genetic algorithm for solving TSP. The Sequential Constructive crossover (SCX) is one of the most efficient crossover operators for solving optimization problems. In this paper, we propose a new crossover operator, named Enhanced Sequential Constructive crossover operator (ESCX), which modifies and improves the criteria of SCX operator in construction of offspring. ESCX considers, in addition to the real cost of the traversed cities, an estimation cost of the remaining tour, and it selects the next node to build the offspring based on that evaluation. The experimental results comparing the proposed crossover operator to the SCX operator on some benchmark TSPLIB instances show the effectiveness of our proposed operator.
1 Google Scholar 
2 BibSonomy 
3 Doc Player 
4 Scribd 
5 SlideShare 
A. Rao and S. Hegde. "Literature Survey On Travelling Salesman Problem Using Genetic Algorithms". International Journal of Advanced Research in Education Technology (IJARET), vol. 2, 2015.
A. Saiyed, "The Traveling Salesman problem", Indiana State University, vol. 2, pp. 1-15, 2012.
B.F. Al-Dulaimi and H. A. Ali. "Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)". International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, vol. 2, 2008.
D. Nandi, S. Samanta and A. De. "An Approach to Analyze the Performance of Inversion Sequence Crossover and Sequential Constructive Crossover Along With Greedy Mutation Operator for Solving TSP Using Genetic Algorithm," ICCCM 2014, International Conference on Computing, Communication & Manufacturing, 2014.
D. Satyananda. "Modification of Crossover Operator on GA Application for TSP, "Proceeding of International Conference On Research, Implementation And Education Of Mathematics And Sciences, 2015.
F. Imeson and S. Smith."A Language For Robot Path Planning in Discrete Environments: The TSP with Boolean Satis?ability Constraints," Proceedings of the IEEE Conf. on Robotics and Automation, May 2014.
G. Gopal, R. Kumar, I. Jawa and N. Kumar. "Enhanced Order Crossover for Permutation Problems". International Journal of Innovative Research in Science, Engineering, and Technology, vol. 4, no. 2, 2015.
G. Reinelt. "TSPLIB." Internet: https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ , Jan, 1, 2013 [Jun. 3, 2017].
H. Gress and E. Selene. "The job shop scheduling problem solved with the travel salesman problem and genetic algorithms," https://repository.uaeh.edu.mx/bitstream/handle/123456789/15273, Apr. 14, 2017.
H. Rasit and N. Erdogan, "Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster". The International Journal of Soft Computing and Software Engineering [JSCSE], vol. 3, no. 3, 2013.
I. Gupta and A. Par. (2011, Aug.). "Study of Crossover operators in Genetic Algorithm for Travelling Salesman Problem." [On-line]. 2(4), pp. 194-198. Available: www.ijarcs.info [May 1, 2017].
J. Singh and A. Solanki. "An Improved Genetic Algorithm on MapReduce Framework Using Hadoop Cluster for DNA Sequencing". The International Journal of Advanced Research in Computer Science and Software Engineering, vol. 5, 2015.
K. Miclaus, R. Pratt and M. Galati. "The Traveling Salesman Traverses the Genome: Using SAS® Optimization in JMP® Genomics to build Genetic Maps", SAS global forum, 2012.
K. Puljic and R. Manger. "Comparison of eight evolutionary crossover operators for the vehicle routing problem". Journal of mathematical communications, 2013.
L. Šanchez, J. Armenta and V. Ramirez. "Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem," Difu100ci@ Revista en Ingeniería y Tecnología, UAZ, vol. 8, 2014.
N. Bansal, A. Blum, S. Chawla and A. Meyerson. "Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows," Proceedings of the thirty-sixth annual ACM symposium on Theory of Computing (STOC), 2004, pp. 166-174.
O. Sallabi and Y. El-Haddad. "An Improved Genetic Algorithm to Solve the Traveling Salesman Problem". International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 3, 2009.
P. Dinh, H. Binh and B. Lam. "New Mechanism of Combination Crossover Operators in Genetic Algorithm for Solving the Traveling Salesman Problem". Springer International Publishing Switzerland, Knowledge and Systems Engineering, vol. 326, 2015.
P. Larranaga, C.M.H. Kuijpers, R.H. Murga, I. Innza and S. Dizdarevic."Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators", Artificial Intelligence Review 13: 129-170, 1999.
R. Matai, S. Singh and M. L. Mittal. "Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches," in TRAVELING SALESMAN PROBLEM, THEORY AND APPLICATIONS, InTech, Dec. 2010.
S. Abdel-Moetty and A. Heakil. "Enhanced Traveling Salesman Problem Solving using Genetic Algorithm Technique with modified Sequential Constructive Crossover Operator". The International Journal of Computer Science and Network Security (IJCSNS), vol. 12, 2012.
S. Ray, S. Bandyopadhyay and S. Pal, "New operators of genetic algorithms for traveling salesman problem",Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.
S. Ray, S. Bandyopadhyay and S. Pal. "New genetic operators for solving TSP: Application to microarray gene ordering.". Springer-Verlag Berlin Heidelberg, pp. 617-622, 2005.
W. Zeng and R. L. Church. "Finding shortest paths on real road networks: the case for A*". International Journal of Geographical Information Science, vol. 23, pp. 531-543, Jun. 2009.
Z. Ahmed. "Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator". International Journal of Biometrics & Bioinformatics (IJBB), vol. 3, 2010.
Professor Hachemi Bennaceur
Faculty of Computer and Information Sciences Department of Computer Science Al Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, Saudi Arabia - Saudi Arabia
hamnasser@imamu.edu.sa
Mr. Entesar Alanzi
Department of Computer Science Al Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, Saudi Arabia - Saudi Arabia


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS