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

Если вам интересны приложения математики в бизнесе и вы не боитесь жестких тождественных преобразований формул на уровне 5-го класса, то доброго пожаловать под кат!

Статья будет полезна тем, кто внедряет WMS-системы, работает в отрасли складской или производственной логистики, а также программистам, которые интересуются приложениями математики в бизнесе и оптимизацией процессов на предприятии.

Часть вводная


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

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

Когда мы закончили писать статью по алгоритмам оптимизации она получилась очень большой, поэтому накопленный материал мы решили разбить на 2 части:

  • В первой части (эта статья) мы расскажем о том, как мы «строили» математическую модель задачи, и о том с какими большими трудностями мы неожиданно столкнулись при обработке и преобразовании входных данных для алгоритма.
  • Во второй части мы детально рассмотрим реализацию алгоритма на языке C++, проведем вычислительный эксперимент и резюмируем опыт, который мы получили в ходе внедрения таких «интеллектуальных технологий» в бизнес-процессы заказчика.

Как читать статью. Если вы читали предыдущую статью, то можете сразу переходить к главе «Обзор существующих решений», если нет, то описание решаемой проблемы в спойлере ниже.

Описание решаемой проблемы на складе заказчика

Узкое место в процессах


В 2018 году мы сделали проект по внедрению WMS-системы на складе «Торговый дом «ЛД» в г. Челябинске. Внедрили продукт «1С-Логистика: Управление складом 3» на 20 рабочих мест: операторы WMS, кладовщики, водители погрузчиков. Склад средний около 4 тыс. м2, количество ячеек 5000 и количество SKU 4500. На складе хранятся шаровые краны собственного производства разных размеров от 1 кг до 400 кг. Запасы на складе хранятся в разрезе партий, так как есть необходимость отбора товара по FIFO.

В ходе проектирования схем автоматизации складских процессов мы столкнулись с существующей проблемой неоптимального хранения запасов. Специфика хранения и укладки кранов такая, что в одной ячейке штучного хранения может находиться только номенклатура одной партии (см. рис. 1). Продукция приходит на склад ежедневно и каждый приход – это отдельная партия. Итого, в результате 1 месяца работы склада создаются 30 отдельных партий, притом, что каждая должна хранится в отдельной ячейке. Товар зачастую отбирается не целыми палетами, а штуками, и в результате в зоне штучного от-бора во многих ячейках наблюдается такая картина: в ячейке объемом более 1м3 лежит несколько штук кранов, которые занимают менее 5-10% от объема ячейки.


Рис 1. Фото нескольких штук в ячейке

На лицо неоптимальное использование складских мощностей. Чтобы представить масштаб бедствия могу привести цифры: в среднем таких ячеек объемом более 1м3 с «мизерными» остатками в разные периоды работы склада насчитывается от 100 до 300 ячеек. Так как склад относительно небольшой, то в сезоны загрузки склада этот фактор становится «узким горлышком» с сильно тормозит складские процессы приемки и отгрузки.

Идея решения проблемы


Возникла идея: партии остатков с наиболее близкими датами приводить к одной единой партии и такие остатки с унифицированной партией размещать компактно вместе в одной ячейке, или в нескольких, если места в одной не будет хватать на размещение всего количества остатков. Пример такого «сжатия» изображен на рисунке 2.


Рис.2. Схема сжатия остатков в ячейках

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

Процесс решения такой задачи разбивается на 2 этапа:

  • на первом этапе мы находим близкие по дате группы партий для сжатия (этой задаче посвящения предыдущая статья);
  • на втором этапе мы для каждой группы партий вычисляем максимально компактное размещение остатков товара в ячейках.

В текущей статье мы остановимся на втором этапе алгоритма.

Обзор существующих решений


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

В первую очередь необходимо отметить продукт «1С: Предприятие 8. WMS Логистика. Управление складом 4», который принадлежит и тиражируется фирмой 1С и относится к четвертому поколению WMS-систем, разработанных компанией AXELOT. В данной системе заявлен функционал компрессии, который призван объединять разрозненные остатки товара в одной общей ячейке. Стоит оговориться, что функционал компрессии в такой системе включает в себя еще и другие возможности, например, исправление размещения товаров в ячейках согласно их ABC классам, но на них мы останавливаться не будем.

