Распределение задач между погрузчиками на складе пищевого производства

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

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

В данной статье рассматривается применение методов линейного программирования (ЛП) для нахождения оптимального расписания задач погрузчиков на складе.

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

• 1)    формализация задачи оптимизации с использованием ЛП;

• 2)    адаптация модели к реальным условиям работы склада;

• 3)    получение результатов вычислительных экспериментов, демонстрирующих эффективность предложенного подхода в сравнении с традиционными методами планирования.

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

В ходе работы использовалась топология и описание действующего склада производственной компании в городе Самара. Склад поделен на ячейки хранения - прямоугольный участок склада, на полу которого расположены паллеты. Паллеты могут стоять в несколько ярусов друг на друге. В ячейках хранится только одно наименование складского учета (SKU), ячейки заполняются товаром только из одной партии. Если после прихода из производства партии ее объема не хватило для заполнения ячейки хранения, то в данную ячейку не будут ставить паллеты с другой партией товара, и ячейка останется полупустой. При формировании заказа клиентами действует принцип «первым пришёл - первым ушёл» (FIFO), и, соответственно, будут выбирать паллеты из той ячейки, в которой лежит партия, пришедшая из производства раньше всего. Также следует отметить, что если в ходе отгрузки заказа из ячейки забрали не всю партию товара, то в такую ячейку не будут выгружать иную партию. Таким образом, следует важный вывод - на складе не будет ситуаций, когда погрузчику необходимо достать паллет из глубины ячейки хранения, предварительно переместив все паллеты, которые закрывают доступ к искомому.

Все погрузчики передвигаются по специальным проходам. Ширина проходов составляет 3,5 метра, проходы разделены на две полосы движения, следовательно, погрузчики могут двигаться без остановки, если одна из полос занята другим погрузчиком. Скорость погрузчика ограничена 12 м/с.

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

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

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

Для вычисления расстояния между локациями склада предпочтительней использовать Манхэттенское расстояние [2, с. 4]:

dij = ∑ )=1Ы ^- *jk\ ․ (1)

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

Схема склада в виде графа, каждая вершина которого – это локация на складе (ячейка, доки отгрузки и т. д.) Однако такое представление неудобно для моделирования задачи оптимизации, поэтому было принято решение ввести в качестве вершины графа не отдельную локацию, а задачу, состоящую из исходной и целевой ячейки. Локации в рамках одной задачи будут объединены в одну вершину.

Таким образом, будет создан полный граф, где все вершины-задачи соединены между собой. При этом расстояние от задачи к задаче – это расстояние от целевой ячейки i -й задачи до исходной ячейки j -й задачи. В отличие от графа с локациями склада, граф с задачами будет ориентированный, так как расстояние от i -й задачи к -й задачи и наоборот будут не равны между собой.

Полученный граф G – это ориентированный полный граф, содержащий | C |+2 вершины, где множество C содержит задачи 1,2… n – задачи погрузчиков по перемещению продукции, и 2 дополнительные вершины 0 и n +1 – задачи по выезду из депо и возвращению в депо. Множество дуг обозначается как A . Ни одна дуга не заканчивается в вершине 0, и ни одна дуга не выходит из вершины n +1. Для каждой дуги ( i , j ), где i ≠ j , мы можем присвоить расстояние ^cij , которое рассчитывается как расстояние от конечной точки i -й задачи до начальной (исходной) точки -й задачи. Также каждой дуге мы присваиваем время t^ , включающее время переезда от исходной до конечной точки i -й задачи, а также поднятие поддонов на вилы на исходной точке и их снятие на конечной точке -й задачи.

Так как на складе внедрена сдельная оплата труда и доход водителей погрузчиков напрямую зависит от выполненных ими операций, необходимо обеспечить равномерное распределение задач между ними. Для этого необходимо решить задачу MWPN (Multy-Way Number Partition).

Данная задача состоит в том, чтобы при заданном наборе целых чисел разделить его на k подмножеств таким образом, чтобы суммы чисел в каждом подмножестве была как можно более похожи друг на друга [7, с. 71]. Список задач делится на k подмножеств, k равно числу погрузчиков. Список состоит из единиц, каждая единица представляет собой задачу. Сумма одного подмножества – это количество задач одного погрузчика. Математическую постановку можно описать следующим образом [8, с. 4]. Дано: S – список задач, K – множество всех погрузчиков. Параметры задачи: ^si ∈ s – список задач и k ∈ K – множество всех погрузчиков.

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

upper bound → min,(2)

где upper bound – это «идеальная» сумма подмножества или число задач для каждого из погрузчиков.

При задействованных ограничениях:

∑i∈Ssi ∗  , ≤ upper bound ∀к∈К(3)

∑к∈ К vi,к =, 1 ∀ i∈S(4)

Vik ∈ {0,1} ∀i∈S,∀к∈V(5)

