INTELLIGENT PATH OPTIMIZATION OF TRAVELLING SALESMAN PROBLEM BASED ON MODIFY GENETIC ALGORITHM

Aug 8, 2023

Journal altinbsa jornal

The travelling salesman problem (TSP) is one of the oldest and most common problems that should be optimized using one of the optimization algorithms to make the salesman's travel itinerary to be short and non-repeated. The solution for travelling salesman problem becomes computationally complex because there are a large number of cities and the travelling salesman requires to visit each city once with shortest path. Multiple algorithms are used to find a good solution to this problem such as genetic algorithm. This study used modify genetic algorithm which is depend on a set of biological changes that occur in living organisms, through a set of steps (natural selection, population, crossover, and mutation). A new intersection method is proposed in this thesis, which uses three techniques together in intersection, namely (flipping, swapping, and sliding). The experiments were applied to the variant number of cities which are 10,50 and 150,200 with two scenarios. In the first scenario, each experiment, a fixed number of iteration (100000) and population size (150) were chosen, the execution time to find solution was (82.00 seconds), (111.41 seconds), (151.10 seconds) and (240.41 seconds) for cities (10,20,100,200), respectively. In the second scenario, the population size was set to (50) or (100) and the number of iteration set to (10000) or (50000). The results to find solution were (03.2 seconds), (04.33 seconds), (05.47 seconds), and (35.05 seconds) for cities (10,20,100,200), respectively, and the results showed that each of (iteration, population) is directly proportional to the number of cities, with the use of the three techniques together, we get a shorter path and less time comparing with the performance of the traditional genetic algorithm.

Read Publication