Разработка генетического алгоритма решения одноэтапной транспортной задачи с фиксированными доплатами

Управление сложными логистическими процессами современных предприятий требует разработки адекватных математических моделей, позволяющих рассчитать оптимальные планы перевозки. Одной из таких моделей является транспортная задача с фиксированными доплатами, особенностью которой является нелинейность функции цели. Настоящее исследование посвящено разработке генетического алгоритма решения транспортной задачи с фиксированными доплатами. Основу исследования составляет проведенный анализ существующих подходов к решению различных модификаций транспортных задач. Особенностью предлагаемого алгоритма является формирование на каждом из этапов хромосом, удовлетворяющих ограничениям задачи, что позволяет сократить время решения. В исследовании подробно представлены шаги алгоритма формирования начальной популяции, кроссинговера и мутации, адаптированные к условиям транспортной задачи с фиксированными доплатами. В основу формирования начальной популяции положен подход случайного выбора пары «поставщик-потребитель», что обеспечивает ее достаточное разнообразие. Оператор кроссинговера реализуется посредством разработки алгоритма, основанного на делении по модулю двух сумм генов родителей и последующем перераспределении остатков от деления между потомками. Алгоритм мутации хромосомы основан на изменении плана перевозок для случайно выбранных строк и столбцов при сохранении допустимости особи. Для проведения вычислительного эксперимента разработан программный продукт на языке Python, приведен демонстрационный пример расчета. Результаты проведенных расчетов для группы сельхозпроизводителей позволили сделать выводы о практической значимости предлагаемого алгоритма и выявили возможности его использования для решения многоэтапных транспортных задач, актуальных для крупных производственных и логистических компаний.

1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. Москва: Наука; 1969. 368 с.

2. Димов Ю.С., Лукьянов Н.Д. Применение генетического алгоритма для решения трипланарной транспортной задачи. Вестник Иркутского государственного технического университета. 2016;(7):73–79. https://doi.org/10.21285/1814-3520-2016-7-73-79

3. Чернышова Г.Д., Чигодаева А.С. Задачи транспортного типа с разрывными целевыми функциями. Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2016;(2):65–69.

4. Кумари А., Босе Т., Гупта Г., Бала Р. Модифицированный метод поиска решения сбалансированных транспортных задач: метод степенного ранга. Вычислительные технологии. 2024;29(2):62–68. (На англ.). https://doi.org/10.25743/ICT.2024.29.2.005

5. Волхонская Е.Е. Задача оптимального назначения автономных транспортных средств в производственно-логистической системе. Вестник Самарского государственного технического университета. Серия: Технические науки. 2023;31(2):20–30. https://doi.org/10.14498/tech.2023.2.2

6. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Москва: Физматлит; 2010. 366 с.

7. Вирсански Э. Генетические алгоритмы на Python. Москва: ДМК Пресс; 2020. 286 с.

8. Саймон Д. Алгоритмы эволюционной оптимизации. Москва: ДМК Пресс; 2020. 940 с.

9. Загинайло М.В., Фатхи В.А. Генетический алгоритм как эффективный инструмент эволюционных алгоритмов. Инновации. Наука. Образование. 2020;(22):513–518.

10. Гусев П.Ю., Гусев К.Ю., Вахмин С.Ю. Применение генетических алгоритмов в оптимизации планировочных решений производственных подразделений машиностроительных предприятий. Вестник Воронежского государственного технического университета. 2019;15(2):22–28. https://doi.org/10.25987/VSTU.2019.15.2.003

11. Шитов А.Е., Журавлев И.А. Исследование работы генетического алгоритма в процессе производственно-хозяйственной деятельности. Наукосфера. 2021;(12 1):236–240. https://doi.org/10.5281/zenodo.5788763

12. Скворцов С.В., Дьяков М.С. Ускорение генетического алгоритма решения транспортной задачи средствами многопоточного программирования. Вестник Рязанского государственного радиотехнического университета. 2023;(84):99–107. https://doi.org/10.21667/1995-4565-2023-84-99-107

13. Altiparmak F., Gen M., Lin L., Paksoy T. A genetic algorithm approach for multi-objective optimization of supply chain networks. Computers & Industrial Engineering. 2006;51(1):196–215. https://doi.org/10.1016/j.cie.2006.07.011

14. Khalili-Damghani K., Tavana M., Santos-Arteaga F.J., Ghanbarzad-Dashti M. A customized genetic algorithm for solving multi-period cross-dock truck scheduling problems. Measurement. 2017;108:101–118. https://doi.org/10.1016/j.measurement.2017.05.027