Ограничение (3) указывает на то, что количество задач для любого погрузчика не должно превышать upper bond. Согласно ограничению (4), любая задача может быть распределена только одному погрузчику. Ограничение (5) – естественное ограничение, которое предполагает, что переменная ^ik может принимать значение либо 0, либо 1.

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

Основную задачу оптимизации можно описать следующим образом: V – множество всех погрузчиков, N– множество всех задач: 0,1,2…n+1, M– множество всех задач первого приоритета, они обязательны к выполнению, L – множество задач второго приоритета, В – множество задач третьего приоритета. M⊆c,L⊆CиВ⊆C.M∪L∪В=  . Множества M, L и B – попарно непересекающиеся множества.

Каждая задача имеет время начала ее выполнения, обозначаемое как a^ . Предполагается, что ^ai , ^cij являются целыми неотрицательными числами, в то время как ^ij считаются целыми положительными числами.

Модель содержит два набора переменных x и s для принятия решений. Для каждого ребра ( i , j ), где i ≠ j , i ≠ n +1, j ≠0, и для каждого k -го погрузчика мы определяем ^ijk как:

• 0, если k -й погрузчик не совершает порожнее перемещение от i -й задачи к j -й,

• 1, если k -й погрузчик совершает порожнее перемещение от i -й задачи к j -й,

Решающая переменная ^ik определяется для каждой вершины i и каждого транспортного средства к и обозначает время, когда транспортное средство к начинает обслуживать клиента i . В случае, если данное транспортное средство k не обслуживает клиента i , значение ^ik ничего не значит. Предполагается, что CLq = 0 и, следовательно, ^0k = 0 для всех k . Поэтому многокритериальная задача оптимизации будет иметь следующий вид:

• ∑к∈V∑i∈М ^ik →min(6)

∑к∈V∑i∈L∑j∈N %ijk →max(7)

∑к∈V∑i∈L ^ik →min(8)

∑к∈V∑i∈В∑J∈ N ^i jk →max(9)

∑к∈V∑i∈В ^ik →min(10)