Если анализировать код системы «1С: Предприятие 8. WMS Логистика. Управление складом 4» (который в данной части функционала является открытым), то можно заключить следующее. Алгоритм компрессии остатков реализует довольно примитивную линейную логику и не о какой «оптимальной» компрессии речи быть не может. Естественно, кластеризацию партий он не предусматривает. Несколько клиентов, у которых такая система была внедрена, жаловались на результаты планирования компрессии. К примеру, зачастую на практике при компрессии случалась такая ситуация: 100 шт. остатков товара из одной ячейки планируется переместить в другую ячейку, где лежит 1 шт. товара, хотя оптимально с точки зрения затрат времени сделать наоборот.

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

Поиск математической модели задачи


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

Имеется множество ячеек $J$, в которых находятся остатки некоторого товара. Далее такие ячейки будем называть ячейками-донорами. Обозначим $w_j$ объем товара, находящегося в ячейке $$j$$.

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

Имеется множество ячеек $I$, в которые могут быть потенциально помещены остатки из ячеек-доноров. Такие ячейки будем далее называть ячейками-контейнерами. Это могут быть как свободные ячейки на складе, так и ячейки-доноры из множества $J$. Всегда множество $J$ является подмножеством $I$.

Для каждой ячейки $i$ из множества $I$ заданы ограничения на вместимость $d_i$, измеряемые в дм3. Один дм3 представляет собой кубик со сторонами 10 см. Продукция, хранимая на складе достаточно крупная, поэтому в данном случае такой дискретизации вполне хватает.

Задана матрица кратчайших расстояний $s_{ij}$ в метрах между каждой парой ячеек $(i,j)$, где $i$ и $j$ принадлежат множествам $I$ и $J$ соответственно.

Обозначим $S_{ij}$ «затраты» на перемещения товара из ячейки$i$ в ячейку $j$. Обозначим $D_i$ «затраты» на выбор контейнера $i$ для перемещения в него остатков из других ячеек. Как именно и в каких единицах измерения будут вычисляться значения $S_{ij}$ и $D_i$ рассмотрим далее (см. раздел подготовка входных данных), сейчас достаточно сказать, что такие величины будут прямо пропорциональны величинам $s_{ij}$ и $d_i$ соответственно.

Обозначим через $x_{ij}$ переменную принимающую значение 1, если остатки из ячейки $j$ перемещаются в контейнер $i$, и 0 в противном случае. Обозначим через $y_i$ переменную принимающую значение 1, если контейнер $i$ содержит в себе остатки товара, и 0 в противном случае.

Задача ставится так: необходимо найти такое множество контейнеров $I^*$ и таким образом «прикрепить» ячейки-доноры к ячейкам контейнерам, чтобы минимизировать функцию

$\min{F} = \sum _{i \in I,~ j \in J}^{}S_{ij} \cdot x_{ij} + \sum _{i \in I}^{}D_{i} \cdot y_{i}$

при ограничениях

$\sum _{j \in J}^{}w_{j} \cdot x_{ij} \leq d_{i} \cdot y_{i}, ~для ~всех~ i \in I$

Итого в ходе вычисления решения задачи мы стремимся:

  • во-первых, экономить складские мощности;
  • во-вторых, экономить время кладовщиков.

Последнее ограничение означает, что мы не можем перемещать товары в контейнер, который не выбрали, ну и соответственно не «понесли затраты» на его выбор. Так же это ограничение означает, что объем перемещаемых товаров из ячеек в контейнер не должен превышать вместимости контейнера. Под решением задачи будем понимать множество контейнеров $I^*$ и способы прикрепления ячеек-доноров к контейнерам.

Такая формулировка задачи оптимизации является не новой, и была исследована многими математиками еще с начала 80-х годов прошлого столетия. В зарубежной литературе есть 2 задачи оптимизации с подходящей математической моделью: Single-Source Capacitated Facility Location Problem и Multi-Source Capacitated Facility Location Problem (о различиях задач поговорим далее). Стоит сказать, что в математической литературе постановки таких двух задач оптимизации формулируются в терминах размещения предприятий на местности, отсюда и название «Facility Location». По большей части это дань традиции, так как впервые потребность в решении таких комбинаторных задач пришла из сферы логистики, в большинстве своем, военно-промышленной отрасти в 50-х годах прошлого столетия. В терминах размещения предприятий такие задачи формулируются так:

  • Есть конечное множество городов, где потенциально возможно разместить производственные предприятия (далее города-производители). Для каждого города-производителя заданы затраты на открытие в нем предприятия, а также ограничение на производственные мощности открываемого в нем предприятия.
  • Есть конечное множество городов, где фактически находятся клиенты (далее города-клиенты). Для каждого такого города-клиента задан объем спроса на продукцию. Для простоты будем считать, что продукт, который производят предприятия и потребляют клиенты один.
  • Для каждой пары город-производитель и город-клиент задана величина транспортных затрат на доставку требуемого объема продукции от производителя клиенту.

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

  • Суммарные затраты на открытия предприятий и транспортные затраты были минимальны;
  • Объем спроса клиентов, прикрепленных к какому-либо открытому предприятию, не превосходил производственных мощностей этого предприятия.

