A genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo delivery

Скорочена інформація про документ
dc.contributor.authorRomanuke, V.V.
dc.contributor.authorRomanov, A.Y.
dc.contributor.authorMalaksiano, M.O.
dc.date.accessioned2023-08-10T22:51:23Z
dc.date.available2023-08-10T22:51:23Z
dc.date.issued2023
dc.description.abstractAbstract. The problem of minimizing the cost of maritime cargo delivery is considered. The cost is equivalent to the sum of the tour lengths of feeders used for the delivery. The problem is formulated as a multiple traveling salesman problem. In order to find its solution as the shortest route of the tours of feeders, a genetic algorithm is used where we present two inequalities constraining the tour length of every feeder to lie between the shortest and longest lengths. Apart from the constant tour constraint violation penalty in the genetic algorithm, we suggest a changeable penalty as an exponential function of the algorithm iteration, where we maintain the possibility of the penalty rate to be either increasing or decreasing, whose steepness is controlled by a positive parameter. Our tests show that the changeable penalty algorithm may return shorter routes, although the constant penalty algorithms cannot be neglected. As the longest possible tour of the feeder is shortened, the changeable penalty becomes more useful owing to a penalty discount required either at the beginning or at the end of the algorithm run to improve the selectivity of the best feeder tours. In optimizing maritime cargo delivery, we propose to run the genetic algorithm by the low and constant penalties along with the increasing and decreasing penalties. The solution is the minimal value of the four route lengths. In addition, we recommend that four algorithm versions be initialized by four different pseudorandom number generator states. The expected gain is a few percent, by which the route length is shortened, but it substantially reduces expenses for maritime cargo delivery.uk
dc.description.abstractotherАнотація. Розглянуто задачу мінімізації вартості морської доставки вантажів. Ця вартість еквівалентна сумі довжин рейсів фідерів, що використовуються для доставки. Задача формулюється у формі задачі декількох комівояжерів. Для знаходження розв’язку у формі найкоротшого маршруту, що складається з рейсів фідерів, використовується генетичний алгоритм, у якому дві нерівності, котрі обмежують довжину рейсу кожного фідера до інтервалу між найкоротшою та найбільшою довжинами. Окрім сталого штрафу за порушення обмежень рейсу у генетичному алгоритмі запропоновано змінюваний штраф у формі експоненціальної функції ітерації алгоритму, де залишається можливість як зростаючого, так і спадного штрафу, чия крутизна контролюється деяким додатним параметром. Тести показують, що алгоритм зі змінюваним штрафом може повертати коротші маршрути, хоча алгоритми зі сталими штрафами не можуть бути відкинуті. Зі скороченням найдовшого рейсу фідера змінюваний штраф стає більш корисним завдяки тому, що деякий дисконт штрафу потрібний на початку або наприкінці прогону алгоритму задля покращення селективності найкращих рейсів фідерів. Для оптимізації морської доставки вантажів запропоновано запускати даний генетичний алгоритм за низького та високого штрафів разом зі зростаючим та спадаючим штрафами, після чого розв’язком є мінімальне значення з чотирьох відповідних довжин маршрутів. Рекомендовано ініціалізувати ці чотири версії алгоритму чотирма різними станами генератора псевдовипадкових чисел. Очікуваний виграш складає декілька відсотків скорочення довжини маршруту, але для морської доставки вантажів це є значним скороченням витрат.uk
dc.format.pagerangePp. 104-126uk
dc.identifier.citationRomanuke, V.V. A genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo delivery / V.V. Romanuke, A.Y. Romanov, M.O. Malaksiano // Системні дослідження та інформаційні технології : міжнародний науково-технічний журнал. – 2023. – № 2. – С. 104-126. – Бібліогр.: 17 назв.uk
dc.identifier.doihttps://doi.org/10.20535/SRIT.2308-8893.2023.2.08
dc.identifier.issn1681–6048
dc.identifier.orcid0000-0001-9638-9572uk
dc.identifier.orcid0000-0002-1714-3310uk
dc.identifier.orcid0000-0002-4075-5112uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/59150
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofСистемні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 2uk
dc.subjectmaritime cargo deliveryuk
dc.subjecttour lengthuk
dc.subjectgenetic algorithmuk
dc.subjecttour constraint violation penaltyuk
dc.subjectpenalty discountuk
dc.subjectморська доставка вантажівuk
dc.subjectдовжина рейсуuk
dc.subjectгенетичний алгоритмuk
dc.subjectштраф за порушення обмежень рейсуuk
dc.subjectдисконт штрафуuk
dc.subject.udc519.854.2+519.714.71uk
dc.titleA genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo deliveryuk
dc.title.alternativeПокращення генетичного алгоритму на основі дисконту штрафу за порушення обмежень рейсу для морської доставки вантажівuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
285452-658320-1-10-20230802.pdf
Розмір:
334.06 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити

Зібрання

Системні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 2