∑к∈V∑i∈N∑j∈ N C[ j ^i jk →min(11)

Ограничение к данным целевым функциям приведено в табл. 1. С помощью целевой функции в формуле (6) возможно минимизировать время старта всех работ первого приоритета, с помощью функции в формуле (7) – максимизировать количество выполненных задач второго приоритета, с помощью целевой функции в формуле (8) – минимизировать время старта выполнения погрузчиками задач второго приоритета. Четвертая и пятая целевые функции ((9) и (10) формулы) аналогичны функциям для задач второго приоритета. Последняя, шестая целевая функция в формуле (11) необходима для минимизации порожнего перемещения между задачами.

Ограничения задачи оптимизации

Таблица 1

Номер	Ограничение
1	Z Z   , j , к =1 ∀ i ∈ M , i ≠ j к ∈ V j ∈ N /{0}
2	E E   , j , к ≤1 ∀ i ∈ L ∪ в , i ≠ j к ∈ V j ∈ N /{0}
3	at ∗ EXi , j , к ≤ Sik ∀ i ∈ N , ∀ к ∈ V , i ≠ j                  \ ~n 7 ∈ { о}
4	Sik + tij - K( 1- xijk ) ≤ Sjk ∀ i , j ∈ c , ∀ к ∈ V , i ≠ j
6	X° ^=1 ∀ к ∈ V                    \ j ∈ N /{ n+1 }
7	xihk - Zj xhjk =0 ∀ ℎ ∈ c , ∀ к ∈ V , i ≠ j i ∈ N          j ∈ N                                                             \
8	E Xi , n+l , к =1 ∀ к ∈ V                       \ i ∈ N /{0}
9	, , ≥ upper bound ∀ k ∈ V, i ≠ j i ∈ N /{n+l} j ∈ N /{0}
10	xijk ∈ {0,1} ∀ i , j ∈ N , ∀ к ∈ V , i ≠ j                      \

Ограничение (1) служит гарантом, что все задачи первого приоритета будут выполнены. В ограничении номер (2) допускается, что не все задачи второго и третьего приоритета буду выполнены. Данное ограничение отличается от классической постановки TSP [3, c. 327] и постановки VRPTW [4, с. 13]. (3) ограничение необходимо для того, чтобы погрузчики не приступали к задаче раньше ее возникновения или же раньше, чем к ней необходимо приступить. Аналогичное по смыслу ограничение для задач третьего и второго приоритетов – ограничение номер (4). Если задача из множества задач первого и второго приоритетов не выполняется (сумма порожних перемещений из i -й вершины в -ю по всем погрузчикам равна 0), то в таком случае Ct[ будет равно 0, и условие (4) всегда будет выполняться [9, c. 22]. Ограничение (5) говорит о том, что старт начала выполнения j -й задачи не должен наступать до времени окончания выполнения -й задачи. K – константа. В качестве ее значения было выбрано самое позднее время возникновения задачи, умноженное на 2. Если перемещение от задачи i к задаче j не состоится, то левая часть неравенства будет являться отрицательным числом, и условие обязательно будет выполняться. Ограничение (6) необходимо, чтобы каждый погрузчик покинул депо. С помощью ограничения (7) мы можем убедиться, что погрузчик не остановился в вершине h , а продолжил свой путь к другим задачам, и при этом не вернулся к предыдущей задаче. Иными словами – ограничение на консервацию потока. Ограничение (8) обозначает, что все погрузчики должны вернуться в депо. Ограничение (9) необходимо, чтобы погрузчики получали приблизительно равную нагрузку. Последнее ограничение (10) – естественное ограничение: ^ijk – бинарный индикатор может принимать значение только 1 или 0.

Целевые функции задачи и ограничения в своей основе имеют классическую постановку задачи коммивояжёра (TSP) и постановку задачи по маршрутизации с временными окнами. После нахождения оптимального значения целевой функции на текущем шаге оптимизации в модель будут добавляться следующие ограничения:

^∑ к ∈ V ^∑ i ∈ M ^si , к ≤ ^SI ^P                                                 (12)

opt где $1   – оптимальная сумма времени начала задач первого приоритета, ре зультат выполнения первого шага оптимизации. Сумма времени задач первого приоритета будет ограничена сверху в следующем решении.

∑к∈V∑i∈L∑j∈N ^ijk ≥ xn(13)

opt где ^XII – оптимальное количество задач второго приоритета, результат выполнения второго шага оптимизации.

∑к∈V∑i∈Lsi,к≤ sn(14)

opt где ^SII – оптимальная сумма времени начала задач второго приоритета, результат выполнения третьего шага оптимизации.

∑к∈V∑i∈В∑j∈ N xt jk ≥ XIU(15)

opt где Х_ш – оптимальное количество задач третьего приоритета, результат выполнения четвертого шага оптимизации.

^∑ к ∈ V ^∑ i ∈ в ^si , к ≤ ^SIH                                                 (16)

opt где S_UI – оптимальная сумма времени начала задач третьего приоритета, результат выполнения пятого шага оптимизации. Таким образом, на каждом шаге в модель в качестве ограничений добавляются найденные оптимальные значения на каждом из шагов.

Математическая постановка была реализована с помощью библиотеки Pyomo [1, с. 19] языка Python и решателем cbc, находящимся в открытом доступе. В ходе расчета на реальных данных, представляющих собой часть задач, выполненных за смену, были получены следующие результаты (табл. 2.). Время расчета для оптимизации каждой из целевых функций было ограничено 120 минутами.

Таблица 2

Результат вычислений

Показатель	20 задач		30 задач		40 задач
	8 ТС	10 ТС	8 ТС	10 ТС	8 ТС	10 ТС
Количество оптимальных решений	4	5	3	3	1	1
Количество допустимых решений	2	1	2	2	1	2
Среднее отклонение значения целевой функции допустимого решения от оценки оптимального решения	15%	12%	30%	22%	33%	30%
Шаги оптимизации, для которых не было найдено целочисленное решение	0	0	1	0	4	3

Таким образом, для небольшой части задач от общего количества задач смены (в смене в среднем 600–700 задач) не удается найти оптимальное решение для всех критериев оптимизации за приемлемое время. Например, для 20 задач при 8 или 10 погрузчиках (штатная численность парка 10 погрузчиков) оптимальное решение находится только для 4 и 5 критериев оптимизации соответственно. При увеличении числа задач, даже незначительном, сокращается число критериев, для которых было найдено оптимальное решение и увеличилось расхождение между оценкой оптимального решения и допустимого решения. Более того, начиная с объемом выборки в 30 задач для некоторых шагов оптимизации решатель не смог найти целочисленное решение в течение 120 минут.

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

Также хотелось бы обратить внимание на ограниченные возможности находящихся в открытом доступе решателей, к которым относится использовавшийся при расчетах cbc (coin-or branch and cut). Данные решатели уступают в скорости коммерческим продуктам, таким как CPLEX [5, с. 2] и Gurobi [10, с. 6].

Можно сделать вывод о том, что математическая постановка, учитывающая все требования бизнес-процесса, не может быть решена за время, позволяющее оперативно выставлять расписания водителям погрузчиков. Более того, в случае непредвиденных обстоятельств нет возможности в кратчайшие сроки произвести перерасчет и найти новое распределение задач. Следовательно, для составления расписания задач водителям погрузчиков необходимо применить эвристические и метаэвристические алгоритмы, которые в большинстве случае помогут найти допустимое решение за требуемое время, Один из таких алгоритмом – генетический алгоритм, решающий задачу многокритериальной оптимизации [6, c. 8].