Дискретна математика за WMS: алгоритъм за компресиране на стоки в клетки (част 1)

В статията ще ви разкажем как решавахме проблема с недостига на свободни клетки на склада и за разработването на алгоритъма за дискретна оптимизация за решаване на такъв проблем. Ще ви разкажем как «изграждахме» математическия модел на оптимизационната задача и с какви трудности неочаквано се сблъскахме при обработката на входните данни за алгоритъма.

Ако ви интересуват приложенията на математиката в бизнеса и не се страхувате от строги тъждествени преобразования на ниво 5-ти клас, то добре дошли под кота!

Статията ще бъде полезна за тези, които внедряват WMS-системи, работят в сферата на складовата или производствената логистика, а също и за програмисти, които се интересуват от приложенията на математиката в бизнеса и оптимизацията на процесите в предприятието.

Част на въведението

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

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

Когато завършихме статията за алгоритмите за оптимизация, тя стана много обемна, затова решихме да разделим събрания материал на 2 части:

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

Как да четете статията. Ако сте прочели предишната статия, можете веднага да преминете към глава «Преглед на съществуващите решения». Ако не, описанието на решаваната проблема е в спойлер по-долу.

Описание на решаваната проблема на склада на клиента

Тясно място в процесите

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

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

Рис 1. Снимка на няколко бройки в клетка

Очевидно е неефективното използване на складовите капацитети. За да илюстрирам мащаба на бедствието, мога да дам данни: средно в складовата работа има от 100 до 300 клетки с обем над 1м³ с "мизерни" остатъци в различни периоди. Тъй като складът е сравнително малък, през сезоните на натоварване този фактор става „узко място“, което сериозно забавя складските процеси по приемане и експедиция.

Идея за решаване на проблема

Възникна идея: остатъците от партидите с най-близки дати да бъдат обединени в една единствена партида и тези остатъци с унифицирана партида да бъдат компактно разположени в една клетка или в няколко, ако мястото в една не е достатъчно за настаняване на цялото количество остатъци. Пример за такова "стискание" е изобразен на рисунка 2.

Рис.2. Схема на стъкване на остатъци в клетките

Това позволява значително да се намалят складовите площи, които ще се използват за новия разположен продукт. В ситуация на претоварване на складовите мощности, такава мярка е крайно необходима, в противен случай свободното място за разполагане на нови стоки може просто да не е достатъчно, което ще доведе до спиране на складовите процеси по разполагане и захранване и, като следствие, до спиране на приемането и изпращането. Преди внедряването на WMS системата, такава операция се изпълняваше ръчно, което не беше ефективно, тъй като процесът на търсене на подходящи остатъци в клетките беше доста дълъг. Сега, с внедряването на WMS системата, решихме да автоматизираме, ускори и да направим процеса интуитивен.

Процесът на решаване на такава задача се дели на 2 етапа:

• на първия етап намираме близки по дата групи от партии за компресия (тази задача е посветена на предишната статия);
• на втория етап изчисляваме максимално компактно разположение на остатъците от продукта в клетките за всяка група партии.

В текущата статия ще се фокусираме на втория етап от алгоритъма.

Преглед на съществуващите решения

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

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

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

Функционалността за компресиране на остатъците от стоките в клетките е заявена и в много чуждестранни WMS-системи, но за съжаление, нямаме нито реални отзиви за ефективността на работа на алгоритмите (това е търговска тайна), нито пък представа за дълбочината на логиката им (проприетарен софтуер с затворен код), затова не можем да съдим.

Търсене на математически модел на задачата

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

Има множество клетки , в които се намират остатъци от стока. Накрая ще наричаме тези клетки клетки-донори. Да обозначим обема на стоката, която се намира в клетката $.

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

Има множество клетки , в които могат потенциално да бъдат поместени остатъци от клетките-донори. Такива клетки ще наричаме по-нататък клетки-контейнери. Това могат да бъдат както свободни клетки в склада, така и клетки-донори от множество . Винаги множеството е подмножество на .

За всяка клетка от множеството са зададени ограничения за вместимост. , измервани в дм3. Един дм3 представлява кубче с ръб по 10 см. Подобрената стока на склада е достатъчно голяма, поради което в този случай такава дискретизация е напълно достатъчна.

Задана матрица на най-кратките разстояния в метри между всяка двойка клетки , където и принадлежат на множества и съответно.

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

