A genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo delivery
dc.contributor.author | Romanuke, V.V. | |
dc.contributor.author | Romanov, A.Y. | |
dc.contributor.author | Malaksiano, M.O. | |
dc.date.accessioned | 2023-08-10T22:51:23Z | |
dc.date.available | 2023-08-10T22:51:23Z | |
dc.date.issued | 2023 | |
dc.description.abstract | Abstract. 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.pagerange | Pp. 104-126 | uk |
dc.identifier.citation | Romanuke, 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.doi | https://doi.org/10.20535/SRIT.2308-8893.2023.2.08 | |
dc.identifier.issn | 1681–6048 | |
dc.identifier.orcid | 0000-0001-9638-9572 | uk |
dc.identifier.orcid | 0000-0002-1714-3310 | uk |
dc.identifier.orcid | 0000-0002-4075-5112 | uk |
dc.identifier.uri | https://ela.kpi.ua/handle/123456789/59150 | |
dc.language.iso | en | uk |
dc.publisher | КПІ ім. Ігоря Сікорського | uk |
dc.publisher.place | Київ | uk |
dc.relation.ispartof | Системні дослідження та інформаційні технології: міжнародний науково-технічний журнал, № 2 | uk |
dc.subject | maritime cargo delivery | uk |
dc.subject | tour length | uk |
dc.subject | genetic algorithm | uk |
dc.subject | tour constraint violation penalty | uk |
dc.subject | penalty discount | uk |
dc.subject | морська доставка вантажів | uk |
dc.subject | довжина рейсу | uk |
dc.subject | генетичний алгоритм | uk |
dc.subject | штраф за порушення обмежень рейсу | uk |
dc.subject | дисконт штрафу | uk |
dc.subject.udc | 519.854.2+519.714.71 | uk |
dc.title | A genetic algorithm improvement by tour constraint violation penalty discount for maritime cargo delivery | uk |
dc.title.alternative | Покращення генетичного алгоритму на основі дисконту штрафу за порушення обмежень рейсу для морської доставки вантажів | uk |
dc.type | Article | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- 285452-658320-1-10-20230802.pdf
- Розмір:
- 334.06 KB
- Формат:
- Adobe Portable Document Format
- Опис: