УДК 004.023 DOI: 10.26200/GSTOU.2023.75.38.019

РЕШЕНИЕ ЗАДАЧИ ТРАНСПОРТНОЙ ЛОГИСТИКИ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

© О.П. Тимофеева, А.Ю. Карпычева, А.Н. Санников

Нижегородский государственный технический университет им. Р.Е. Алексеева,

г. Нижний Новгород

Аннотация. Логистика — это неотъемлемая часть любой отрасли, прямо или косвенно связанной с транспортировкой грузов. Оптимизация транспортной логистики является очень острой проблемой на производстве, в бизнесе. Из-за большой конкуренции на рынке все стремятся минимизировать свои затраты на производство, перевозку, тем самым повысить эффективность деятельности и конкурентоспособность своего продукта или услуги. Большинство из существующих математических методов, оказываются неэффективными при решении задач больших размерностей. Целью работы является выяснение применимости генетического алгоритма к решению транспортной задачи. В статье приводятся постановка задачи транспортной логистики, описание генетического алгоритма и генетических операторов, результаты тестирования на различных начальных условиях, настройка параметров генетического алгоритма.

Ключевые слова: транспортная логистика, оптимизация, генетический алгоритм, эвристический метод.

Введение

Транспортировка людей и грузов — очень важная часть жизни современного человека. Необходимость решения задач транспортной логистики, с минимизацией издержек на перевозку, определяется большим экономическим эффектом, т.к. это явно увеличивает прибыль предприятия. Применение компьютерных методов решения задач позволяет увеличить скорость принятия решений и повысить эффективность найденных решений. Данный класс задач является сложным для решения, но необходимым и широко применяемым на практике [1-4]. В классическом виде задача логистики предполагает нахождение оптимального, т. е. сопряженного с минимальными затратами, плана грузоперевозок.

Кроме детерминированных методов, еще одним подходом к решению данной задачи являются эвристические методы, моделирующие физические, биологические процессы.

Эвристический алгоритм – это не полностью математически обоснованный, но при этом полезный практически алгоритм. Правильность его для всех возможных случаев не доказана, в отличие от детерминированных методов он не гарантирует нахождение лучшего решения, но все же дает приемлемый результат и за короткое время.

В данной работе рассматривается решение задачи транспортной логистики с помощью генетического алгоритмов.

Обзор литературы

Задача оптимизации логистических перевозок рассмотрена во многих научных работах как российских, так и иностранных ученых. Так, в работе [5] изложены известные подходы к решению задач оптимальной и экономной эксплуатации транспортных средств городского электротранспорта, которые можно условно поделить на численные и аналитические. При выборе режима движения транспортных средств городского электрического транспорта с минимально возможными затратами электроэнергии необходимо решать задачу оптимизации потребления электрической энергии. Рассмотрен численный метод определения оптимальных режимов движения троллейбуса при пассажирских перевозках в городских условиях.

При организации движения материального потока по логистическому каналу возникает объективная необходимость в специально обустроенных помещениях или площадках, предназначенных для хранения запасов товаров различных наименований, а также выполнения

над ними ряда важных логистических операций, таких как сортировка, комплектация, упаковка и прочие. На основе анализа в статье [6] предлагаются направления совершенствования управления, даются рекомендации по использованию зарубежного опыта, рассматриваются новые технологии и примеры использования искусственного интеллекта в логистике складирования.

В статье [7] рассматривается подход к оптимизации перемещений автомобильного транспорта при доставке товаров с крупного склада в универсальные магазины, относящиеся к одной торговой сетевой фирме. Целью решения этой задачи оптимизации являются: сокращение времени на транспортировку товаров; проведение рационального распределения транспортных средств; уменьшение количества требующегося автотранспорта, задействованного в этих перевозках; сокращение эксплуатационных затрат на содержание автомобилей. В результате анализа предлагается использовать для оптимизации перемещений автомобильного транспорта при доставке товаров алгоритм Литтла. На втором месте идет алгоритм муравьиных колоний. Модификация жадного алгоритма эффективнее жадного алгоритма (на 37%), при этом время его работы в несколько раз больше, чем у жадного алгоритма.

В исследовании [8] рассмотрен новый подход к проблеме маршрутизации линейных судов на основе модели оптимизации маршрутов линейных судов при распределении грузов между хинтерландами портов. Указывается, что новый метод создан путем совмещения методов генетических химер и упорядоченного кроссовера. Рассматриваемый подход имеет ряд преимуществ над актуальными методами, так как в процессе оптимизации маршрутов линейной судоходной компании учитывается распределение грузов между хинтерландами портов.

