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

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