Matematika diskrete për WMS: algoritmi i kompresimit të produkteve në qeliza (pjesa 1)

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

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

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

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

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

Në artikulli i mëparshëm описывается специфика склада, на котором нами была внедрена 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 этапа:

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

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

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

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

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

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

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

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

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

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

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

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

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

Задана матрица кратчайших расстояний в метрах между каждой парой ячеек , ku dhe принадлежат множествам dhe përkatësisht.

Обозначим «затраты» на перемещения товара из ячейки в ячейку . Обозначим «затраты» на выбор контейнера для перемещения в него остатков из других ячеек. Как именно и в каких единицах измерения будут вычисляться значения dhe do të shqyrtojmë më tej (shih seksionin përgatitja e të dhënave hyrëse), tani mjafton të thuhet se këto vlera do të jenë përmbledhëse me vlerat dhe përkatësisht.

Shenjësojmë përmes një variabël që merr vlerën 1, nëse mbetjet nga qelia ësht ne të lëvizura në kontenier , dhe 0 përndryshe. Shenjësojmë përmes një variabël që merr vlerën 1, nëse kontenieri përmban mbetjet e mallrave, dhe 0 përndryshe.

Detyra formullohet kështu: është e nevojshme të gjendet një shumës kontenierash dhe në këtë mënyrë ‘të lidhim’ qelitë-dhuruese me qelitë kontenier, në mënyrë që të minimizojmë funksionin

në kufizimet

Pra, gjatë llogaritjes së zgjidhjes së detyrës ne përpiqemi:

• së pari, të kursejmë kapacitetin e magazinave;
• së dyti, të kursejmë kohën e magazinierëve.

Kufizimi i fundit do të thotë se nuk mund të lëvizim mallrat në një kontenier që nuk e kemi zgjedhur, dhe për rrjedhojë nuk kemi ‘patur shpenzime’ për zgjedhjen e tij. Po ashtu, ky kufizim do të thotë se vëllimi i mallrave të lëvizura nga qelitë në kontenier nuk duhet të tejkalojë kapacitetin e kontenierit. Nga zgjidhja e detyrës, do të kuptojmë shumën e kontenierëve dhe mënyrat e lidhjes së qelive-dhuruese me kontenierët.

Një formulim i tillë i detyrës së optimizimit nuk është i ri dhe është studiuar nga shumë matematiciene që nga fillimi i viteve '80 të shekullit të kaluar. Në literaturën e huaj ekzistojnë 2 detyra optimizimi me një model matematikor të përshtatshëm: Single-Source Capacitated Facility Location Problem dhe Multi-Source Capacitated Facility Location Problem (për dallimet e detyrave do të flasim më vonë). Duhet thënë se në literaturën matematike formulimet e këtyre dy detyrave të optimizimit janë përshkruar në terma të vendosjes së ndërmarrjeve në territor, prej nga dhe emri ‘Facility Location’. Kryesisht kjo është një trashëgimi tradicionale, sepse nevoja për zgjidhjen e këtyre detyrave kombinatorial ka ardhur nga fusha e logjistikës, kryesisht, sektori industrial ushtarak në vitet '50 të shekullit të kaluar. Në terma të vendosjes së ndërmarrjeve, këto detyra formulohen kështu:

• Ekziston një shumicë e fundme qytetesh, ku potencialisht mund të vendosen ndërmarrje prodhimi (më pas qytetet-prodhues). Për secilin qytet-prodhues janë përcaktuar kostot për hapjen e një ndërmarrjeje atje, si dhe kufizimet e kapaciteteve prodhuese të ndërmarrjes së hapur.
• Ekziston një shumicë e fundme qytetesh, ku faktikisht ndodhen klientët (më pas qytetet-klient). Për secilin qytet-klient të tillë, është përcaktuar një vëllim kërkese për produktin. Për thjeshtësi, të supozojmë se produkti që prodhojnë ndërmarrjet dhe konsumojnë klientët është një.
• Për secilën palë qytet-prodhues dhe qytet-klient është përcaktuar një sasi e kostove të transportit për të dërguar vëllimin e kërkuar të produktit nga prodhuesi te klienti.

Duhet të gjendet se në cilat qytete të hapen ndërmarrjet dhe si të lidhën klientët me këto ndërmarrje, në mënyrë që:

• Kostot totale të hapjeve të ndërmarrjeve dhe kostot e transportit të jenë minimale;
• Vëllimi i kërkesës së klientëve, të lidhur me ndonjë ndërmarrje të hapur, të mos e kalojë kapacitetin prodhues të kësaj ndërmarrjeje.

Tani vlen të thuhet për dallimin e vetëm midis këtyre dy detyrave klasike:

• Single-Source Capacitated Facility Location Problem – klienti furnizohet vetëm nga një ndërmarrje të hapur;
• Multi-Source Capacitated Facility Location Problem – klienti mund të furnizohet nga disa ndërmarrje të hapura njëherazi.

Ky dallim midis detyrave, në shikim të parë, duket i parëndësishëm, por në të vërtetë, çon në një strukturë kombinatoriale krejtësisht të ndryshme të këtyre detyrave dhe, si pasojë, në algoritme krejtësisht të ndryshme për zgjidhjen e tyre. Dallimi midis detyrave është demonstruar në figurën më poshtë.

Fig.3. a) Multi-Source Capacitated Facility Location Problem

Fig.3. b) Single-Source Capacitated Facility Location Problem

Të dy detyrat janë të vështira, që do të thotë se nuk ekziston një algoritëm i saktë, i cili për një kohë polinomiale të madhësisë së të dhënave hyrëse do të zgjidhte një detyrë të tillë. Thënë ndryshe, të gjitha algoritmet e sakta për zgjidhjen e detyrës do të punojnë për një kohë eksponenciale, megjithatë, ndoshta më shpejt se provimi i plotë i mundësive. Siç janë të vështira, ne do të shqyrtojmë vetëm heuristika afër, që do të thotë algoritme që do të llogaritin zgjidhje të qëndrueshme shumë afër optimalëve dhe do të funksionojnë mjaft shpejt. Nëse ka interes për këto detyra, këtu mund të gjeni një përmbledhje të mirë në rusisht. Nëse e shikojmë në terminologjinë e detyrës sonë për optimizimin e mbushjes së mallrave në qelia, atëherë:

qytetet-klient janë qelitë-dhuruese

• me mbetje mallrash, qytetet-prodhues janë qelitë-kontenierë
• города-производители – ячейки-контейнеры , në të cilat parashihet të vendosen mbetjet nga qeliza të tjera,
• kostot e transportit – kohëzgjatja e kostove të magjistarit për lëvizjet e volumit të mallrave nga qeliza burimore në qelizën-container ;
• kostot e hapjes së biznesit – kostot e zgjedhjes së qelizës-container , të barabarta me volumet e qelizës-container , të shumëzuara me një koeficient të caktuar të kursimeve të hapësirave të lira (vlera e koeficientit gjithmonë > 1) (shih seksionin përgatitja e të dhënave hyrëse).

Pasi të jetë bërë analogjia me dërgesat klasike të njohura, duhet të përgjigjemi në një pyetje të rëndësishme, nga e cila varet zgjedhja e arkitekturës së algoritmit të zgjidhjes: është e mundur që mbetjet të zhvendosen nga qeliza burimore vetëm në një dhe vetëm një container (Single-Source), ose është e mundur zhvendosja e mbetjeve në disa qeliza-container (Multi-Source)?

Vlen të theksohet se në praktikë të dy qasjet e problemit kanë vend. Do të paraqesim të gjitha 'pro' dhe 'kundër' për secilën prej tyre më poshtë:

Tavola 1. Avantazhet dhe disavantazhet e opsioneve Single-Source dhe Multi-Source.

Duke qenë se numri i avantazheve për opsionin Single-Source është më i madh, si dhe duke marrë parasysh faktin se sa më pak të jetë sasia e mbetjeve në qelizat burimore, aq më e vogël është dallimi në shkallën e kompaktësisë së kompresionit të llogaritur sipas të dy opsioneve të problemit, zgjedhja jonë ra në opsionin Single-Source.

Vlen të thuhet se zgjidhja e opsionit Multi-Source gjithashtu ka një vend. Ekzistojnë shumë algoritma efektivë për zgjidhjen e saj, shumica e të cilëve përfshihen në zgjidhjen e një sërë problemesh të transportit. Ka gjithashtu algoritma jo vetëm efektivë, por edhe elegantë, për shembull, këtu.

Përgatitja e të dhënave hyrëse

Para se të fillojmë analizën dhe zhvillimin e algoritmit për zgjidhjen e problemit, është e nevojshme të përcaktojmë se cilat të dhëna dhe në çfarë forme do t'i dorëzojmë atij. Me volumet e mbetjeve të mallrave në qelizat burimore dhe kapacitetin e qelizave-container nuk ka probleme, sepse ato janë triviale – këto sasi do të matet në m3, por me kostot e përdorimit të qelizës-container dhe matricën e kostove për zhvendosjen nuk është aq e thjeshtë!