Теперь стоит сказать о единственном различии в этих двух классических задачах:

  • Single-Source Capacitated Facility Location Problem – клиент снабжается только из одного открытого предприятия;
  • Multi-Source Capacitated Facility Location Problem – клиент может снабжаться из нескольких открытых предприятий одновременно.

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


Рис.3. а) Multi-Source Capacitated Facility Location Problem


Рис.3. b) Single-Source Capacitated Facility Location Problem

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

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

  • города-клиенты – это ячейки-доноры $J$ с остатками товара,
  • города-производители – ячейки-контейнеры $I$, в которые предполагается поместить остатки из других ячеек,
  • транспортные затраты – затраты времени $S_{ij}$ кладовщика на перемещения объема товара из ячейки-донора $j$ в ячейку-контейнер $i$;
  • затраты на открытие предприятия – затраты на выбор контейнера $D_i$, равные объему ячейки-контейнера $i$, умноженный на некоторый коэффициент экономии свободных объемов (значение коэффициента всегда > 1) (см. раздел подготовка входных данных).

После того как аналогия с известными классическими поставками задачи проведена, необходимо ответить на важный вопрос, от которого зависит выбор архитектуры алгоритма решения: перемещение остатков из ячейки-донора возможно только в один и только один контейнер (Single-Source), или же возможно перемещение остатков в несколько ячеек-контейнеров (Multi-Source)?

Стоит отметить, что на практике обе постановки задачи имеют место быть. Приведем все «за» и «против» для каждой такой постановки ниже:
Вариант задачи Плюсы варианта Минусы варианта
Single-Source Операции перемещения товаров, рассчитанные по этому варианту задачи:
  • требуют меньше контроля со стороны кладовщика (взял ВСЕ из одной ячейки, положил ВСЕ в другую ячейку-контейнер), что устраняет риски: ошибок при пересчете количества товара при выполнении операций «Положить в ячейку»; ошибок ввода пересчитанного количества в ТСД;
  • Не требуется времени на пересчет количества товаров при выполнении операций «Положить в ячейку» и ввод их в ТСД
Multi-Source Сжатия, рассчитанные по этому варианту задачи, как правило более компактны на 10-15% по сравнению со сжатиями, рассчитанными по варианту «Single-Source». Но также заметим, что чем меньше количество остатков в ячейках-доноров, тем такое различие в компактности меньше Операции перемещения товаров, рассчитанные по этому варианту задачи:
  • требуют большего контроля со стороны кладовщика (необходимо пересчитывать количество товара, перемещаемого в каждую из спланированных ячеек-контейнеров), что устраняет риск ошибки при пересчете количества товара и ввода данных в ТСД при выполнении операций «Положить в ячейку»
  • Требуется время на пересчет количества товаров при выполнении операций «Положить в ячейку»
  • Требуется время на «накладные расходы» (остановиться, подойти к поддону, отсканировать ШК ячейки-контейнера) при выполнении операций «Положить в ячейку»
  • Иногда алгоритм может «дробить» количество практически полного палета между большим количеством ячеек-контейнеров, где есть уже подходящий товар, что, с точки зрения заказчика, было неприемлемо
Таблица 1. Плюсы и минусы вариантов Single-Source и Multi-Source.

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

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

Подготовка входных данных


Перед тем как приступать к анализу и разработке алгоритма для решения задачи, необходимо определиться какие данные и в каком виде мы будем подавать ему на вход. С объемами остатков товаров в ячейках-донорах и вместимостью ячеек-контейнеров проблем нет, так как это тривиально – такие величины будут измеряться в м3, но вот с затратами на использование ячейки-контейнера и матрицей затрат на перемещение не все так просто!