Да обозначим чрез променлива, приемаща стойност 1, ако остатъците от клетка се преместват в контейнер , и 0 в противен случай. Да обозначим чрез променлива, приемаща стойност 1, ако контейнерът съдържа остатъци от стоката, и 0 в противен случай.

Задачата е формулирана така: необходимо е да намерим такова множество контейнери и по такъв начин да „прикрепим“ клетките-донори към контейнерите, за да минимизираме функцията

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

В хода на решаването на задачата се стремим:

• първо, да спестим складови мощности;
• второ, да спестим времето на складовите работници.

Последното ограничение означава, че не можем да преместим стоки в контейнер, който не сме избрали, поради което не „носихме разходи“ за него. Също така, това ограничение означава, че обемът на преместваните стоки от клетките в контейнера не трябва да надвишава капацитета на контейнера. Под решението на задачата разбираме множеството контейнери и начините за прикрепване на клетките-донори към контейнерите.

Такава формулировка на задачата по оптимизация не е нова и е изследвана от много математици още от началото на 80-те години на миналия век. В чуждестранната литература има две задачи по оптимизация с подходяща математическа модел: Проблем на разположението на капацитирани съоръжения с един източник и Проблем на разположението на капацитирани съоръжения с множество източници (за различия в задачите ще говорим по-късно). Струва си да се спомене, че в математическата литература формулировките на тези две задачи за оптимизация се изразяват в термини на разполагане на предприятия в терен, откъдето произлиза и името „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

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

Ако прехвърлим към терминологията на нашата задача за оптимално опаковане на стоки в клетки, то:

• градовете-клиенти – това са клетки-донори с остатъците от стоките,
• градовете-производители – клетки-контейнери , в които се предполага да се поставят остатъците от други клетки,
• транспортните разходи – разходите за време на складовия работник за пренасяне на обема на стоките от клетка-донор в клетка-контейнер ;
• разходите за откриване на предприятието – разходите за избор на контейнер , равни на обема на клетка-контейнера , умножено по определен коефициент на икономия на свободните обеми (стойността на коефициента винаги > 1) (вижте раздела подготовка на входните данни).

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

Следва да се отбележи, че на практика и двете формулировки на задачата съществуват. По-долу ще представим всички „за“ и „против“ за всяка такава формулировка:

Таблица 1. Плюсове и минуси на вариантите Един източник и Мулти-източник.

Тъй като количеството плюсове на варианта Един източник е повече, а също така с оглед на факта, че колкото по-малко са остатъците в отсеките-донори, толкова по-малка е разликата в степента на компактност на сжатието, изчислено по двата варианта на задачата, нашият избор падна на варианта Един източник.

Струва си да се каже, че решението на варианта Мулти-източник също има своето място. Съществува голямо количество ефективни алгоритми за решаването му, повечето от които се свеждат до решаването на редица транспортни задачи. Има не само ефективни алгоритми, но и елегантни, например, тук.

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

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

Първо ще разгледаме изчислението разходи за преместване на стоки от клетката-дарител към клетката-контейнер. Първо трябва да определим в какви единици ще изчисляваме разходите за преместване. Двата най-очевидни варианта са метри и секунди. В „чисти“ метри изчисляването на разходите за преместване е безсмислено. Нека да покажем това с пример. Нека клетката да се намира на първия етаж, клетката да е на 30 метра разстояние и да се намира на втория етаж:

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

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

Нека от клетка да се премества бр. стока в контейнер . Нека да е средната скорост на движение на работника в склада, измервана в м/сек. Нека и да са средните скорости за еднократно изпълнение на операциите вземане и слагане за съответния обем на стоката от 4 дм3 (средният обем, който взима за 1 път служителят в склада при изпълнение на операциите). Нека и да е височината на клетките, от които се извършват операциите вземане и слагане. Например, средната височина на първия етаж (под) е 1 м, вторият етаж 2 м и т.н. Тогава формулата за изчисление на общото време за изпълнение на операцията по преместване е следната:

В таблица 2 е представена статистика на времето за изпълнение на всяка елементарна операция, събрана от служителите на склада с оглед спецификата на съхраняваните стоки.

Наименование на операцията	Ознака	Средно значение
Средна скорост на движение на работника в склада		1,5 м/сек
Средна скорост на изпълнение на една операция слагане (за обем на стоката 4 дм3)		2,4 сек