Fillimisht do të shqyrtojmë llogaritjen e kostove të zhvendosjes së mallrave nga qeliza burimore në qeliza-container. Së pari, duhet të përcaktojmë në cilat njësi matëse do të llogarisim kostot e zhvendosjes. Dy opsionet më të dukshme – janë metrat dhe sekondat. Në 'metra të pastër' nuk ka sens të llogariten kostot e zhvendosjes. Do ta tregojmë këtë me një shembull. Le të themi se qeliza ndodhet në katin e parë, qeliza është e largët 30 metra dhe ndodhet në katin e dytë:

• Zhvendosja nga në është më e shtrenjtë se zhvendosja nga në , sepse është më e lehtë të zgjatësh poshtë nga kati i dytë (1.5-2 metra nga toka) sesa të ngresh në të dytin, megjithëse distanca do të kalojë e njëjtë;
• Të zhvendosësh 1 copë mall nga qeliza në do të jetë më e lehtë se të zhvendosësh 10 copë të atij mallit, megjithëse distanca do të kalojë e njëjtë.

Shpenzimet për transferim duhet të merren parasysh në sekonda, pasi kjo mundëson marrjen parasysh të dallimeve në katet dhe sasinë e mallrave të transferuar. Për të vlejtur shpenzimet e transferimit në sekonda, duhet të ndarje operacionin e transferimit në komponentët elementarë dhe të realizohet matja e kohës për përfundimin e çdo komponenti elementar.

Le të thuhet se nga qeliza transferohet copëra mallrash në kontejner . Le të thuhet se është shpejtësia mesatare e lëvizjes së punëtorit në depo, e matur në m/se. Le të thuhet se dhe janë shpejtësitë mesatare për kryerjen një herë të operacioneve të marrjes dhe vendosjes, për një volum mallrash të barabartë me 4 dm3 (vëllimi mesatar që punonjësi e merr një herë gjatë operacioneve në depo). Le të thuhet se dhe lartësitë e qelizave nga të cilat kryhen operacionet e marrjes dhe vendosjes janë përkatësisht. Për shembull, lartësia mesatare e katit të parë (dhe) 1 m, katit të dytë 2 m etj. Atëherë formula për të llogaritur kohën totale të përfundimit të operacionit të transferimit është si në vijim:

Tabela 2 paraqet statistikën e kohrave të përfundimit për çdo operacion elementar, të mbledhur nga punonjësit e depos duke marrë parasysh specifikën e mallrave të ruajtur.

Emri i operacionit	Simboli	Vlera mesatare
Shpejtësia mesatare e lëvizjes së punëtorit në depo		1.5 m/se
Shpejtësia mesatare e kryerjes së një operacioni të vendosjes (për volum mallrash 4 dm3)		2.4 sek

Tabela 2. Koha mesatare e kryerjes së operacioneve në depo

Tani e kemi përcaktuar mënyrën e llogaritjes së shpenzimeve për transferim. Tani duhet të zbulojmë se si llogaritet shpenzimi për zgjedhjen e qelisë-konteiner.Këtu gjithçka është shumë, shumë më e komplikuar se me shpenzimet për transferim, sepse:

• së pari, shpenzimet duhet të jenë në varësi të drejtpërdrejtë nga volumi i qelisë - një volum i njëjtë i mbetjeve, të transferuara nga qelizat dhuruese, është më mirë të vendoset në një kontejner më të vogël sesa në një kontejner të madh, nëse ky volum plotësisht arrin për të dy konteinerët. Kështu, me minimizimin e shpenzimeve totale për zgjedhjen e konteinerëve, ne përpiqemi të kursejmë kapacitetet e depozitimit "të deficituara" në fushën e zonës së përzgjedhjes, për të kryer operacione të mëtejshme të vendosjes së mallrave në qeliza. Në figurën 4 ilustrohen variantet e transferimit të mbetjeve në konteinerë të mëdhenj dhe të vegjël dhe pasojat e këtyre varianteve të transferimit gjatë përfundimit të operacioneve të mëtejshme në depo.
• së dyti, pasi na duhet të minimizojmë përgjithësisht shpenzimet, duke përfshirë si shpenzimet për transferim ashtu edhe shpenzimet për zgjedhjen e konteinerëve, volumin e qelive në metra kub duhet të lidhet disi me sekondat, gjë që nuk është aspak e thjeshtë.

