Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm
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 funct...
Збережено в:
| Дата: | 2024 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2024
|
| Онлайн доступ: | http://mcm-math.kpnu.edu.ua/article/view/313364 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Репозитарії
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543279091286016 |
|---|---|
| author | Івохін, Євген Юштін, Костянтин |
| author_facet | Івохін, Євген Юштін, Костянтин |
| author_sort | Івохін, Євген |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2024-10-14T19:18:41Z |
| description | 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. |
| first_indexed | 2025-07-17T10:44:04Z |
| format | Article |
| id | mcm-mathkpnueduua-article-313364 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:44:04Z |
| publishDate | 2024 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-3133642024-10-14T19:18:41Z Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm Двоетапний метод розв’язання задачі комівояжера на основі генетичного алгоритму Івохін, Євген Юштін, Костянтин 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. Одним з основних завдань логістики є пошук найбільш ефективного маршруту в задачі комівояжера на заданій транспортній мережі, що дозволяє обслуговувати максимальну кількість споживачів, враховуючи певні критерії. У типовій задачі комівояжера критеріальною функцією найчастіше виступає довжина або тривалість маршруту. Однак, така постановка не враховує суб'єктивність оцінок тривалості переміщень за етапами, що може бути пов’язано з різними об’єктивними та суб’єктивними факторами. Розглянуто постановку задачі комівояжера з нечітко визначеною тривалістю переміщень між вузлами мережі. В основу підходу для розв’язання задачі покладено генетичний алгоритм з вдосконаленими процедурами мутації та формування різноманітності в популяціях. Для формалізації нечітких величин застосовується трапецієподібні нечіткі числа, що подаються в узагальненому випадку, який базується на застосуванні гаусовського розподілу та відповідних характеристик. На основі поєднання генетичного алгоритму та методу кластеризації Варда запропоновано двоетапну схему розв’язування оптимізаційної задачі комівояжера на заданій транспортній мережі. На першому етапі проводиться процедура кластеризації за методом Варда. На другому етапі на основі отриманого набору кластерів та знайдених оптимальних міжкластерних відстаней проводиться оптимізація тривалості маршрутів всередині кластерів. Для тестування ефективності створеного методу згенеровано два види моделей: з обмеженою кількістю доступних шляхів та з повнозв'язною топологією. Проведено обчислювальні експерименти по застосуванню розробленого методу для розв’язання задачі комівояжера з тривалістю переміщень між містами у вигляді нечітких чисел. Проведено порівняння результатів чисельних розрахунків. Отримані результати показали ефективність застосування попередньої кластеризації при використанні генетичного алгоритму для знаходження найкращих локальних оптимумів за однаковими вхідними параметрами. Кам'янець-Подільський національний університет імені Івана Огієнка 2024-09-12 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/313364 10.32626/2308-5878.2024-25.82-95 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2024: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 25; 82-95 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2024: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 25; 82-95 2308-5878 10.32626/2308-5878.2024-25 uk http://mcm-math.kpnu.edu.ua/article/view/313364/304369 |
| spellingShingle | Івохін, Євген Юштін, Костянтин Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title | Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title_alt | Двоетапний метод розв’язання задачі комівояжера на основі генетичного алгоритму |
| title_full | Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title_fullStr | Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title_full_unstemmed | Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title_short | Two-Stage Method for Solving the Traveling Salesman Problem Using the Genetic Algorithm |
| title_sort | two-stage method for solving the traveling salesman problem using the genetic algorithm |
| url | http://mcm-math.kpnu.edu.ua/article/view/313364 |
| work_keys_str_mv | AT ívohínêvgen twostagemethodforsolvingthetravelingsalesmanproblemusingthegeneticalgorithm AT ûštínkostântin twostagemethodforsolvingthetravelingsalesmanproblemusingthegeneticalgorithm AT ívohínêvgen dvoetapnijmetodrozvâzannâzadačíkomívoâžeranaosnovígenetičnogoalgoritmu AT ûštínkostântin dvoetapnijmetodrozvâzannâzadačíkomívoâžeranaosnovígenetičnogoalgoritmu |