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

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

ГРНТИ 28.17.19

Статья поступила в редакцию 30.07.2021.

• •    распределение заказов по пик-листам, содержащим информацию о товарах и их количестве, которое необходимо собрать комплектовщикам при подборе строк заказов в коробки;

• •    формирование пик-рейсов (объединение пик-листов в один пик-рейс, соответствующий тележке, с которой перемещается комплектовщик);

• •    формирование маршрутов движения сборщиков по этажу мезонина;

• •    распределение сборщиков по зонам (этажам) склада и пик-рейсов по сборщикам.

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

Ежедневно на склад поступает множество заказов, товары в которых могут храниться на разных этажах мезонина. Пусть множество F (fE F) - множество этажей склада, тогда для каждого этажа известны собираемые на нем заказы (Ог у ) от магазинов. Каждый заказ оЕ От у представлен строками заказа sE о, которые содержат информацию объеме (ш₅) и количестве товара (^_s), необходимого магазину. При этом, объем товара, указанный в строке, не должен превышать максимальной вместимости коробки (batchCap). Для каждой строки заказа известна ячейка на мезонине, в которой располагается товар из строки. Один товар располагается в одной ячейке. Все ячейки-местоположения товаров всех заказов на этаже мезонина, включая пункт контроля, составляют множество V y .

Для каждого заказа оЕ От у на этаже fE F создается множество пик-листов В_о (|В_о| = |о|), по которым распределяются строки заказа. Суммарный объем товаров, назначенных в пик-лист, не должен превышать максимальной вместимости коробки.

На этажах склада работают сборщики, управляющие тележками (Р - множество сборщиков). Работа комплектовщика в течение смены заключается в выполнении пик-рейсов - заданий по сбору товаров со стеллажей в коробки, помещенные в одну тележку. Множество С у - множество пик-рейсов (телег) для сбора множества заказов на этаже fE F (|С у | = T._OE or _f |о|) • В каждом пик-рейсе сЕ С у могут быть коробки, сформированные для сбора заказов разных магазинов, а общее количество пик-листов, объединенных в пик-рейс, не должно превышать максимальной вместимости телеги (cartCap).

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

Целью решения задачи сбора заказов и построения расписания работы сборщиков является поиск для каждого сменного задания такого распределения заказов по пик-листам и пик-рейсам, при котором общее время, затрачиваемое на выполнение сменного задания, будет минимальным. Общее время сбора сменного задания - это максимальное из времен выполнения задания сборщиками на каждом этаже склада. Время выполнения задания сборщиком - суммарное время на сбор назначенных ему пик-рейсов. Время на сбор пик-рейса сборщиком рЕР оценивается как сумма времени на сбор нужного количества товаров, с учетом его скорости подбора (•Vp^tcktn9 ), и времени на перемещение с учетом его скорости маршрутизации (V p^OUling ).

Переменные оптимизационной задачи:

• •    x_sb - индикаторная переменная, которая показывает включена ли строка s из заказа оЕ Ог_г в пик-лист ЬЕ В_о (x_sb = 1) или нет (x_sb = 0);

• •    h_sc - индикаторная переменная, которая показывает включена ли строка s из заказа оЕ Ог_г в пик-рейс сЕ С у (h_sc = 1) или нет (h_sc = 0);

• •    У_Ьс — индикаторная переменная, которая показывает включен ли пик-лист ЬЕ В_о , формируемый для заказа оЕ Ог у , в пик-рейс сЕ С у (y_bc = 1) или нет (y_bc = 0);

• •    w_lc - индикаторная переменная, которая показывает нужно ли посетить ячейку 1Е V y при сборе пик-рейса сЕ С у (w_lc = 1) или нет (w_lc = 0);

• •    z_lmc - индикаторная переменная, которая показывает пройдет ли сборщик при сборе пик-рейса сЕ С у от ячейки 1Е V y к ячейке тЕ V y (z i _mc = 1) или нет (z i _mc = 0);

