An evolutionary method for solving the traveling salesman problem
A method is proposed for solving the traveling salesman problem on the basis of an evolutionary approach, and their approbation in the pharmacy business has been carried out by optimizing the operation of the drug delivery device. A modification of the evolutionary algorithm has been developed, name...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Теми: | |
| Онлайн доступ: | http://drsp.ipri.kiev.ua/article/view/183550 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Data Recording, Storage & Processing |
Репозитарії
Data Recording, Storage & Processing| id |
drspiprikievua-article-183550 |
|---|---|
| record_format |
ojs |
| spelling |
drspiprikievua-article-1835502019-12-10T12:37:29Z An evolutionary method for solving the traveling salesman problem Розв’язання задачі комівояжера на основі еволюційного моделювання Oliinyk, A. О. Fedorchenko, Iе. М. Stepanenko, О. О. Rud, M. S. задача комівояжера генетичний алгоритм еволюційна модель мінімальна відстань граф optimal path traveling salesman problem genetic algorithm evolutionary algorithm minimum distance graph C Qt A method is proposed for solving the traveling salesman problem on the basis of an evolutionary approach, and their approbation in the pharmacy business has been carried out by optimizing the operation of the drug delivery device. A modification of the evolutionary algorithm has been developed, namely, three methods for initializing an initial population of a simple GA: the standard method (Default), the mixed method (Random), and the mixed optimal (Random optimal). In the developed standard method, each individual, when generating the initial population, consists of the same gene sequence — indices of the visited drug packages, arranged in ascending order from first to last. When using the mixed method, each individual in the generation of the initial population consists of different sequences of genes — indices of visited packages of drugs arranged in a random order. In the mixed optimal method developed, each individual, when generating the initial population, will consist of identical sequences of genes, each of which is the best way among the number of generated mixed paths specified by the user.Unlike existing methods, a modified GA version allows one to select the initial population initialization method when solving the traveling salesman problem, which, in turn, allows generating more adapted chromosomes (chromosomes with better fitness functions) at the initialization stage and thus improving the results of the algorithm. The proposed modification allows significantly increase the speed due to the fact that when using the standard initial population initialization method, the initial value of the calculated fitness function and, accordingly, the distance will be less than when using other initialization methods, which will allow to more accurately determine the optimum of the problem.Created software that allows you to change the initial parameters of the genetic algorithm, graphically observe the process of solving the traveling salesman problem get the result in text and graphic form. Tabl.: 1. Fig.: 6. Refs: 29 titles. Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації початкової популяції передбачають створення початкової множини рішень, виходячи з особливостей розв’язуваної задачі, що дозволяє генерувати більш пристосовані хромосоми (хромосоми з кращими значеннями функції пристосованості) на початковому етапі пошуку та наблизити початкові точки до області глобального екстремуму, зменшити час оптимізації і обсяг використаних ресурсів комп’ютера. Розроблену еволюційну модель для розв’язання задачі комівояжера було імплементовано шляхом її програмної реалізації і впровадження в аптечній мережі «Аптека низьких цін». У програмі реалізовано можливість побудови контуру обходу для пошуку ліків у роботизованому складі на 1000 чарунок, тривалість пошуку ліків є прийнятною для підприємства та складає не більше п’яти секунд. Інститут проблем реєстрації інформації НАН України 2019-11-21 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/183550 10.35681/1560-9189.2019.21.3.183550 Data Recording, Storage & Processing; Vol. 21 No. 3 (2019); 31-41 Регистрация, хранение и обработка данных; Том 21 № 3 (2019); 31-41 Реєстрація, зберігання і обробка даних; Том 21 № 3 (2019); 31-41 1560-9189 uk http://drsp.ipri.kiev.ua/article/view/183550/185242 Авторське право (c) 2021 Реєстрація, зберігання і обробка даних |
| institution |
Data Recording, Storage & Processing |
| baseUrl_str |
|
| datestamp_date |
2019-12-10T12:37:29Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
optimal path traveling salesman problem genetic algorithm evolutionary algorithm minimum distance graph C Qt |
| spellingShingle |
optimal path traveling salesman problem genetic algorithm evolutionary algorithm minimum distance graph C Qt Oliinyk, A. О. Fedorchenko, Iе. М. Stepanenko, О. О. Rud, M. S. An evolutionary method for solving the traveling salesman problem |
| topic_facet |
задача комівояжера генетичний алгоритм еволюційна модель мінімальна відстань граф optimal path traveling salesman problem genetic algorithm evolutionary algorithm minimum distance graph C Qt |
| format |
Article |
| author |
Oliinyk, A. О. Fedorchenko, Iе. М. Stepanenko, О. О. Rud, M. S. |
| author_facet |
Oliinyk, A. О. Fedorchenko, Iе. М. Stepanenko, О. О. Rud, M. S. |
| author_sort |
Oliinyk, A. О. |
| title |
An evolutionary method for solving the traveling salesman problem |
| title_short |
An evolutionary method for solving the traveling salesman problem |
| title_full |
An evolutionary method for solving the traveling salesman problem |
| title_fullStr |
An evolutionary method for solving the traveling salesman problem |
| title_full_unstemmed |
An evolutionary method for solving the traveling salesman problem |
| title_sort |
evolutionary method for solving the traveling salesman problem |
| title_alt |
Розв’язання задачі комівояжера на основі еволюційного моделювання |
| description |
A method is proposed for solving the traveling salesman problem on the basis of an evolutionary approach, and their approbation in the pharmacy business has been carried out by optimizing the operation of the drug delivery device. A modification of the evolutionary algorithm has been developed, namely, three methods for initializing an initial population of a simple GA: the standard method (Default), the mixed method (Random), and the mixed optimal (Random optimal). In the developed standard method, each individual, when generating the initial population, consists of the same gene sequence — indices of the visited drug packages, arranged in ascending order from first to last. When using the mixed method, each individual in the generation of the initial population consists of different sequences of genes — indices of visited packages of drugs arranged in a random order. In the mixed optimal method developed, each individual, when generating the initial population, will consist of identical sequences of genes, each of which is the best way among the number of generated mixed paths specified by the user.Unlike existing methods, a modified GA version allows one to select the initial population initialization method when solving the traveling salesman problem, which, in turn, allows generating more adapted chromosomes (chromosomes with better fitness functions) at the initialization stage and thus improving the results of the algorithm. The proposed modification allows significantly increase the speed due to the fact that when using the standard initial population initialization method, the initial value of the calculated fitness function and, accordingly, the distance will be less than when using other initialization methods, which will allow to more accurately determine the optimum of the problem.Created software that allows you to change the initial parameters of the genetic algorithm, graphically observe the process of solving the traveling salesman problem get the result in text and graphic form. Tabl.: 1. Fig.: 6. Refs: 29 titles. |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2019 |
| url |
http://drsp.ipri.kiev.ua/article/view/183550 |
| work_keys_str_mv |
AT oliinykao anevolutionarymethodforsolvingthetravelingsalesmanproblem AT fedorchenkoiem anevolutionarymethodforsolvingthetravelingsalesmanproblem AT stepanenkooo anevolutionarymethodforsolvingthetravelingsalesmanproblem AT rudms anevolutionarymethodforsolvingthetravelingsalesmanproblem AT oliinykao rozvâzannâzadačíkomívoâžeranaosnovíevolûcíjnogomodelûvannâ AT fedorchenkoiem rozvâzannâzadačíkomívoâžeranaosnovíevolûcíjnogomodelûvannâ AT stepanenkooo rozvâzannâzadačíkomívoâžeranaosnovíevolûcíjnogomodelûvannâ AT rudms rozvâzannâzadačíkomívoâžeranaosnovíevolûcíjnogomodelûvannâ AT oliinykao evolutionarymethodforsolvingthetravelingsalesmanproblem AT fedorchenkoiem evolutionarymethodforsolvingthetravelingsalesmanproblem AT stepanenkooo evolutionarymethodforsolvingthetravelingsalesmanproblem AT rudms evolutionarymethodforsolvingthetravelingsalesmanproblem |
| first_indexed |
2025-07-17T10:57:42Z |
| last_indexed |
2025-07-17T10:57:42Z |
| _version_ |
1850411387427225600 |