Цель работы [9] состоит в том, чтобы минимизировать время разгрузки и погрузки автотранспорта и исключить время хранения товара на складе. Описывается метод планирования разгрузки/загрузки входящих и исходящих грузовиков на платформе кросс- докинг. В статье описывается разработанный метод на основе генетических алгоритмов, направленный на решение задачи кросс-докинга.

В статье [10] рассмотрены особенности современной транспортной логистики, возникающие в связи с применением информационных технологий, позволяющих получать более полную и точную информацию о логистических процессах и автоматически вырабатывать управленческие решения. Под транспортной логистикой понимается деятельность предприятий в области транспортировки и хранения грузов. На примере модели разрабатывается применение комбинированных эвристик, настраиваемых на конкретные условия применения путем подбора весовых коэффициентов при элементарных эвристиках в числовых экспериментах, достоинством которых является возможность адаптации к условиям конкретного логистического предприятия.

Таким образом актуальность решения задачи транспортной логистики подтверждается проводимыми в этой области исследованиями и несомненным экономическим эффектом для предприятий, стремящихся оптимизировать свою деятельность.

Постановка задачи

Рассмотрим математическую постановку задачи транспортной логистики [11].

Пусть имеется m поставщиков и n потребителей, показатели Cij – стоимость перевозки единицы груза от каждого i-го поставщика (i =1,2,…,m) каждому j-му потребителю (j

=1,2,…,n); ai – мощность (запасы) i-го поставщика в планируемый период; bj – спрос j-го потребителя на этот же период.

Математическая модель транспортной задачи имеет вид:

𝑚 𝑛

𝑍(𝑥) = ∑ ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑖𝑗 → 𝑚𝑖𝑛 ,

𝑖=1 𝑗=1

где Z(x) – целевая функция при ограничениях

(1)

𝑛

∑ 𝑥𝑖𝑗 = 𝑎𝑖, 𝑖 = 1,2, … , 𝑚,

𝑖=1

𝑚

∑ 𝑥𝑖𝑗 = 𝑏𝑗, 𝑗 = 1,2, … , 𝑛,

𝑗=1

(2)

