Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm

• Дата: 2024
• Автори: Івохін, Євген, Юштін, Костянтин
• Формат: Стаття
• Мова: Українська
• Опубліковано: Кам'янець-Подільський національний університет імені Івана Огієнка 2024
• Онлайн доступ: http://mcm-math.kpnu.edu.ua/article/view/313364
• Назва журналу: Mathematical and computer modelling. Series: Physical and mathematical sciences

One of the main tasks in logistics is to find the most efficient route in the traveling salesman problem on a given transportation network, allowing for the servicing of the maximum number of customers while considering certain criteria. In the typical traveling salesman problem, the objective function is most often the route length or duration. However, such a formulation does not account for the subjectivity in evaluating the travel durations at different stages, which may be influenced by various objective and subjective factors. The problem of the traveling salesman with fuzzily defined travel durations between network nodes is considered. The approach to solving the problem is based on a genetic algorithm with enhanced mutation procedures and population diversity generation. Trapezoidal fuzzy numbers are used to formalize fuzzy values, presented in the generalized case based on the application of Gaussian distribution and corresponding characteristics. A two-stage scheme for solving the optimization problem of the traveling salesman on a given transportation network is proposed, combining the genetic algorithm and Ward's clustering method. In the first stage, a clustering procedure is conducted using Ward's method. In the second stage, based on the obtained set of clusters and the identified optimal inter-cluster distances, route duration optimization is performed within the clusters. To test the efficiency of the developed method, two types of models were generated: one with a limited number of available paths and one with a fully connected topology. Computational experiments were conducted to apply the developed method to solving the traveling salesman problem with travel durations between cities represented as fuzzy numbers. A comparison of numerical calculation results was performed. The obtained results demonstrated the effectiveness of preliminary clustering when using the genetic algorithm to find the best local optima under the same input parameters.