Вначале рассмотрим расчет затрат на перемещение товаров из ячейки-донора в ячейку-контейнер. В первую очередь необходимо определиться в каких единицах измерения мы будем рассчитывать затраты на перемещение. Два самых очевидных варианта – это метры и секунды. В «чистых» метрах затраты на перемещение считать бессмысленно. Покажем это на примере. Пусть ячейка $A$ расположена на первом ярусе, ячейка $В$ удалена на 30 метров и располагается на втором ярусе:

  • Перемещение из $A$ в $B$ более затратно, чем перемещение из $B$ в $A$, так как спускать вниз со второго яруса (1,5-2 метра от пола) легче, чем поднимать на второй, хотя расстояние будет пройде-но одинаковое;
  • Переместить 1 шт. товара из ячейки $A$ в $B$ будет легче, чем переместить 10 шт. того же товара, хотя расстояние будет пройдено одинаковое.

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

Пусть из ячейки $j$ перемещается $N_j$ шт. товара в контейнер $i$. Пусть $S_{run}$ – средняя скорость движения работника по складу, измеряемая в м/сек. Пусть $S_{get}$ и $S_{put}$ – средние скорости разового выполнения операций взять и положить соответственно для объема товара равным 4 дм3 (средний объем, который берет за 1 раз сотрудник на складе при выполнении операций). Пусть $H_{get}$ и $H_{put}$ высота ячеек, из которых выполняются операции взять и положить соответственно. Например, средняя высота первого яруса (пол) 1 м, второго ярус 2 м и т.д. Тогда формула для расчета общего времени на выполнение операции перемещения $T_{ij}$ следующая:

$T_{ij}= \left( N_{j} \cdot \frac{w_{j}}{4} \right) \cdot S_{get} \cdot H_{get}+s_{ij} \cdot S_{run}+ \left( N_{j} \cdot \frac{w_{j}}{4} \right) \cdot S_{put} \cdot H_{put}.$

В таблице 2 приведена статистика времени выполнения каждой элементарной операции, собранная сотрудниками склада с учетом специфики хранимого товара.
Наименование операции Обозначение Среднее значение
Средняя скорость движения работника по складу $S_{run}$ 1,5 м/сек
Средняя скорость выполнения одной операции положить (для объема товара 4 дм3) $S_{put}$ 2,4 сек
Таблица 2. Среднее время выполнение складских операций

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

  • во-первых, затраты должны находиться в прямой зависимости от объема ячейки – один и тот же объем остатков, перемещаемых из ячеек-доноров, лучше положить в контейнер меньшего объема, чем в большой контейнер, при условии, что такой объем полностью вмещается в оба контейнера. Так, минимизируя общие затраты на выбор контейнеров, мы стремимся сэкономить «дефицитные» свободные складские мощности в области зоны отбора, для выполнения последующих операций размещения товара в ячейках. На рисунке 4 продемонстрированы варианты перемещения остатков в большой и маленький контейнеры и последствия таких вариантов перемещения при выполнении последующих складских операций.
  • во-вторых, поскольку нам в решении исходной задачи необходимо минимизировать именно общие затраты, а это сумма как затрат на перемещение, так и затрат на выбор контейнеров, то объемы ячеек в метрах кубических необходимо как-то увязать с секундами, что далеко не тривиально.


Рис. 4. Варианты перемещения остатков в контейнеры разной вместимости.

На рисунке 4 красным цветом изображен объем остатков, который уже не вмещается в контейнер на втором этапе размещения последующих товаров.

Поможет увязать метры кубические затрат на выбор контейнера с секундами затрат на перемещение следующие требования к вычисляемым решениям задачи:

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

Начнем с последнего требования. Для того, чтобы конкретизировать многозначное слово «баланс» мы провели опрос сотрудников склада с целью выяснить следующее. Пусть имеется ячейка-контейнер объема $d_0$, в которую назначено перемещение остатков товаров из ячеек-доноров и общее время такого перемещения равно $T_0$. Пусть имеется еще несколько альтернативных вариантов размещения того же количества товара из тех же ячеек-доноров в другие контейнеры, где каждое размещение имеет свои оценки $d_1$, где $d_1$<$d_0$ и $T_1$, где $T_1$>$T_0$.