Fig. 4. Variantet e transferimit të mbetjeve në konteinerë me kapacitet të ndryshëm.

Në figurën 4, me ngjyrë të kuqe paraqitet volumi i mbetjeve, i cili nuk mund të përshtatet në kontejner në fazën e dytë të vendosjes së mallrave të mëtejshëm.

Do të ndihmojë lidhja e metrave kub të shpenzimeve për zgjedhjen e konteinerit me sekondat e shpenzimeve për transferim këto kërkesa për zgjidhjet e llogaritura:

• Duhet të sigurohet që mbetjet nga qeliza-dhuruese të transferohen në qeliza-konteiner në çdo rast, nëse kjo redukton numrin e përgjithshëm të qelizave-konteiner në të cilat ndodhet mallri.
• Duhet të ruhet balanci mes volumit të konteinerëve dhe shpenzimeve të kohës për transferim: për shembull, nëse në variantin e ri të zgjidhjes së problemit, krahasuar me variantin e mëparshëm, fitimi në volum është i madh, ndërsa humbja në shpenzimet e kohës është e vogël, atëherë duhet të zgjidhet varianti i ri.

Të fillojmë me kërkesën e fundit. Për të konkretizuar fjalën shumëkuptimëshe "balancë", ne zhvilluam një anketë tek punonjësit e depos për të zbuluar sa vijon. Le të supozojmë se ka një qeli-konteiner me volum , në të cilin është caktuar transferimi i mbetjeve nga qelizat dhuruese dhe koha totale e këtij transferimi është e barabartë me . Le të ketë disa variante alternative për vendosjen e të njëjtës sasi mallrash nga të njëjtat qeliza dhuruese në konteinerë të ndryshëm, ku çdo vendosje ka vlerësimet e saj. , ku < dhe , ku >.

Cila është pyetja: cili është përfitimi minimal në volum i pranueshëm, me një vlerë të caktuar të humbjes në kohë. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagrami i varshmërisë së kursimit minimal të volumin nga rritja e diferencës në kohën e përfundimit të operacionit.

Kështu, nëse shpenzimet shtesë të kohës janë 40 sekonda, ne jemi të gatshëm t’i shpenzojmë ato vetëm kur përfitimi në volum është të paktën 500 dm3. Pavarësisht nga fakti se në varshmëri ekziston një paksa jo-line, për thjeshtësinë e llogaritjeve të mëtejshme, do të supozojmë se varshmëria mes këtyre sasive është lineare dhe përshkruhet nga një barazim.

Në figurën më poshtë, ne do të shqyrtojmë mënyrat e ndryshme të vendosjes së produkteve në kontenierë.

Fig. 6. Varianti (a): 2 kontenierë, volumi total 400 dm3, koha totale 150 sekonda.

Fig. 6. Varianti (b): 2 kontenierë, volumi total 600 dm3, koha totale 190 sekonda.

Fig. 6. Varianti (c): 1 kontenier, volumi total 400 dm3, koha totale 200 sekonda.

Varianti (a) i zgjedhjes së kontenierëve është më i preferueshëm se varianti fillestar, pasi plotësohet pabarazia: (800-400)/10 >= 150-120 nga e cila ndjekim 40 >= 30. Varianti (b) është më pak i preferueshëm se varianti fillestar, pasi pabarazia nuk bëhet: (800-600)/10 >= 190-150 nga e cila ndjekim 20 >= 40. Por varianti (c) nuk përputhet me këtë logjikë! Le të shqyrtojmë këtë variant më në detaje. Nga ana e parë pabarazia (800-400)/10 >= 200-120, pra pabarazia 40 >= 80 nuk plotësohet, çka tregon se fitimi nga volumi nuk justifikon një humbje kaq të madhe në kohë.

Por nga ana tjetër, në këtë variant (c) ne jo vetëm që zvogëlojmë volumin e mbushur total, por gjithashtu ulim numrin e qelizave të zëna, që është kërkesa e parë nga dy kërkesat e rëndësishme për zgjidhjet e llogaritura të detyrave, të renditura më sipër. E qartë është se për të filluar ndaj këtij kërkese, duhet të shtojmë një konstante pozitive në anën e majtë të pabarazisë. , kështu që duhet të shtojmë një konstante të tillë vetëm kur numri i kontenierëve zvogëlohet. Kujtojmë se — është një variabël që është e barabartë me 1 kur kontenieri është zgjedhur, dhe 0 kur kontenieri nuk është zgjedhur. Le të shënojmë, – seti i kontenierëve në zgjidhjen fillestare dhe – seti i kontenierëve në zgjidhjen e re. Në formë të përgjithshme, pabarazia e re do të duket kështu:

Duke transformuar pabarazinë e lartpërmendur, ne marrim

Duke e pasur këtë, kemi formulën për llogaritjen e kostos totale e një varianti të caktuar të zgjidhjes së detyrës:

Por tani del pyetja: çfarë vlerë duhet të ketë kjo konstante ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Le të themi se – distanca maksimale midis qelizave të magazinës në një zonë ABC, e barabartë në rastin tonë me 100 m. Le të themi se – volumi maksimal i qelizës-kontenier në magazinë, i barabartë në rastin tonë me 1000 dm3.

Mënyra e parë për llogaritjen e madhësisë . Le të shqyrtojmë situatën, kur ka 2 kontenierë në katin e parë, në të cilët tashmë fizikisht ndodhet produkti, domethënë, ata vetë janë qeliza-dhënës, ndërsa shpenzimet për zhvendosjen e produktit në të njëjtat qeliza, natyrisht, janë të barabarta me 0. Duhet të gjejmë një vlerë të tillë konstante , për të cilën do të ishte e favorshme gjithmonë të zhvendosnim mbetjet nga konteneri 1 në kontenerin 2. Duke vendosur vlerat dhe në pabarazinë e lartpërmendur, ne marrim:

nga e cila ndjekim

Duke vendosur vlerat e kohës mesatare të ekzekutimit të operacioneve elementare në formulën e lartpërmendur, ne marrim

Mënyra e dytë për llogaritjen e madhësisë . Le të shqyrtojmë situatën, kur ka qeliza-dhënëse nga të cilat planifikohet të zhvendosen produktet në kontenerin 1. Le të shënojmë – distanca nga qeliza-dhënëse në kontenerin 1. Gjithashtu ka një kontenier 2, në të cilin tashmë ka produkte, dhe volumi i tij lejon të përmbajë mbetjet nga të gjitha qelizat. Për thjeshtësi, le të supozojmë se volumi i produktit, që po zhvendoset nga qelizat-dhënëse në kontenierë, është i njëjtë dhe i barabartë me . Duhet të gjejmë një vlerë të tillë konstante , për të cilën vendosja e të gjitha mbetjeve nga qelizat në kontenerin 2 do të ishte gjithmonë më e favorshme se sa vendosja e tyre në mënyra të ndryshme:

Duke transformuar pabarazinë, ne marrim

Për të "forcuar" vlerën e madhësisë , le të pranojmë se = 0. Numri mesatar i qelizave që zakonisht janë të angazhuara në procedurën e shkrirjes së mbetjeve në magazinë është 10. Duke vendosur vlerat e njohura, kemi vlerën e mëposhtme të konstantes

Marrim vlerën më të madhe, të llogaritur për secilin variant, kjo do të jetë dhe vlera e madhësisë për parametrat e caktuar të magazinës. Tani për përfundim, le të shkruajmë formulën për llogaritjen e kostove totale për një zgjidhje të pranueshme :

Tani, pas të gjitha përpjekjeve titanike për transformimin e të dhënave hyrëse, mund të themi se të gjitha të dhënat hyrëse janë transformuar në formën e nevojshme dhe janë gati për t'u përdorur në algoritmin e optimizimit.

Përfundimi

Siç tregojnë praktikat, ngarkesa punuese dhe rëndësia e fazës së përgatitjes dhe transformimit të të dhënave hyrëse për algoritmin shpesh nënvlerësohet. Në këtë artikull ne i kemi kushtuar shumë vëmendje këtij treguesi, për të treguar se vetëm të dhënat hyrëse të përgatitura mirë dhe me mend mund t'i bëjnë zgjidhjet, të llogaritura nga algoritmi, vërtet të vlefshme për klientin. Po, ka pasur shumë formulash përfundimtare, por ju kemi paralajmëruar edhe para kësaj 🙂

Në artikullin e ardhshëm, ne përfundimisht do të arrijmë në atë për të cilin ishin menduar 2 publikimet e mëparshme – algoritmin e optimizimit diskret.

Artikulli është përgatitur nga
Roman Shangin, programatori i departamentit të projekteve,
kompania e Parë Bit, qyteti Chelyabinsk

Burimi: habr.com