У артыкуле расказваецца як пры ўкараненні WMS-сістэмы мы сутыкнуліся з неабходнасцю рашэння нестандартнай задачы кластарызацыі і якімі алгарытмамі мы яе вырашалі. Раскажам, як мы прымянялі сістэмны, навуковы падыход да вырашэння праблемы, з якімі цяжкасцямі сутыкнуліся і якія ўрокі вынеслі.
Гэтая публікацыя пачынае цыкл артыкулаў, у якіх мы дзелімся сваім паспяховым досведам укаранення алгарытмаў аптымізацыі ў складскія працэсы. Мэтай цыкла артыкулаў ставіцца пазнаёміць аўдыторыю з відамі задач аптымізацыі складскіх аперацый, якія ўзнікаюць практычна на любым сярэднім і буйным складзе, а таксама расказаць пра наш вопыт вырашэння такіх задач і сустракаемыя на гэтым шляху падводныя камяні. Артыкулы будуць карысныя тым, хто працуе ў галіне складской лагістыкі, укараняе WMS-сістэмы, а таксама праграмістам, якія цікавяцца праграмамі матэматыкі ў бізнэсе і аптымізацыяй працэсаў на прадпрыемстве.
Вузкае месца ў працэсах
У 2018 годзе мы зрабілі праект па ўкараненні WMS-сістэмы на складзе кампаніі «Гандлёвы дом «ЛД» у г. Чэлябінску. Укаранілі прадукт "1С-Лагістыка: Упраўленне складам 3" на 20 працоўных месцаў: аператары WMS, кладаўшчыкі, вадзіцелі пагрузчыкаў. Склад сярэдні каля 4 тыс. м2, колькасць ячэек 5000 і колькасць SKU 4500. На складзе захоўваюцца шаравыя краны ўласнай вытворчасці розных памераў ад 1 кг да 400 кг. Запасы на складзе захоўваюцца ў разрэзе партый, бо ёсць неабходнасць адбору тавара па FIFO.
Пры праектаванні схем аўтаматызацыі складскіх працэсаў мы сутыкнуліся з існуючай праблемай неаптымальнага захоўвання запасаў. Спецыфіка захоўвання і кладкі кранаў такая, што ў адным вочку адзінкавага захоўвання можа знаходзіцца толькі наменклатура адной партыі. Прадукцыя прыходзіць на склад штодня і кожны прыход - гэта асобная партыя. Разам, у выніку 1 месяца працы склада ствараюцца 30 асобных партый, прытым, што кожная павінна захоўваецца ў асобным вочку. Тавар часцяком адбіраецца не цэлымі палетамі, а штукамі, і ў выніку ў зоне адзінкавага адбору ў шматлікіх вочках назіраецца такая карціна: у вочку аб'ёмам больш 1м3 ляжыць некалькі штук кранаў, якія займаюць меней 5-10% ад аб'ёму вочка.
Мал 1. Фота некалькіх штук тавару ў вочку
У наяўнасці неаптымальнае выкарыстанне складскіх магутнасцяў. Каб прадставіць маштаб бедства магу прывесці лічбы: у сярэднім такіх ячэек аб'ёмам больш за 1м3 з "мізэрнымі" рэшткамі ў розныя перыяды працы склада налічваецца ад 100 да 300 ячэек. Бо склад адносна невялікі, то ў сезоны загрузкі склада гэты фактар становіцца "вузкім горлышком" з моцна тармозіць складскія працэсы.
Ідэя вырашэння праблемы
Узнікла ідэя: партыі рэшткаў з найбольш блізкімі датамі прыводзіць да адной адзінай партыі і такія рэшткі з уніфікаванай партыяй размяшчаць кампактна разам у адным вочку, або ў некалькіх, калі месца ў адной не будзе хапаць на размяшчэнне ўсёй колькасці рэшткаў.
Мал.2. Схема сціску рэштак у ячэйках
Гэта дазваляе значна скараціць займаныя складскія плошчы, якія будуць выкарыстоўвацца пад новы тавар. У сітуацыі з перагрузкай складскіх магутнасцяў такая мера з'яўляецца вельмі неабходнай, у адваротным выпадку вольнага месца пад размяшчэнне новага тавару можа папросту не хапіць, што прывядзе да стопар складскіх працэсаў размяшчэння і падсілкоўвання. Раней да ўкаранення WMS-сістэмы такую аперацыю выконвалі ўручную, што было не эфектыўна, бо працэс пошуку падыходных рэштак у вочках быў досыць доўгім. Цяпер з укараненнем WMS-сістэмы вырашылі працэс аўтаматызаваць, паскорыць і зрабіць яго інтэлектуальным.
Працэс рашэння такой задачы разбіваецца на 2 этапы:
- на першым этапе мы знаходзім блізкія па даце групы партый для сціску;
- на другім этапе мы для кожнай групы партый вылічаем максімальна кампактнае размяшчэнне рэшткаў тавара ў ячэйках.
У бягучым артыкуле мы спынімся на першым этапе алгарытму, а асвятленне другога этапа пакінем для наступнага артыкула.
Пошук матэматычнай мадэлі задачы
Перад тым як садзіцца пісаць код і вынаходзіць свой ровар, мы вырашылі падысці да такой задачы навукова, а менавіта: сфармуляваць яе матэматычна, звесці да вядомай задачы дыскрэтнай аптымізацыі і выкарыстоўваць эфектыўныя існуючыя алгарытмы для яе рашэння або ўзяць гэтыя існуючыя алгарытмы за аснову і мадыфікаваць іх пад спецыфіку развязальнай практычнай задачы.
Так як з бізнес-пастаноўкі задачы відавочна вынікае, што мы маем справу з мноствамі, то сфармулюем такую задачу ў тэрмінах тэорыі мностваў.
Хай - мноства ўсіх партый рэшткаў некаторага тавару на складзе. Няхай - зададзеная канстанта дзён. Няхай - падмноства партый, дзе розніца дат для ўсіх пар партый падмноства не пераўзыходзіць канстанты . Патрабуецца знайсці мінімальную колькасць неперасякальных падмноства , такое што ўсе падмноствы у сукупнасці давалі б мноства .
Іншымі словамі, нам трэба знайсці групы ці кластары падобных партый, дзе крытэр падабенства вызначаецца канстантай . Такая задача нагадвае нам добра вядомую ўсім задачу кластарызацыі. Важна сказаць, што разгляданая задача адрозніваецца ад задачы кластарызацыі, тым што ў нашай задачы ёсць цвёрда зададзеная ўмова па крытэры падабенства элементаў кластара, вызначанае канстантай , а ў задачы кластарызацыі такая ўмова адсутнічае. Пастаноўку задачы кластарызацыі і інфармацыю па гэтай задачы можна знайсці
Такім чынам, нам удалося сфармуляваць задачу і знайсці класічную задачу са падобнай пастаноўкай. Цяпер неабходна разгледзець агульнавядомыя алгарытмы для яе вырашэння, каб не вынаходзіць веласіпед нанава, а ўзяць лепшыя практыкі і прымяніць іх. Для рашэння задач кластарызацыі мы разглядалі самыя папулярныя алгарытмы, а менавіта: -means, -means, алгарытм вылучэння сувязных кампанент, алгарытм мінімальнага драбнага дрэва. Апісанне і разбор такіх алгарытмаў можна знайсці
Для рашэння нашай задачы алгарытмы кластарызацыі -means і -means не дастасавальныя зусім, бо загадзя ніколі не вядома колькасць кластараў і такія алгарытмы не ўлічваюць абмежаванне канстанты дзён. Такія алгарытмы былі першапачаткова адкінуты з разгляду.
Для рашэння нашай задачы алгарытм вылучэння сувязных кампанент і алгарытм мінімальнага драбавога падыходзяць больш, але, як апынулася, іх нельга ўжыць «у ілоб» да развязальнай задачы і атрымаць добрае рашэнне. Каб растлумачыць гэта, разгледзім логіку працы такіх алгарытмаў у дачыненні да нашай задачы.
Разгледзім граф , у якім вяршыні - гэта мноства партый , а рабро паміж вяршынямі и мае вагу роўную розніцы дзён паміж партыямі. и . У алгарытме вылучэння сувязных кампанент задаецца ўваходны параметр , Дзе , і ў графе выдаляюцца ўсе рэбры, для якіх вага больш . Злучанымі застаюцца толькі найболей блізкія пары аб'ектаў. Сэнс алгарытму складаецца ў тым, каб падабраць такое значэнне. , пры якім граф «разваліцца» на некалькі сувязных кампанентаў, дзе партыі, якія належаць гэтым кампанентам, будуць задавальняць нашаму крытэру падабенства, які вызначаецца канстантай . Атрыманыя кампаненты і ёсць кластары.
Алгарытм мінімальнага якое пакрывае дрэва спачатку будуе на графе мінімальнае якое пакрывае дрэва, а затым паслядоўна выдаляе рэбры з найвялікай вагай датуль, пакуль граф не "разваліцца" на некалькі сувязных кампанент, дзе партыі, прыналежныя гэтым кампанентам, будуць таксама задавальняць нашаму крытэру падабенства. Атрыманыя кампаненты і будуць кластарамі.
Пры выкарыстанні такіх алгарытмаў для рашэння разгляданай задачы можа ўзнікнуць сітуацыя як на малюнку 3.
Рыс 3. Ужыванне алгарытмаў кластарызацыі да развязальнай задачы
Дапусцім у нас канстанта розніцы дзён партый роўная 20 дзён. Граф быў намаляваны ў прасторавым выглядзе для зручнасці візуальнага ўспрымання. Абодва алгарытму далі рашэнне з трыма кластарамі, якое можна лёгка палепшыць, аб'яднаўшы партыі, змешчаныя ў асобныя кластары, паміж сабой! Відавочна, што такія алгарытмы неабходна дапрацоўваць пад спецыфіку развязальнай задачы і іх ужыванне ў чыстым выглядзе да рашэння нашай задачы будзе даваць дрэнныя вынікі.
Такім чынам, перш чым пачынаць пісаць код мадыфікаваных пад нашу задачу графавых алгарытмаў і вынаходзіць свой ровар (у сілуэтах якога ўжо адгадваліся абрысы квадратных колаў), мы, ізноў жа, вырашылі падысці да такой задачы навукова, а менавіта: паспрабаваць звесці яе да іншай задачы дыскрэтнай аптымізацыі, у надзеі на тое, што існуючыя алгарытмы для яе вырашэння можна будзе прымяніць без мадыфікацый.
Чарговы пошук падобнай класічнай задачы ўвянчаўся поспехам! Удалося знайсці задачу дыскрэтнай аптымізацыі, пастаноўка якой 1 у 1 супадае з пастаноўкай нашай задачы. Гэтай задачай аказалася задача аб пакрыцці мноства. Прывядзем пастаноўку задачы ў дачыненні да нашай спецыфікі.
Маецца канчатковае мноства і сямейства усіх яго неперасякальных падмностваў партый, такіх што розніца дат для ўсіх пар партый кожнага падмноства з сямейства не пераўзыходзіць канстанты . Пакрыццём называюць сямейства найменшай магутнасці, элементы якога належаць , такое што аб'яднанне мностваў з сямейства павінна даваць мноства ўсіх партый .
Падрабязны разбор гэтай задачы можна знайсці и Іншыя варыянты практычнага прымянення задачы аб пакрыцці і яе мадыфікацый можна знайсці
Алгарытм рашэння задачы
З матэматычнай мадэллю вырашаемай задачы вызначыліся. Цяпер прыступім да разгляду алгарытму для яе рашэння. Падмноствы з сямейства можна лёгка знайсці наступнай працэдурай.
- Упарадкаваць партыі з мноства у парадку змяншэння іх дат.
- Знайсці мінімальную і максімальную даты партый.
- Для кожнага дня ад мінімальнай даты да максімальнай знайсці ўсе партыі, даты якіх адрозніваюцца ад не больш чым на (таму значэнне лепш браць цотнае).
Логіка працы працэдуры фармавання сямейства мностваў пры дзён паказана на рысунку 4.
Мал.4. Фарміраванне падмноства партый
У такой працэдуры неабавязкова для кожнага перабіраць усе іншыя партыі і правяраць рознасць іх дат, а можна ад бягучага значэння рухацца налева або права да таго часу, пакуль не знайшлі партыю, дата якой адрозніваецца ад больш за на палавіннае значэнне канстанты. Усе наступныя элементы пры руху як направа, так і налева будуць нам не цікавыя, бо для іх адрозненне ў днях будзе толькі павялічвацца, паколькі элементы ў масіве былі першапачаткова спарадкаваны. Такі падыход будзе істотна эканоміць час, калі колькасць партый і роскід іх дат значна большыя.
Задача аб пакрыцці мноства з'яўляецца -цяжкай, а значыць для яе рашэння не існуе хуткага (з часам працы роўнаму паліному ад уваходных дадзеных) і дакладнага алгарытму. Таму для рашэння задачы аб пакрыцці мноства быў абраны хуткі прагны алгарытм, які вядома не з'яўляецца дакладным, але валодае наступнымі добрымі якасцямі:
- Для задач невялікай памернасці (а гэта як раз наш выпадак) вылічае рашэнні дастаткова блізкія да оптымуму. З ростам памеру задачы якасць рашэння пагаршаецца, але ўсё ж даволі павольна;
- Вельмі просты ў рэалізацыі;
- Хуткі, бо ацэнка яго часу працы роўная .
Прагны алгарытм выбірае мноства кіруючыся наступным правілам: на кожным этапе выбіраецца мноства, якое пакрывае максімальную колькасць яшчэ не пакрытых элементаў. Падрабязнае апісанне алгарытму і яго псеўдакод можна знайсці
Параўнанне дакладнасці такога прагнага алгарытму на тэставых дадзеных развязальнай задачы з іншымі вядомымі алгарытмамі, такімі як імавернасны прагны алгарытм, алгарытм мурашынай калоніі і г.д., не выраблялася. Вынікі параўнання такіх алгарытмаў на згенераваных выпадковых дадзеных можна знайсці
Рэалізацыя і ўкараненне алгарытму
Такі алгарытм быў рэалізаваны на мове 1С і быў уключаны ў знешнюю апрацоўку пад назвай «Сціск рэшткаў», якая была падключана да WMS-сістэме. Мы не сталі рэалізоўваць алгарытм на мове З ++ і выкарыстоўваць яго з знешняй Native кампаненты, што было б правільней, так як хуткасць працы кода на C + + у разы і на некаторых прыкладах нават у дзясяткі разоў пераўзыходзіць хуткасць працы аналагічнага кода на 1С. На мове 1С алгарытм быў рэалізаваны для эканоміі часу на распрацоўку і прастаты адладкі на працоўнай базе заказчыка. Рэзультат работы алгарытму паказаны на рысунку 5.
Мал.5. Апрацоўка па «сціску» рэштак
На малюнку 5 відаць, што на паказаным складзе бягучыя рэшткі тавараў у вочках захоўвання разбіліся на кластары, усярэдзіне якіх даты партый тавараў адрозніваюцца паміж сабой не больш за на 30 дзён. Бо замоўца вырабляе і захоўвае на складзе металічныя шаравыя краны, у якіх тэрмін прыдатнасці вылічаецца гадамі, то такой розніцай дат можна занядбаць. Адзначым, што ў цяперашні час такая апрацоўка выкарыстоўваецца ў прадакшэне сістэматычна, і аператары. WMS пацвярджаюць добрую якасць кластарызацыі партый.
Высновы і працяг
Галоўны досвед, які мы атрымалі ад рашэння такой практычнай задачы - гэта пацверджанне эфектыўнасці выкарыстання парадыгмы: мацюк. фармулёўка задачы вядомая мацюк. мадэль вядомы алгарытм алгарытм з улікам спецыфікі задачы. Дыскрэтнай аптымізацыі ўжо налічваецца больш за 300 гадоў і за гэты час людзі паспелі разгледзець вельмі шмат задач і назапасіць вялікі вопыт па іх вырашэнні. У першую чаргу мэтазгодней звярнуцца да гэтага досведу, а ўжо потым пачынаць вынаходзіць свой ровар.
У наступным артыкуле мы працягнем аповяд пра алгарытмы аптымізацыі і разгледзім самае цікавае і значна больш складанае: алгарытм аптымальнага «сціску» рэштак у ячэйках, які выкарыстоўвае на ўваходзе дадзеныя, атрыманыя ад алгарытму кластарызацыі партый.
Артыкул падрыхтаваў
Раман Шангін, праграміст дэпартамента праектаў,
кампанія Першы БІТ, г. Чэлябінск
Крыніца: habr.com