Ставится вопрос: какой минимальный выигрыш в объеме $d_0-d_1$ приемлем, при заданном значении проигрыша по времени $T_1-T_0$? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.


Рис. 5. Диаграмма зависимости минимальной допустимой экономии объема от увеличения разницы во времени выполнения операции

То есть, если дополнительные затраты по времени составляют 40 секунд, то мы готовы их потратить только тогда, когда выигрыш в объеме будет не менее 500 дм3. Несмотря на то, что в зависимости наблюдается небольшая нелинейность, для простоты дальнейших расчетов будем полагать, что зависимость между величинами линейна и описывается неравенством

$\frac{d_{0}-d_{1}}{10} \geq T_{1}-T_{0}$

На рисунке ниже рассмотрим следующие способы размещения товара в контейнеры.


Рис. 6. Вариант (а): 2 контейнера, общий объем 400 дм3, суммарное время 150 сек.

Рис. 6. Вариант (b): 2 контейнера, общий объем 600 дм3, суммарное время 190 сек.

Рис. 6. Вариант (с): 1 контейнер, общий объем 400 дм3, суммарное время 200 сек.

Вариант (а) выбора контейнеров является более предпочтительным, чем изначальный вариант, так как выполняется неравенство: (800-400)/10>=150-120 из чего следует 40 >= 30. Вариант (b) является менее предпочтительным, чем изначальный вариант, поскольку неравенство не выполняется: (800-600)/10>=190-150 из чего следует 20 >= 40. Но вариант (с) не укладывается в подобную логику! Рассмотрим этот вариант подробнее. С одной стороны неравенство (800-400)/10>=200-120, а значит неравенство 40 >= 80 не выполняется, что говорит о том, что выигрыш по объему не стоит такого большого проигрыша по времени.

Но с другой стороны, в таком варианте (с) мы не просто сокращаем совокупный занятый объем, но также и уменьшаем количество занятых ячеек, что является первым из двух важных требований к вычисляемым решениям задачам, перечисленных выше. Очевидно, для того, чтобы данное требование начало выполняться необходимо в левую часть неравенства добавить некоторую положительную константу $Const$, причем такую константу необходимо добавлять только тогда, когда количество контейнеров уменьшается. Напомним, что $y_i$ — это переменная, равная 1, когда контейнер $i$ выбран, и 0 когда контейнер $i$ не выбран. Обозначим, $I_0$ – множество контейнеров в изначальном решении и $I_1$ – множество контейнеров в новом решении. В общем виде новое неравенство будет выглядеть так:

$\sum _{i \in I_{0}}^{}\frac{d_{i}}{10}+Const \cdot \sum _{i \in I_{0}}^{}y_{i}- \left( \sum _{i \in I_{1}}^{}\frac{d_{i}}{10}+Const \cdot \sum _{i \in I_{1}}^{}y_{i} \right) \geq T_{1}-T_{0}$

Преобразовывая неравенство выше, получаем

$\sum _{i \in I_{0}}^{}\frac{d_{i}}{10}+Const \cdot \sum _{i \in I_{0}}^{}y_{i}+T_{0} \geq \sum _{i \in I_{1}}^{}\frac{d_{i}}{10}+Const \cdot \sum _{i \in I_{1}}^{}y_{i}+T_{1}$

Исходя из этого, имеем формулу для расчета общей стоимости $F_k$ некоторого варианта решения задачи:

$F_{k}= \sum _{i \in I_{k}}^{}\frac{d_{i}}{10}+Const \cdot \sum _{i \in I_{k}}^{}y_{i}+T_{k}.$

Но теперь возникает вопрос: а какое значение должна иметь такая константа $Const$? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Пусть $S_{max}$ – максимальное расстояние между ячейками склада одной зоны ABC, равное в нашем случае 100 м. Пусть $d_{max}$ – максимальный объем ячейки-контейнера на складе, равный в нашем случае 1000 дм3.

Первый способ расчета величины $Const$. Рассмотрим ситуацию, когда есть 2 контейнера на первом ярусе, в которых уже физически находится товар, то есть они сами являются ячейками-донорами, а затраты на перемещение товара в те же ячейки, естественно равно 0. Необходимо найти такое значение константы $Const$, при котором было бы выгодно всегда перемещать остатки из контейнера 1 в контейнер 2. Подставляя значения $S_{max}$ и $d_{max}$ в неравенство, приведенное выше, получаем:

$\frac{d_{max}}{10}+Const \geq S_{max} \cdot s_{run}+\frac{d_{max}}{4} \left( s_{get}+s_{put} \right),$

из чего следует

$Const \geq S_{max} \cdot s_{run}+d_{max} \left( \frac{s_{get}+s_{put}}{4}-\frac{1}{10} \right) .$

Подставляя значения среднего времени выполнения элементарных операций в формулу выше получаем

$Const \geq 100 \cdot 1,5+1000 \left( \frac{9}{10} \right) \rightarrow Const \geq 1050.$

Второй способ расчета величины $Const$. Рассмотрим ситуацию, когда есть $N$ ячеек-доноров из которых планируется перемещать товар в контейнер 1. Обозначим $S_{1j}$ – расстояние от ячейки-донора $j$ до контейнера 1. Имеется также контейнер 2, в котором уже есть товары, и объем которого позволяет вместить остатки из всех $N$ ячеек. Для простоты будем полагать, что объем товара, перемещаемого из ячеек-доноров в контейнеры одинаков и равен $d_{max}/N$. Требуется найти такое значение константы $Const$, при котором размещение всех остатков из $N$ ячеек в контейнер 2 было бы всегда выгоднее, чем размещение их в разные контейнеры:

$2 \cdot \frac{d_{max}}{10}+2 \cdot Const+N \left( S_{1j} \cdot s_{run}+\frac{d_{max}}{4 \cdot N} \left( s_{get}+s_{put} \right) \right) \geq \qquad\qquad\qquad\qquad\qquad \\ \qquad\qquad\qquad\qquad\qquad \frac{d_{max}}{10}+Const+N \cdot \left( S_{max} \cdot s_{run}+\frac{d_{max}}{4 \cdot N} \left( s_{get}+s_{put} \right) \right) .$

Преобразовывая неравенство получаем

$\frac{d_{max}}{10}+Const+N \cdot S_{1j} \cdot s_{run} \geq N \cdot S_{max} \cdot s_{run} \rightarrow Const \geq N \cdot s_{run} \left( S_{max}-S_{1j} \right) -\frac{d_{max}}{10}.$

Для того, чтобы «усилить» значение величины $Const$, примем, что $S_{1j}$ = 0. Среднее количество ячеек, участвующих обычно в процедуре сжатия остатков на складе равно 10. Подставляя известные значение величин, имеем следующее значение константы

$Const \geq 10 \cdot 1,5 \cdot 100-\frac{1000}{10} \rightarrow Const \geq 1400.$

Берем наибольшее значение, вычисленное по каждому варианту, это и будет значение величины $Const$ для заданных параметров склада. Теперь для завершенности запишем формулу расчета общих затрат $F_k$ для некоторого допустимого решения $k$:

$F_{k}= \sum _{i \in I_{k}}^{}\frac{d_{i}}{10}+1400 \cdot \sum _{i \in I_{k}}^{}y_{i}+T_{k}.$

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

Заключение


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

В следующей статье мы наконец-то придем к тому, ради чего задумывались 2 предыдущие публикации – к алгоритму дискретной оптимизации.

Статью подготовил
Роман Шангин, программист департамента проектов,
компания Первый Бит, г. Челябинск

