Розв'язання задачі комівояжера на основі еволюційного моделювання
Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації по...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2019 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/169109 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Розв'язання задачі комівояжера на основі еволюційного моделювання / А.О. Олійник, Є.М. Федорченко, О.О. Степаненко, М.С. Рудь // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 3. — С. 31–41. — Бібліогр.: 29 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862748831841517568 |
|---|---|
| author | Олійник, А.О. Федорченко, Є.М. Степаненко, О.О. Рудь, М.С. |
| author_facet | Олійник, А.О. Федорченко, Є.М. Степаненко, О.О. Рудь, М.С. |
| citation_txt | Розв'язання задачі комівояжера на основі еволюційного моделювання / А.О. Олійник, Є.М. Федорченко, О.О. Степаненко, М.С. Рудь // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 3. — С. 31–41. — Бібліогр.: 29 назв. — укр. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації початкової популяції передбачають створення початкової множини рішень, виходячи з особливостей розв’язуваної задачі, що дозволяє генерувати більш пристосовані хромосоми (хромосоми з кращими значеннями функції пристосованості) на початковому етапі пошуку та наблизити початкові точки до області глобального екстремуму, зменшити час оптимізації і обсяг використаних ресурсів комп’ютера. Розроблену еволюційну модель для розв’язання задачі комівояжера було імплементовано шляхом її програмної реалізації і впровадження в аптечній мережі «Аптека низьких цін». У програмі реалізовано можливість побудови контуру обходу для пошуку ліків у роботизованому складі на 1000 чарунок, тривалість пошуку ліків є прийнятною для підприємства та складає не більше п’яти секунд.
Предложена эволюционная модель для решения задачи коммивояжера, выполнена ее апробация в сфере аптечного бизнеса путем оптимизации процесса работы средства подачи лекарств. В разработанной модели использованы модифицированные операторы инициализации начальной популяции. Разработанные операторы инициализации начальной популяции предусматривают создание исходного множества решений, исходя из особенностей решаемой задачи, позволяют генерировать более приспособленные хромосомы (хромосомы с лучшими значениями функции приспособленности) на начальном этапе поиска и приблизить начальные точки в область глобального экстремума, уменьшить оптимизации и объем использованных ресурсов компьютера. Разработанная эволюционная модель для решения задачи коммивояжера была имплементирована путем ее программной реализации и внедрения в аптечной сети «Аптека низких цен». В программе реализована возможность построения контура обхода для поиска лекарств в роботизированном складе на 1000 ячеек, продолжительность поиска лекарств является приемлемой для предприятия и составляет не более пяти секунд.
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.
|
| first_indexed | 2025-12-07T20:57:27Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-169109 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Ukrainian |
| last_indexed | 2025-12-07T20:57:27Z |
| publishDate | 2019 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Олійник, А.О. Федорченко, Є.М. Степаненко, О.О. Рудь, М.С. 2020-06-04T17:57:19Z 2020-06-04T17:57:19Z 2019 Розв'язання задачі комівояжера на основі еволюційного моделювання / А.О. Олійник, Є.М. Федорченко, О.О. Степаненко, М.С. Рудь // Реєстрація, зберігання і обробка даних. — 2019. — Т. 21, № 3. — С. 31–41. — Бібліогр.: 29 назв. — укр. 1560-9189 DOI: https://doi.org/10.35681/1560-9189.2019.21.3.183550 https://nasplib.isofts.kiev.ua/handle/123456789/169109 004.93 Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації початкової популяції передбачають створення початкової множини рішень, виходячи з особливостей розв’язуваної задачі, що дозволяє генерувати більш пристосовані хромосоми (хромосоми з кращими значеннями функції пристосованості) на початковому етапі пошуку та наблизити початкові точки до області глобального екстремуму, зменшити час оптимізації і обсяг використаних ресурсів комп’ютера. Розроблену еволюційну модель для розв’язання задачі комівояжера було імплементовано шляхом її програмної реалізації і впровадження в аптечній мережі «Аптека низьких цін». У програмі реалізовано можливість побудови контуру обходу для пошуку ліків у роботизованому складі на 1000 чарунок, тривалість пошуку ліків є прийнятною для підприємства та складає не більше п’яти секунд. Предложена эволюционная модель для решения задачи коммивояжера, выполнена ее апробация в сфере аптечного бизнеса путем оптимизации процесса работы средства подачи лекарств. В разработанной модели использованы модифицированные операторы инициализации начальной популяции. Разработанные операторы инициализации начальной популяции предусматривают создание исходного множества решений, исходя из особенностей решаемой задачи, позволяют генерировать более приспособленные хромосомы (хромосомы с лучшими значениями функции приспособленности) на начальном этапе поиска и приблизить начальные точки в область глобального экстремума, уменьшить оптимизации и объем использованных ресурсов компьютера. Разработанная эволюционная модель для решения задачи коммивояжера была имплементирована путем ее программной реализации и внедрения в аптечной сети «Аптека низких цен». В программе реализована возможность построения контура обхода для поиска лекарств в роботизированном складе на 1000 ячеек, продолжительность поиска лекарств является приемлемой для предприятия и составляет не более пяти секунд. 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. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Розв'язання задачі комівояжера на основі еволюційного моделювання Решения задачи коммивояжера на основе эволюционного подхода An evolutionary method for solving the traveling salesman problem Article published earlier |
| spellingShingle | Розв'язання задачі комівояжера на основі еволюційного моделювання Олійник, А.О. Федорченко, Є.М. Степаненко, О.О. Рудь, М.С. Математичні методи обробки даних |
| title | Розв'язання задачі комівояжера на основі еволюційного моделювання |
| title_alt | Решения задачи коммивояжера на основе эволюционного подхода An evolutionary method for solving the traveling salesman problem |
| title_full | Розв'язання задачі комівояжера на основі еволюційного моделювання |
| title_fullStr | Розв'язання задачі комівояжера на основі еволюційного моделювання |
| title_full_unstemmed | Розв'язання задачі комівояжера на основі еволюційного моделювання |
| title_short | Розв'язання задачі комівояжера на основі еволюційного моделювання |
| title_sort | розв'язання задачі комівояжера на основі еволюційного моделювання |
| topic | Математичні методи обробки даних |
| topic_facet | Математичні методи обробки даних |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/169109 |
| work_keys_str_mv | AT olíinikao rozvâzannâzadačíkomívoâžeranaosnovíevolûcíinogomodelûvannâ AT fedorčenkoêm rozvâzannâzadačíkomívoâžeranaosnovíevolûcíinogomodelûvannâ AT stepanenkooo rozvâzannâzadačíkomívoâžeranaosnovíevolûcíinogomodelûvannâ AT rudʹms rozvâzannâzadačíkomívoâžeranaosnovíevolûcíinogomodelûvannâ AT olíinikao rešeniâzadačikommivoâžeranaosnoveévolûcionnogopodhoda AT fedorčenkoêm rešeniâzadačikommivoâžeranaosnoveévolûcionnogopodhoda AT stepanenkooo rešeniâzadačikommivoâžeranaosnoveévolûcionnogopodhoda AT rudʹms rešeniâzadačikommivoâžeranaosnoveévolûcionnogopodhoda AT olíinikao anevolutionarymethodforsolvingthetravelingsalesmanproblem AT fedorčenkoêm anevolutionarymethodforsolvingthetravelingsalesmanproblem AT stepanenkooo anevolutionarymethodforsolvingthetravelingsalesmanproblem AT rudʹms anevolutionarymethodforsolvingthetravelingsalesmanproblem |