• •    U i _c - потенциал вершины (позволяет определить последовательность посещения вершин 1Е V y при выполении пик-рейса сЕ С у на этаже fE F) [5];

  •

  
  

  •

  
  

  •

  
  

  •

  
  

  r_cp - переменная, которая показывает расстояние, которое пройдет сборщик pe Р при выполнении пик-рейса ce U f _eF O f ;

  n_cp - переменная, которая показывает количество товара, собираемое сборщиком pe Р при выполнении пик-рейса ce U f _eF O f ;

  q_cp - индикаторная переменная, которая показывает собирается ли пик-рейс ce U f _eF O f сборщиком pe Р (q_cp = 1) или нет (q_cp = 0);

  g_P f - индикаторная переменная, которая показывает работает ли сборщик pe Р на этаже feF

  
  

  (9 pf = 1) или нет (9 pf = 0).

  Для минимизации общего времени сбора заказов сформулирован критерий оптимизации (1), ответствии с которым минимизируется наибольшее время выполнения заданий сборщиками на дом этаже склада:

  
  

  в со-каж-

  
  

  V V f ^r cp       ⁿ cp \    .

  max Z Z l>=J⁺7E=J I ^ ^min . feFceCfVp         ^ р     /

  Время на выполение задания сборщиком – суммарное время, которое он тратит на сбор

  
  
  
  

  всех

  
  

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

  
  

  _;>ZZ- ' • , ⁿ . '

  ^{- Z Z} \ /outms ⁺ picfcmy I' feFcec_f\^viP           ^v p       /

  
  

  v p e Р,

  
  
  
  

  то можно определить целевую функцию задачи: t+pZZZZ y_bc ^ min,

  
  
  
  

  feF ceC f oeor f beB_o

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

  Далее кратко описана система ограничений задачи.

  Формирование пик-листов и пик-рейсов

  Каждая строка каждого заказа на каждом этаже присутствует только в одном пик-листе:

  
  

  Z- '

  
  

  v f eF, о e Or f , seo.

  
  

  beB₀

  Каждая строка каждого заказа на каждом этаже должна собираться только в одном пик-рейсе:

  Z h_sc = 1, VfeF, о e Or f , seo.

  cec_f

  
  
  
  
  
  

  Каждый пик-лист из множества возможных пик-листов либо встречается в одном пик-рейсе, либо

  
  

  не собирается

  
  

  совсем:

  
  

  Z ■ ■ <1,

  
  

  VfeF, о e Or_f, be B_o.

  
  
  
  

  В каждый сти коробки:

  
  

  сес_?

  пик-лист назначено столько товаров, что их суммарной объем не первышает вместимо-

  
  

  Z^Ss " ^x _sb • Z F_bc,    V f eF, о e Or f , b e B_o.

  seo                        ceC f

  
  
  
  

  В каждый пик-рейс назначено столько пик-листов, что их суммарное количество не превышает вместимости телеги:

  
  

  zz y_bc<  cartOap,   VfeF, c eO f .

  
  
  
  

  oeor f beB₀

  Соответственно, если y_bc = 0 и пик-лист не собирается в допустимом решении, то по ограничению (7) в него не будут назначены товары (строки заказа). Неравенства (7) не исключают ситуации, когда в пик-лист b не назначены строки заказов (Z_seo p_s -x_sb = 0, когда все x_sb = 0), однако он сам

  
  

назначен в один из пик-рейсов с (какой-то из y_bc может быть равен единице). Для исключения «пустых» пик-листов из оптимального решения в целевую функцию (3) введен штраф за использование коробок.

Установление взаимосвязи между переменными x_sb , y_bc и h_sc , то есть соответствия между строкой заказа, пик-листом и пик-рейсом, в которые она будет собрана:

h_sc >x_sb + y_bc -1,VfEF, о eOr y , seo, ЬеВ₀, се C y . (9)

Если строка s не лежит в пик-листе b (x_sb = 0), а пик-лист b не собирается в пик-рейсе с (y_bc = 0), то индикаторная переменная, которая показывает, что строка s собирается в пик-рейсе b (h_sc) не обязательно будет равна нулю. Так как строка s должна лежать в одном пик-листе по ограничению (4), то найдется x_sb , = 1, что с помощью ограничения (7) отметит какой-то один из y_b , _c . Тогда по ограничению (9) соответствующий h_sc будет равен единице.

Формирование оптимального маршрута движения сборщиков

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

w_lc>a_ls'h_sc, V feF, оeOr y , leV y , се С у , seo, (10) где a_ls - индикатор, который показывает, необходимо ли посетить местоположение le V y для сбора строки s заказа ое Or y на этаже feF (a_ls = 1) или нет (a_ls = 0).

^ meV y , ^Z lmc — ^W lc , ^{Vf eF} , ^{l eV} y , ^{с e C} y , m*l

^ ^Z lmc = ^W mc , lev y , m^l

^ lc ^- ^ mc ^{+ |V} y ^| ' ^Z lmc ^{— |V} y ^|- 1,

V f eF, m eV y , с e C y ,

ll^s'hsc

oeO y seo

= ^^ cp , pep

V f eF, с eCy

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

Формирование расписания работы сборщиков

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

г™п™ routing + picking С 6Cf, p 6 P.(16)

Vp         V

Для оценки верхней границы M pf времени выполнения пик-рейса сборщиком p6 P для каждой строки заказа на этаже f6 F необходимо рассчитать: время на движение комплектовщика к ячейке с указанным товаром и возвращение к зоне котроля, время на сбор товаров, с учетом его скоростей маршрутизации и подбора. Время на выполнение пик-рейса не должно превышать суммарное время на индивидуальный подбор всех строк сборщиком на этаже.

Условие (17) устанавливает, что пик-рейс либо назначен одному сборщику, либо не будет выполняться:

^9 ср ^— 1,   c ⁶ U ^c f                             ₍₁7)

p6P               f6F

В правой части каждого из ограничений (14) не более одной величины т_с р может принимать значение больше нуля. Ситуация, в которой т_с р >0 и т_с р, >0 невозможна, так как это приведет к тому, что q_cp = 1 и q_cp , = 1, что нарушает ограничение (17). Аналогично, в правой части каждого из ограничений (15) не более одной величины п_с р может принимать значение больше нуля.