Комментарии (21)


  1. AWSVladimir
    14.08.2019 16:00

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

    Возникла идея: партии остатков с наиболее близкими датами приводить к одной единой партии
    На фарм. складе, вас бы за эту «идею» расстреляли, а потом там же сожгли.
    Что мешало сделать адреса с полной заполняемостью и с частичной, где в одной частично заполняемой ячейки сделать 10 передвигаемых-картонок-перегородок и каждой присвоить адрес?
    Это проще и эффективней, чем творить «ЭТО ЧУДО» (хотел выразится по французски, но сдержался)
    PS:
    Комментов от меня больше не будет, если что то надо, прошу в личку, кармас-с-с…


    1. Warhammer_iii
      15.08.2019 04:40

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


    1. 1c1bit Автор
      15.08.2019 05:35

      С точки зрения фарм склада Вы, возможно, правы, с точки зрения специфики склада шаровых кранов — нет. С Warhammer_iii согласен.

      Перечислю по пунктам почему не правы:
      1. Укладка товаров. Специфика укладки в ячейки у каждого крана разная. Довольно много с горизонтальной укладкой, то есть сначала кладется ряд, а потом на него следующий. Причем 1 на 1 краны редко когда более менее устойчиво поставить можно — упадут (и перегородку, тем более картонную, сломают, так как вес крана небольшого 2-3 кг, а есть и побольше). Для фарм склада такого нет очевидно, там 99% прямоугольники и вес маленький.
      2. Логика WMS-систем. Почти во всех WMS системах задаются фиксированное, конечное множество ячеек, а потом программа с ними уже работает. При необходимости ячейки могут добавляться или убавляться или редактироваться их параметры, если например подошел сезон и мы хотим переконфигурировать какую-то зону склада, чтобы, к примеру, увеличить «фронт отбора». НО, если мы используем перегородки, то сколько их может быть? 2,3, 5 или 15?! Что программа сама будет создавать эти ячейки в базе и присваивать им адреса? Кто потом будет клеить (а потом и сдирать) штрих-кода с адресом на такие «картонные ячейки»? Тоже программа? :) По мне так картонная технология какая-то оторванная от реалий WMS-систем. При бумажном учете без системы WMS, такое наверное прокатило бы.
      3. Здравый смысл. Вот представьте: товар с одной партией у Вас разместился в 3 разные ячейки, которые находятся на расстоянии 5-10 метров друг от друга. Товар в них практически закончился и в каждой остались мизерные остатки (отбирали каждый раз из разной, чтобы минимизировать пройденное расстояние, FIFO здесь нет, дата то партии одна). Потом приходят еще 2 палета точно такого же товара с другой партией, а других ячеек кроме этих нет. Внимание знатоки, какой вариант лучше?

      • Вариант перегородок. Программа начнет дробить товар в каждую ячейку с учетом ее заполненности, и кладовщик будет тратить уйму времени на перелапачивание этих 2-х палет, ну и, конечно же, ставить картонные перегородки :).
      • Вариант сжатия. Выполнить 1 раз сжатие остатков из 2-х ячеек в одну за 5 минут и потом просто поместить 2 палета в свободные ячейки.


      P.S. Прежде чем комменты писать злобные и звонить по коллегам скайпу, вникните в тему :)


      1. Gar02
        15.08.2019 10:48

        У меня возникло стойкое ощущение, что автор автоматизировал бардак. Может, сначала надо было прояснить странные моменты в бизнес-процессах?
        Мне непонятно, почему один товар из разных партий пихают в разные ячейки. Разумное правило (приходы одного товара в разные дни == разные партии) слепили с (разные партии == разные ячейки) и превратили в священную корову.
        1. Разная входная цена? Так вы же по FIFO списываете, уходит одна партия — пошла другая. Какая вам разница, кран из какой партии реально пойдёт покупателю?
        1.1. Взаиморасчёты с поставщиками, поставляющими одинаковый товар (почти фантастика)? Ведите в долях, пропорционально входному объёму. Можете даже выбрать поставщиков, «которые равнее».
        1.2. Гарантия по расходной накладной? Так наверняка у крана есть серийный номер. По нему и гарантируйте.
        1.3. Разительно разное качество партий (надеюсь, что нет)? Даже не знаю, что сказать. Рашен бузинес.
        2. Тупое давление заказчика? Привести ему цифры потерь.
        В общем, ясно, что мне ни фига не ясно.


        1. 1c1bit Автор
          15.08.2019 11:29

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


          1. Gar02
            15.08.2019 12:03

            Нет, конечно. Зачем краны таскать строго по FIFO, если они идентичны друг другу?
            Какая такая религия запрещает отгрузить брата-близнеца, лежащего сверху? Именно эти вопросы я и хотел прояснить в пунктах, которые Вы проигнорировали.


            1. MinimaJack
              15.08.2019 14:07

              срок использования есть у любого продукта...


              Специфика такова, что списание должно быть максимально по FIFO… например через 1 год — начинает исчезать надпись с этикетки, через 2 возможно изменение цвета краски, 3 проблемы со смазкой… и т.п. и т.д.
              Отправить клиенту партию новых, а потом прислать старую; после такого выслушивается миллион претензий и рекламаций с требованиями о скидках.
              Серийный номер явно не гравируется(лазером наносится), а значит старую продукцию можно относить в ремонт с новой этикеткой :) "поломалось на гарантии" — вы же нам шлете "старье"


            1. 1c1bit Автор
              15.08.2019 14:11

              c MinimaJack согласен. У каждого товара есть срок годности и краны не исключение, не смотря на то, что срок годности на складе (без спец смазки и доп. обслуживания) дольше чем у лекарств. Например, у мебели вообще нет срока годности, лежи себе и лежи, но Икея по FIFO работает :)


              1. Gar02
                15.08.2019 15:19

                Логично. Хитрожпопие у клиентов развито на 146%.
                Но сроки хранения… Сдаётся мне, что если товар не уходит со склада по году-два, кто-то не хило ошибается в объёмах закупок. Или такие запасы обусловлены тем, что у клиента непредсказуемо скачут объёмы отгрузки?


                1. MinimaJack
                  15.08.2019 15:57

                  Это производство, а не торговое предприятие =)
                  Товар специфический, я бы сказал в чем то уникальный.


                  1. Вариант: стиль Савдэп — производим что угодно, лишь бы рабочий не стоял.
                    В итоге склады перегружены, валяется старьё...
                  2. Производим по плану(прошлого года как пример), не взлетело — храним пока не сгниёт или не продастся.
                  3. Клиент отказался — храним
                  4. Кладовщики берут всегда свежий товар — работают по FILO, в таком случае старье всегда будет.

                  WMS решает только 4-ю проблему, для других как мертвому припарка — вроде все под контролем, но проблему со старыми остатками оно не решит.


                  Остальное должен разруливать отдел ПДО…


                  1. Gar02
                    15.08.2019 17:10

                    LIFO (FILO — про стоимость разгрузки судна).
                    И не надо гнать на СССР. Затоваривания складов там не было, пока не стали придерживать продукцию перед развалом.


                1. 1c1bit Автор
                  16.08.2019 04:37

                  смотрите пункт 4 у MinimaJack. Там никто не ошибается особо в объемах и разрухи там нет, просто если вы не будете работать по FIFO, то никто не гарантирует, что у Вас не будет старого товара на складе даже при высокой оборачиваемости. Условно вы всегда будете брать верхние свежие из стека, а нижние старые будут оставаться.


                  1. Gar02
                    16.08.2019 09:08

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


  1. gennayo
    16.08.2019 08:02

    По FIFO вы сможете работать при отсутствии возвратов. А иначе FEFO. Терминологию надо соблюдать :)


    1. 1c1bit Автор
      16.08.2019 08:19

      FEFO это когда First Expire, First Out — первый истекает — первый выходит. У нас же, именно истечение срока годности, не рассматривалось, поэтому и назвали FIFO, от слова «In» :)


  1. gennayo
    16.08.2019 09:01

    Так у вас есть партии в разрезе дат, значит рассматривали. В части ВМС правильнее употреблять FEFO в этом случае


    1. 1c1bit Автор
      16.08.2019 09:08

      в FEFO при ротации грузов на складе учитывается остаточный срок годности товара. Мы именно остаток не считали, поэтому и не употребили слово FEFO. Или Вы другое имели ввиду?


  1. gennayo
    16.08.2019 11:19

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


    1. 1c1bit Автор
      16.08.2019 11:34

      ну да, на самом деле штуки похожи, Вы правы. Но, мне кажется, что все таки мы говорим о разных немного вещах.

      Срок годности 10 дней.
      Партия 1. Пришел товар 1 шт 1.01 с остатком срока годности 10 дней.
      Партия 2. Пришел товар 1 шт 5.01 с остатком срока годности 2 дня.

      По FIFO уйдет товар партии 1, по FEFO партия 2. Ну это по тому определению FEFO, которое я знаю, она в вики, вроде такое же. Если Вы по-другому рассуждаете, дайте ссылку на определение FEFO :)


  1. gennayo
    16.08.2019 13:02

    Так в вашем случае какой вариант? Я так понимаю, что у вас товар на склад поступает с производства в разрезе дат выработки, так же должен и уходить? Тогда для вас без разницы. А если может сначала прийти товар от 10.01 выпуска а потом от 01.01 выпуска, тогда какой должен уйти первым?


    1. 1c1bit Автор
      16.08.2019 13:44

      тогда 01.01, по датам производства конечно. Да, краны поступают из производства, поэтому у них остаточный срок годности один и тот же изначально. Здесь отбор по FIFO и FEFO даст один и тот же результат. Поэтому и без разницы как называть :) Хотя, в чем-то Вы и правы.