An evolutionary method for solving the traveling salesman problem

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...

Full description

Saved in:
Bibliographic Details
Date:2019
Main Authors: Oliinyk, A. О., Fedorchenko, Iе. М., Stepanenko, О. О., Rud, M. S.
Format: Article
Language:Ukrainian
Published: Інститут проблем реєстрації інформації НАН України 2019
Subjects:
optimal path
traveling salesman problem
genetic algorithm
evolutionary algorithm
minimum distance
graph
C
Qt
Online Access:http://drsp.ipri.kiev.ua/article/view/183550
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Data Recording, Storage & Processing

Institution

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

Similar Items