Development of a genetic method for solution of routing problems with several transport

A modified genetic method has been developed to solve routing problems with weighted constraints and multiple transportation means. The fundamental difference of this developed genetic method from existing modifications lies in the use of a diploid set of chromosomes in the population of evolving in...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2023
Hauptverfasser:	Федорченко, Є. М., Олійник, А. О., Степаненко, О. О., Зайко, Т. А., Шило, С. І., Нестеров, Г. Д.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем реєстрації інформації НАН України 2023
Schlagworte:	metaheuristic algorithms genetic algorithm optimization tabu search algorithm vehicle routing problem
Online Zugang:	http://drsp.ipri.kiev.ua/article/view/300589
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Data Recording, Storage & Processing

Institution

Data Recording, Storage & Processing

id	drspiprikievua-article-300589
record_format	ojs
spelling	drspiprikievua-article-3005892024-08-24T18:20:40Z Development of a genetic method for solution of routing problems with several transport Розробка генетичного методу для вирішення задач маршрутизації з декількома транспортами та ваговими рамками Федорченко, Є. М. Олійник, А. О. Степаненко, О. О. Зайко, Т. А. Шило, С. І. Нестеров, Г. Д. metaheuristic algorithms, genetic algorithm, optimization, tabu search algorithm, vehicle routing problem метаевристичні алгоритми, генетичний алгоритм, оптимізація, жадібний алгоритм, транспортна задача A modified genetic method has been developed to solve routing problems with weighted constraints and multiple transportation means. The fundamental difference of this developed genetic method from existing modifications lies in the use of a diploid set of chromosomes in the population of evolving indivi-duals. This modification makes the dependence of an individual's phenotype on its genotype less deterministic and, as a result, promotes the preservation of population genetic diversity and phenotypic variability throughout the execution of the method. The result of such modification is the maintenance of a sufficiently high variability of traits (genes) in the population (gene pool of the population) during evolution, which, at the same time, may have a minor impact on the individual's phenotype. A modification of the genetic mutation operator has been proposed. Unlike the classical method, individuals subjected to the mutation operator are selected not randomly, but according to their mutation resistance, corresponding to the value of the individual's fitness function. Thus, «weaker» individuals mutate, while the genome of «strong» individuals remains unchanged. In this case, the likelihood of losing the achieved extremum of the function during the action of the mutation operator decreases, and the transition to a new extremum occurs in case of accumulation of sufficient specific weight of «better» traits in the population. This modification of the operator allows for the search of values approximating the optimal ones, excluding the loss of acquired advantages during the search for better solutions. Tabl.: 1. Fig.: 3. Refs: 36 titles. Розроблено модифікований генетичний метод для розв’язання задач маршрутизації з ваговими обмеженнями та кількома транспортними засобами. Основна відмінність цього методу полягає у використанні диплоїдного набору хромосом у популяції, яка еволюціонує. Ця модифікація робить залежність фенотипу від генотипу менш детермінованою і сприяє збереженню різноманітності генофонду та варіабельнос-ті ознак фенотипу. Результатом є підтримання високої варіабельнос-ті ознак у популяції під час еволюції, при цьому маючи невеликий вплив на фенотип особин. Також було запропоновано модифікацію генетичного оператора мутацій. Особини, які піддаються мутації, обираю-ться відповідно до їхньої мутаційної стійкості, тобто «слабкіші» особини мутують, а «сильніші» залишаються без змін. Це зменшує вірогід-ність втрати досягнутого екстремуму функції під час мутації і сприяє переходу до нового екстремуму при накопиченні «кращих» ознак у популяції. Така модифікація оператора дозволяє здійснювати пошук значень, наближених до оптимальних, без втрати досягнутих під час пошуку найкращих рішень. Інститут проблем реєстрації інформації НАН України 2023-12-19 Article Article application/pdf http://drsp.ipri.kiev.ua/article/view/300589 10.35681/1560-9189.2023.25.2.300589 Data Recording, Storage & Processing; Vol. 25 No. 2 (2023); 77-88 Регистрация, хранение и обработка данных; Том 25 № 2 (2023); 77-88 Реєстрація, зберігання і обробка даних; Том 25 № 2 (2023); 77-88 1560-9189 uk http://drsp.ipri.kiev.ua/article/view/300589/301798 Авторське право (c) 2023 Реєстрація, зберігання і обробка даних
institution	Data Recording, Storage & Processing
baseUrl_str
datestamp_date	2024-08-24T18:20:40Z
collection	OJS
language	Ukrainian
topic	metaheuristic algorithms genetic algorithm optimization tabu search algorithm vehicle routing problem
spellingShingle	metaheuristic algorithms genetic algorithm optimization tabu search algorithm vehicle routing problem Федорченко, Є. М. Олійник, А. О. Степаненко, О. О. Зайко, Т. А. Шило, С. І. Нестеров, Г. Д. Development of a genetic method for solution of routing problems with several transport
topic_facet	metaheuristic algorithms genetic algorithm optimization tabu search algorithm vehicle routing problem метаевристичні алгоритми генетичний алгоритм оптимізація жадібний алгоритм транспортна задача
format	Article
author	Федорченко, Є. М. Олійник, А. О. Степаненко, О. О. Зайко, Т. А. Шило, С. І. Нестеров, Г. Д.
author_facet	Федорченко, Є. М. Олійник, А. О. Степаненко, О. О. Зайко, Т. А. Шило, С. І. Нестеров, Г. Д.
author_sort	Федорченко, Є. М.
title	Development of a genetic method for solution of routing problems with several transport
title_short	Development of a genetic method for solution of routing problems with several transport
title_full	Development of a genetic method for solution of routing problems with several transport
title_fullStr	Development of a genetic method for solution of routing problems with several transport
title_full_unstemmed	Development of a genetic method for solution of routing problems with several transport
title_sort	development of a genetic method for solution of routing problems with several transport
title_alt	Розробка генетичного методу для вирішення задач маршрутизації з декількома транспортами та ваговими рамками
description	A modified genetic method has been developed to solve routing problems with weighted constraints and multiple transportation means. The fundamental difference of this developed genetic method from existing modifications lies in the use of a diploid set of chromosomes in the population of evolving indivi-duals. This modification makes the dependence of an individual's phenotype on its genotype less deterministic and, as a result, promotes the preservation of population genetic diversity and phenotypic variability throughout the execution of the method. The result of such modification is the maintenance of a sufficiently high variability of traits (genes) in the population (gene pool of the population) during evolution, which, at the same time, may have a minor impact on the individual's phenotype. A modification of the genetic mutation operator has been proposed. Unlike the classical method, individuals subjected to the mutation operator are selected not randomly, but according to their mutation resistance, corresponding to the value of the individual's fitness function. Thus, «weaker» individuals mutate, while the genome of «strong» individuals remains unchanged. In this case, the likelihood of losing the achieved extremum of the function during the action of the mutation operator decreases, and the transition to a new extremum occurs in case of accumulation of sufficient specific weight of «better» traits in the population. This modification of the operator allows for the search of values approximating the optimal ones, excluding the loss of acquired advantages during the search for better solutions. Tabl.: 1. Fig.: 3. Refs: 36 titles.
publisher	Інститут проблем реєстрації інформації НАН України
publishDate	2023
url	http://drsp.ipri.kiev.ua/article/view/300589
work_keys_str_mv	AT fedorčenkoêm developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT olíjnikao developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT stepanenkooo developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT zajkota developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT šilosí developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT nesterovgd developmentofageneticmethodforsolutionofroutingproblemswithseveraltransport AT fedorčenkoêm rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami AT olíjnikao rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami AT stepanenkooo rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami AT zajkota rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami AT šilosí rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami AT nesterovgd rozrobkagenetičnogometodudlâviríšennâzadačmaršrutizacíízdekílʹkomatransportamitavagovimiramkami
first_indexed	2025-07-17T10:58:53Z
last_indexed	2025-07-17T10:58:53Z
_version_	1850411634539888640

Development of a genetic method for solution of routing problems with several transport

Institution

Ähnliche Einträge