Решение, в котором г_ср >0, п_ср , >0 и г_с , _р , >0, п^ >0, является недопустимым, так как приводит к нарушению ограничения (17).

Пик-рейс С6 U f _6F C f назначен сборщику p6 P (q_cp = 1), если:

• •    т_с р >  0 и п_с р >  0: сборщик полностью выполнил пик-рейс: осуществил и перемещение до ячеек-местоположений товаров и сбор товара;

• •    г_ср > 0, а п_ср = 0: допустимо только решение, при котором соответсвующий h_sc = 0, так как к_5с = 1 приведет к нарушению ограничений (17);

• •    ^г _ср = 0, а п_ср >  0: недопустимое решение. Существуют h_sc = 1 и w_mc = 1, которые приведут к тому, что г_1гтс и г_т1 ,, _с будут равны единице. Поскольку г_ср = 0, то существует г_ср , >  0, который приведет к тому, что q_cp , = 1 (ограничение (16)), что нарушит ограничение (17).

На последнем этапе необходимо определить этаж, на котором работает сборщик. Для этого необходимы ограничения (18) и (19):

^ qcp — |Cf|" 9pf,    ^ f 6F, p 6p(18)

с6С ^

^g13f

f6F

Ограничения, накладываемые на переменные:

xsb, Уьс, hзс, ™1с, zlmc qcp, 8pf 6 {0,1} и1с 6 ^+, т, гср, пср 6 ^+ U{0},(20)

V f 6 F, о 6 OTf, s 6 о, b 6 В_о, с 6 Cf, l,m6Vf, p6P

Числовые расчеты на модельных данных

Предложенная постановка задачи включает три классические оптимизационные проблемы: задачу об упаковке в контейнеры (bin packing) [4], задачу коммивояжера (travelling salesman problem, TSP – маршрутизация сборщиков при сборе товаров), задачу о разбиении (number partition problem, NPP – распределение пик-рейсов по сборщикам) [3].

Оптимизационные задачи упаковки в контейнеры и разбиения множества являются NP-трудными, поскольку и та, и другая может быть сведена к решению нескольких задач о разбиении множества на два подмножества, каждая из которых является NP-полной [2]. Задача коммивояжера так же, как и две других компоненты общей проблемы, является NP-трудной [2]. Таким образом, предложенная выше постановка задачи является комбинацией NP-трудных задач, и нахождение оптимального решения точными методами на полномасштабных данных невозможно.

Для оценки эффектиктивности математической постановки задачи (2) - (20) в статье представлены результаты вычислительных экспериментов. Проведено 4 типа расчетов на модельных задачах со случайно сгенерированными исходными данными. В каждом типе варьировался один параметр, значение остальных оставались зафиксированными. Для каждого типа расчетов и для каждого значения варьируемого параметра было создано 100 наборов данных.

Для генерирования исходных данных и формирования постановки задачи использовалась среда Wolfram Mathematica 12.2 (http://www.wolfram.com), поиск решения выполнялся с помощью оптимизатора Gurobi Optimizer 9.1.1 (https://www.gurobi.com). Расчеты проводились с ограничением по времени в 30 минут. В таблице представлены результаты по среднему времени счета и среднему GAP (отношение значений целевой функции прямой и двойственной задачи для задачи смешанного программирования).

Таблица

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

Параметры модели		1	2	3	4	5
|F| - вар.; |0ту|-3; |o| -3; |F| -5	Время (с)	1624,9	1800	1433,6	1365,6	550,7
	GAP (%)	24,9	22,1	12,7	10,6	0,9
|F| -2; |Оту| - вар.; |o| -3; |F| -3	Время (с)	0,5	12,5	739,4	1546,2	1800
	GAP (%)	0	0	2,74	22,7	35,2
|F| -2; |0ту|-3; |o| - вар.; |F| -3	Время (с)	0,5	15,2	739,4	1548,2	1800
	GAP (%)	0	0	2,74	21,7	36,2
|F| -2; |Orz|-3; joj -3; |F| - вар.	Время (с)	—	24,5	739,4	1462,3	1800
	GAP (%)	—	0	2,74	11,1	22,1

В обозначениях последних пяти столбцов указаны значения, которые принимал параметр, варьируемый в каждой группе расчетов (этот параметр указан в первом столбце как «вар.»). Средний GAP равный нулю говорит о том, что для всех наборов данных найдено оптимальное решение. Для всех типов расчетов, кроме первого, отмечается значительный рост времени расчета и GAP, на котором остановился расчет, что подтверждает экспоненциальный рост времени счета с увеличением объема исходных данных. Для первой группы отмечается сокращение среднего GAP с увеличением количества этажей с 2 до 5. Уменьшение GAP и, соответсвенно, возможного времени счета связано с сокращением доли допустимых вариантов распределения людей по этажам склада в общем количестве возможных перестановок сборщиков и среднего количества сборщиков, назначенных на этаж мезонина.

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

Заключение

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