Таблица 2. Средно време за изпълнение на складски операции

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

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

Рис. 4. Варианти за преместване на остатъци в контейнери с различна вместимост.

На рис. 4 в червен цвят е изобразен обемът на остатъците, който вече не се побира в контейнера на втория етап на разполагане на последващите стоки.

Следните изисквания към изчисляемите решения на задачата ще помогнат да свържем кубическите метри разходи за избор на контейнер със секундите разходи за преместване:

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

Нека започнем с последното изискване. За да конкретизираме многозначното слово «баланс», проведохме анкета сред служителите на склада с цел да установим следното. Нека имаме клетка-контейнер с обем , в която е предвидено преместването на остатъците от стоките от клетките-дарители и общото време за такова преместване е равно . Нека има още няколко алтернативни варианта за разполагане на същото количество стоки от същите донорски клетки в други контейнери, където всяко разполагане има свои оценки. , където < и , където >.

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

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

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

На изображението по-долу ще разгледаме следните начини за разполагане на стоките в контейнери.

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

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

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

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

Но от друга страна, в такъв вариант (c) не само че намаляваме общо заетия обем, но също така намаляваме и количеството заети клетки, което е първото от двете важни изисквания за изчисляемите решения на задачите, изброени по-горе. Очевидно, за да започне да се изпълнява това изискване, в лявата част на неравенството трябва да добавим известна положителна константа. , като тази константа трябва да се добавя само тогава, когато количеството контейнери намалява. Напомняме, че — това е променлива, която е равна на 1, когато контейнерът е избран и 0, когато контейнерът. не е избрано. Нека обозначим, – множество контейнери в оригиналното решение и – множество контейнери в новото решение. В общ вид новото неравенство ще изглежда така:

Преобразувайки неравенството по-горе, получаваме

От това имаме формула за изчисляване на общата стойност на някакъв вариант на решаване на задачата:

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

Нека – максималното разстояние между клетките на склада в една зона ABC, равно в нашия случай на 100 м. Нека – максималният обем на клетка-контейнер в склада, равен в нашия случай на 1000 дм3.

Първият начин за изчисляване на величината . Нека разгледаме ситуацията, когато има 2 контейнера на първия етаж, в които вече физически се намира стока, тоест те самите са клетки-донори, а разходите за преместване на стоката в същите клетки, естествено е равно на 0. Необходимо е да се намери такова значение на константата , при което би било изгодно винаги да се преместят остатъците от контейнер 1 в контейнер 2. Подставяйки стойности и в неравенството, приведено по-горе, получаваме:

от което следва

Подставяйки стойности на средното време за изпълнение на елементарните операции в формулата по-горе получаваме

Вторият начин за изчисляване на величината . Нека разгледаме ситуацията, когато има клетки-донори, от които се планира да се премества стока в контейнер 1. Нека обозначим – разстоянието от клетка-донор до контейнер 1. Има също контейнер 2, в който вече има стоки и обемът му позволява да побере остатъците от всички клетки. За простота, нека предположим, че обемът на стоката, преместена от клетките-донори в контейнерите, е еднакъв и равен на . Необходимо е да се намери такова значение на константата , при което разполагането на всички остатъци от клетките в контейнер 2 би било винаги по-изгодно, отколкото разполагането им в различни контейнери:

Преобразувайки неравенството получаваме

За да «усилим» значението на величината , приемаме, че = 0. Средното количество клетки, участващи обикновено в процедурата за компресиране на остатъците в склада, е равно на 10. Подставяйки известните стойности на величините, имаме следното значение на константата

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

Сега, след всички титанични усилия по преобразуването на входните данни, можем да кажем, че всички входни данни са обработени в необходимия формат и са готови за използване в алгоритъма за оптимизация.

Заключение

Както показва практиката, трудността и важността на етапа на подготовка и преобразуване на входните данни за алгоритъма често се подценяват. В тази статия посветихме много внимание на този етап, за да покажем, че само качествено и разумно подготвените входни данни могат да направят решенията, изчислявани от алгоритъма, наистина ценни за клиента. Да, имаше много формули, но ви предупредихме преди ката 🙂

В следващата статия най-накрая ще стигнем до това, за което сме говорили в предходните две публикации – алгоритъма за дискретна оптимизация.

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

Източник: habr.com