Research Article Open Access

An Improved Genetic Algorithm for the Traveling Salesman Problem with Multi-Relations

Supat Patvichaichod

Abstract

Problem statement: The aim of this research is to investigate the Traveling Salesman Problems with Multi-Relations (TSPMR) in which each of the vertices has several edges and different weights. The study concerns the weights fluctuated by time in which the problem has more complexity than general TSP problem. However, this type of problem closes to the real-world situation in engineering aspect. Approach: The new genetic algorithm was developed specially for the TSPMR. With the new genetic algorithm, the new coding system is a mixer between the integer numbers (represents the vertices) and the binary (represents the edges). The experiments were done to investigate the suitable input variables, which are a population size, generation, crossover rate and mutation rate. Results: The suitable generation between 300 and 400, the suitable crossover rate between 20 and 60% and the suitable mutation rate between 30 and 80%. Conclusion: The new developed method in this research is found to efficiently solve the problem with less than 100 vertices, which can reduce 50% of the transportation cost. In case of 100 -1,000 vertices problem, the transportation cost is reduced approximately by 20%. If the vertices are more than 1,000, the transportation cost can be reduced less than 20%. For the large size of problem as 30,000 vertices, the transportation cost is reduced for 6.07%.

Journal of Computer Science
Volume 7 No. 1, 2011, 70-74

DOI: https://doi.org/10.3844/jcssp.2011.70.74

Submitted On: 26 November 2010 Published On: 14 January 2011

How to Cite: Patvichaichod, S. (2011). An Improved Genetic Algorithm for the Traveling Salesman Problem with Multi-Relations. Journal of Computer Science, 7(1), 70-74. https://doi.org/10.3844/jcssp.2011.70.74

  • 2,702 Views
  • 2,758 Downloads
  • 2 Citations

Download

Keywords

  • Genetic algorithm
  • traveling salesman problem
  • traveling salesman problem with multi-relations (TSPMR)
  • Generalized Chromosome Genetic Algorithm (GCGA)
  • Gene Expression Messy Genetic Algorithm or (GEMGA)
  • vertices
  • fluctuated
  • Hierarchical Genetic Algorithms (HGA)
  • Successive Zooming Genetic Algorithm (SZGA)