{𝑥𝑖𝑗 ≥ 0, 𝑖 = 1,2, … , 𝑚, 𝑗 = 1,2, … , 𝑛.

Генетический алгоритм в решении задачи логистики

При описании генетического алгоритма используется терминология, взятая из генетики.

Представим с ее помощью нашу задачу.

Особь – это вариант решения задачи, состоящий из одной хромосомы. В транспортной задаче особь представляет собой хромосому-решение и является допустимым планом перевозок

𝑋 = {𝑥𝑖𝑗}(i = 1, 2…, m и j = 1, 2…, n), т.е. возможным решением задачи.

Популяция – это конечное число особей, т.е. набор допустимых решений задачи. В процессе работы алгоритма эти решения эволюционируют, т.е. становятся лучше. Очередная популяция называется поколением.

Одним из важных понятий является функция приспособленности. Она определяет качество особей в популяции, т.е. позволяет оценить, насколько приспособлены конкретные особи в популяции, и выбрать из них наиболее приспособленные в соответствии с эволюционным принципом выживания «сильнейших».

В задаче логистики и других задачах оптимизации функция приспособленности, как правило, подлежит оптимизации и называется целевой функцией [12].

Генетический алгоритм состоит из трех основных генетических операторов.

Скрещивание - операция, которая по родительской паре хромосом-решений находит потомка. Оператор моделирует процесс скрещивания особей, за счет которого производится обмен генетического материала. Для улучшения качества популяции, подразумевается выбор пар родителей с хорошей приспособленностью, т.е. с наименьшим значением целевой функцией. Мутация – операция, которая случайно изменяет хромосому-решение или ее часть.

Оператор мутации позволяет поддерживать разнообразие особей в популяции.

Отбор – это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции снова применяются операции скрещивания и мутации, затем опять происходит отбор, и так далее. Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом [13]:

• Приспособленность индивидуума – это значение целевой функции (функции приспособленности) на этом индивидууме.

• Выживание наиболее приспособленных. Популяция следующего поколения формируется в соответствии с целевой функцией. Наиболее приспособленные индивидуумы, которым соответствуют наименьшие значения целевой функции, получают возможность перейти в следующую популяцию.

  
  

  Рассмотрим подробнее выполнение операторов скрещивания и мутации. Особи в популяции отсортированы по возрастанию функций приспособленности. В качестве родителей выбираются соседние пары особей в популяции X1 и X2. Заполняются матрицы DIV и REM так, что для i = 1, 2…, m и j = 1, 2…, n:

  
  

  𝑑𝑖𝑣𝑖𝑗 = (𝑥1𝑖𝑗 + 𝑥2𝑖𝑗)/2

  𝑟𝑒𝑚𝑖𝑗 = (𝑥1𝑖𝑗 + 𝑥2𝑖𝑗) 𝑚𝑜𝑑 2

  Формируется матрица REM2, обладающая свойствами:

  𝑛 𝑛

  ∑ 𝑟𝑒𝑚2𝑖𝑗 = (∑ 𝑟𝑒𝑚𝑖𝑗)/2

  (𝑖 = 1,2, … , 𝑚)

  𝑗=1 𝑗=1

  
  

  𝑚 𝑚

  ∑ 𝑟𝑒𝑚2𝑖𝑗 = (∑ 𝑟𝑒𝑚𝑖𝑗)/2

  (𝑗 = 1,2, … , 𝑛)

  𝑖=1 𝑖=1

  Потомок получается по формуле 𝑋3 = 𝐷𝐼𝑉 + 𝑅𝐸𝑀2 и также является допустимым решением, т.е. удовлетворяет ограничением задачи (2).

  Операция мутации применяется к полученным потомкам с вероятностью h. Для каждого потомка берется случайное число на отрезке [0;1], и если это число меньше вероятности h, то данный потомок мутирует.

  Также есть возможность задать, какая часть хромосомы будет мутировать, для этого необходимо выбрать числа p (количество строк) и q (количество столбцов) такие, что 1

  ≤ p ≤ m и 1 ≤ q ≤ n.

  Вычисляются вектора a` и b`:

  𝑞

  𝑎`𝑖 = ∑ 𝑥3𝑖𝑗

  𝑗=1

  𝑝

  𝑏`𝑗 = ∑ 𝑥3𝑖𝑗

  𝑖=1

  
  

  (𝑖 = 1,2, … , 𝑝)

  
  

  (𝑗 = 1,2, … , 𝑞)

  
  

  Формируется матрица X` с помощью функции создания особи, в которую передаем параметры p, q, a`, b`.

  Далее элементы из X` возвращаются в X3 так, что для 𝑖 = 1,2, … , 𝑝 и 𝑗 = 1,2, … , 𝑞:

  𝑥3𝑖𝑗 = 𝑥`𝑖𝑗

  После мутации потомки тоже удовлетворяют ограничениям задачи.

  Результаты

  Для проведения исследований было разработано программное обеспечение на языке программирования C++ в среде разработки Visual Studio.

  Проанализируем результаты работы генетического алгоритма на различных наборах исходных данных и параметрах задачи. Для нахождения точного оптимального решения (эталонного) использовалась программа, реализующая метод потенциалов.

  Рассмотрим задачу размерности 10×10 (10 производителей, 10 потребителей). Проведем три эксперимента, каждый из которых состоит из четырех прогонов программы. В каждом эксперименте количество особей в популяции фиксировано (10, 20, 40 особей для соответственно), а количество итераций будет увеличиваться (50, 100, 150, 200 итераций для каждого прогона программы соответственно). Посмотрим, как изменялось среднее значение целевой функции за каждый эксперимент (рис. 1).

  

  Рис. 1. Изменение среднего значения целевой функции от размера популяции

  Анализ результатов тестирования показал, что среднее значение целевой функции за каждый эксперимент уменьшается. Следовательно, можно сделать вывод о том, что размер популяции 40 особей является наилучшим. Из графика (рис. 2) заметно, что наилучший результат получен при количестве итераций равном 200.

  
  

  

  Рис. 2. График зависимости целевой функции от количества итераций (при размере популяции 40 особей)

  Рассмотрим влияние вероятности мутации потомков и размера мутирующего участка на результат. Поскольку мы выяснили, что оптимальными параметрами являются количество особей в популяции - 40 и количество итераций - 200, то зафиксируем их для всех последующих случаев. Также будем фиксировать размер мутирующего участка, а изменять вероятность возникновения мутации.

  Посмотрим, как изменялось среднее значение целевой функции за каждый эксперимент (рис.3).

  

  Рис. 3. Изменение среднего значения целевой функции от размера мутирующего

  участка

  Анализ получившегося графика показывает, что наилучшие результаты получились при размере мутирующего участка 10×10, т.е. для задачи размерности 10×10 оптимальным вариантов будет мутация всей особи. Также эксперименты показали, что лучше использовать вероятность возникновения мутации равную 0,5 (рис. 4).

  
  

  

  Рис. 4. График зависимости целевой функции от вероятности мутации (при размере мутирующего участка 10×10)

  Таким образом, в ходе работы был изучен и адаптирован к транспортной задаче генетический алгоритм. Для задачи размерности 10×10 экспериментальным путем были получены оптимальные параметры генетического алгоритма:

  • размер популяции 40 особей;

  • количество итераций 200;

  • вероятность возникновения мутации 0.5;

  • размер мутирующего участка 10×10.

15%.

Минимальное отклонение от оптимального результата при таких параметрах составило

При решении тестовых задач время получения результата увеличивалось

пропорционально размерности задачи. Сравнение скорости работы генетического алгоритма со скоростью работы детерминированного метода потенциалов показало значительное преимущество первого.

В дальнейшем к рассмотренной задаче планируется применить механизм нечеткой логики для моделирования работы логистической сети с нечеткими потребностями.

Заключение

В отличие от точных методов математического программирования, эволюционные методы позволяют находить решения близкие к оптимальным за приемлемое время. Решения могут по определенному правилу порождать новые решения, которые будут наследовать лучшие черты своих «предков». В качестве случайного элемента в методах эволюционных вычислений используется процесс мутации особи. С его помощью решение может быть случайно изменено, что приведет к новому направлению в процессе эволюции и может ускорить процесс получения лучшего решения. Таким образом в ходе эксперимента было установлено, что генетический алгоритм целесообразно применять для решения задачи транспортной логистики, т.к. он дает достаточно хороший результат и выигрывает по времени работы относительно детерминированного алгоритма.

СПИСОК ЛИТЕРАТУРЫ

1. Емельянова Т.С. Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов: дис. канд. тех. наук – 2009. С. 3-4.

2. Timofeeva, O.; Sannikov, A.; Stepanenko, M.; Balashova, T. Modification of the Bellman–Ford Algorithm for Finding the Optimal Route in Multilayer Network Structures. Computation 2023, 11, 74.

3. Berlinski, M.; Warchulski, E.; Kozdrowski, S. Applications of Metaheuristics Inspired by Nature in a Specific Optimisation Problem of a Postal Distribution Sector. Appl. Sci. 2022, 12, 9384. Chen, G.; Chen, J. Reverse Logistics Network Model of Dual-Channel Recycling Boxes Based on Genetic Algorithm Optimization: A Multi-Objective and Uncertain Environment Perspective. Sustainability 2023, 15, 4408.

4. Chen, G.; Chen, J. Reverse Logistics Network Model of Dual-Channel Recycling Boxes Based on Genetic Algorithm Optimization: A Multi-Objective and Uncertain Environment Perspective. Sustainability 2023, 15, 4408.

5. Оптимизация режимов движения транспортных средств городского электрического транспорта / Д. А. Лычев, А. С. Поварехо // Вестник Белорусско-Российского университета. 2020. № 1. с. 58 – 63.

6. Оптимизация процессов в логистике складирования / М.В. Писарев, Г.И. Шепелин // E- Scio. 2022.

7. Оптимизация параметров транспортного процесса на основе эвристических алгоритмов задачи коммивояжёра / И.П. Романова, П.С. Романов // Интеллект. Инновации. Инвестиции. 2018. № 1. с. 67-71.

8. Модель оптимизации линейных маршрутов на основе генетического алгоритма / А.В. Галин, А.С. Малыхин // Вестник государственного университета морского и речного флота им. Адмирала С.О. Макарова. 2021. том 13. № 4. с. 530-538.

9. Генетический алгоритм решения логистической задачи / В.М. Курейчик, А.А. Рокотянский // Известия ЮФУ. Технические науки. 2012. № 11. с. 245-251.

10. Эвристический метод управления транспортной логистикой / О.А. Найдис, В.А. Павлов, С.О. Пирогов // Азимут научных исследований: экономика и управление. 2016. том 5. - № 2. с. 195-198.

11. Математическое программирование в задачах управления: учебное пособие / О.П. Тимофеева [и др.]; НГТУ им. Р.Е. Алексеева. Нижний Новгород, 2013. 142 С.

12. Кононюк А. Е Дискретно-непрерывная математика. (Алгоритмы). В 12-и кн. Кн. 10, Ч.3— К.: 2017. 444 с.

13. Эвристические методы оптимизации: учебное пособие / А.А. Мицель. Томск: Томский государственный университет систем управления и радиоэлектроники, 2022. 73 С.

SOLUTION OF A TRANSPORT LOGISTICS TASK WITH GENETIC ALGORITHM

© O.P. Timofeeva, A.Y. Karpycheva, A.N. Sannikov

Nizhny Novgorod State Technical University named after R. E. Alekseev Nizhny Novgorod, Russia

Abstract. The purpose of this article is to solution the transport problem using a genetic algorithm and analyze the results received. The adaptation of the genetic algorithm to the transport problem and are made the adjustment of the parameters of the genetic algorithm. Finally, the analysis of the received results was conducted and the optimal parameters of the genetic algorithm were found. The results received in the course of the work can be used for further research in this field. The novelty of the work lies in the use of a genetic algorithm to solution a transport problem.

Keywords: transport logistics, optimization, genetic algorithm, heuristic method.