Maqolada qanday amalga oshirish kerakligi tasvirlangan WMS-tizim, biz nostandart klasterlash masalasini hal qilish zarurati bilan duch keldik va uni qanday algoritmlardan foydalanganmiz. Muammoni hal qilishda tizimli, ilmiy yondashuvni qanday qo'llaganimizni, qanday qiyinchiliklarga duch kelganimizni va qanday saboqlarni olganimizni aytib beramiz.
Ushbu nashr bir qator maqolalarni boshlaydi, unda biz ombor jarayonlarida optimallashtirish algoritmlarini amalga oshirish bo'yicha muvaffaqiyatli tajribamiz bilan o'rtoqlashamiz. Maqolalar turkumining maqsadi - auditoriyani deyarli har qanday o'rta va yirik omborlarda paydo bo'ladigan ombor operatsiyalarini optimallashtirish muammolari turlari bilan tanishtirish, shuningdek, bunday muammolarni hal qilish bo'yicha tajribamiz va yo'lda duch keladigan tuzoqlar haqida gapirib berishdir. . Maqolalar ombor logistika sanoatida ishlaydiganlar uchun foydali bo'ladi, amalga oshiradi WMS-tizimlar, shuningdek, biznesda matematikani qo'llash va korxonadagi jarayonlarni optimallashtirishga qiziqqan dasturchilar.
Jarayonlardagi to'siqlar
2018 yilda biz amalga oshirish uchun loyihani yakunladik WMS-Chelyabinskdagi "LD savdo uyi" kompaniyasining omboridagi tizimlar. Biz 1 ta ish joyi uchun "3C-Logistics: Omborni boshqarish 20" mahsulotini joriy qildik: operatorlar WMS, omborchilar, forklift haydovchilari. O'rtacha ombor taxminan 4 ming m2, kameralar soni 5000 va SKU soni 4500. Omborda 1 kg dan 400 kg gacha bo'lgan turli o'lchamdagi o'zimiz ishlab chiqargan sharli klapanlar saqlanadi. Ombordagi inventar partiyalarda saqlanadi, chunki FIFO bo'yicha tovarlarni tanlash zarurati mavjud.
Ombor jarayonlarini avtomatlashtirish sxemalarini loyihalashda biz inventarizatsiyani maqbul bo'lmagan saqlash muammosiga duch keldik. Kranlarni saqlash va joylashtirishning o'ziga xos xususiyatlari shundan iboratki, bitta saqlash kamerasi faqat bitta partiyadan narsalarni o'z ichiga olishi mumkin. Mahsulotlar har kuni omborga keladi va har bir kelishi alohida partiya hisoblanadi. Hammasi bo'lib, omborning 1 oylik ishlashi natijasida har biri alohida kamerada saqlanishi kerakligiga qaramay, 30 ta alohida partiyalar yaratiladi. Mahsulotlar ko'pincha butun palletlarda emas, balki bo'laklarda tanlanadi va natijada ko'plab hujayralardagi parcha tanlash zonasida quyidagi rasm kuzatiladi: hajmi 1 m3 dan ortiq bo'lgan hujayrada bir nechta kran bo'laklari mavjud. hujayra hajmining 5-10% dan kamini egallaydi.
1-rasm. Hujayradagi bir nechta tovarlarning fotosurati
Saqlash hajmidan optimal foydalanilmayotgani aniq. Falokat ko'lamini tasavvur qilish uchun men raqamlarni keltira olaman: o'rtacha hisobda ombor faoliyatining turli davrlarida "mayda" balanslari bilan 1 m3 dan ortiq hajmdagi bunday hujayralarning 100 dan 300 gacha hujayralari mavjud. Ombor nisbatan kichik bo'lganligi sababli, omborning gavjum mavsumlarida bu omil "darboΔaz" ga aylanadi va ombor jarayonlarini sezilarli darajada sekinlashtiradi.
Muammoni hal qilish g'oyasi
Bir fikr paydo bo'ldi: eng yaqin sanalari bo'lgan qoldiqlarning partiyalari bitta partiyaga qisqartirilishi kerak va birlashtirilgan partiyaga ega bo'lgan bunday qoldiqlar ixcham holda bitta katakka yoki bir nechta bo'sh joy bo'lmasa, joylashtirilishi kerak. qoldiqlarning butun miqdori.
2-rasm. Hujayralardagi qoldiqlarni siqish sxemasi
Bu sizga joylashtiriladigan yangi tovarlar uchun ishlatiladigan ombor maydonini sezilarli darajada kamaytirish imkonini beradi. Ombor sig'imi haddan tashqari yuklangan vaziyatda bunday chora juda zarur, aks holda yangi tovarlarni joylashtirish uchun bo'sh joy etarli bo'lmasligi mumkin, bu esa omborni joylashtirish va to'ldirish jarayonlarini to'xtatishga olib keladi. Ilgari amalga oshirishdan oldin WMS-tizimlar ushbu operatsiyani qo'lda bajardilar, bu samarasiz edi, chunki hujayralardagi mos qoldiqlarni izlash jarayoni ancha uzoq edi. Endi WMS tizimini joriy qilish bilan biz jarayonni avtomatlashtirishga, tezlashtirishga va uni aqlli qilishga qaror qildik.
Bunday muammoni hal qilish jarayoni 2 bosqichga bo'linadi:
- birinchi bosqichda biz siqilish sanasiga yaqin bo'lgan partiyalar guruhlarini topamiz;
- ikkinchi bosqichda har bir partiyalar guruhi uchun biz hujayralardagi qolgan tovarlarning eng ixcham joylashishini hisoblaymiz.
Joriy maqolada biz algoritmning birinchi bosqichiga e'tibor qaratamiz va keyingi maqola uchun ikkinchi bosqichni yoritishni qoldiramiz.
Muammoning matematik modelini qidiring
Kod yozish va g'ildirakni qayta ixtiro qilish uchun o'tirishdan oldin, biz ushbu muammoga ilmiy yondashishga qaror qildik, ya'ni: uni matematik tarzda shakllantirish, uni taniqli diskret optimallashtirish muammosiga qisqartirish va uni hal qilish uchun samarali mavjud algoritmlardan foydalanish yoki ushbu mavjud algoritmlarni olish. asos qilib oling va ularni hal qilinayotgan amaliy muammoning o'ziga xos xususiyatlariga qarab o'zgartiring.
Biz to'plamlar bilan shug'ullanayotgan muammoning biznes shakllantirilishidan aniq kelib chiqadigan bo'lsak, biz bunday masalani to'plamlar nazariyasi nuqtai nazaridan shakllantiramiz.
Keling - ombordagi ma'lum bir mahsulot qoldig'ining barcha partiyalari to'plami. Mayli β kunlar doimiysi berilgan. Mayli - partiyalarning kichik to'plami, bunda kichik to'plamdagi barcha partiyalar juftlari uchun sanalardagi farq doimiy qiymatdan oshmaydi. . Biz ajratilgan kichik to'plamlarning minimal sonini topishimiz kerak , shunday qilib, barcha kichik to'plamlar birgalikda olib, ko'p beradi .
Boshqacha qilib aytganda, o'xshashlik mezoni doimiy bilan belgilanadigan o'xshash tomonlarning guruhlari yoki klasterlarini topishimiz kerak. . Bu vazifa bizga ma'lum bo'lgan klasterlash muammosini eslatadi. Shuni aytish kerakki, ko'rib chiqilayotgan muammo klasterlash muammosidan farq qiladi, chunki bizning muammomiz konstanta bilan aniqlangan klaster elementlarining o'xshashlik mezoni uchun qat'iy belgilangan shartga ega. , lekin klasterlash muammosida bunday shart yo'q. Klasterlash muammosining bayoni va ushbu muammo bo'yicha ma'lumotni topish mumkin
Shunday qilib, biz muammoni shakllantirishga muvaffaq bo'ldik va shunga o'xshash formulaga ega klassik muammoni topdik. Endi g'ildirakni qayta ixtiro qilmaslik, balki eng yaxshi tajribalarni olish va ularni qo'llash uchun uni hal qilish uchun taniqli algoritmlarni ko'rib chiqish kerak. Klasterlash muammosini hal qilish uchun biz eng mashhur algoritmlarni ko'rib chiqdik, xususan: - degani -vositalar, bog'langan komponentlarni aniqlash algoritmi, minimal kenglikdagi daraxt algoritmi. Bunday algoritmlarning tavsifi va tahlilini topish mumkin
Muammoni hal qilish uchun algoritmlarni klasterlash - degan ma'noni anglatadi va -vositalar umuman qo'llanilmaydi, chunki klasterlar soni hech qachon oldindan ma'lum emas va bunday algoritmlar doimiy kunlar cheklovini hisobga olmaydi. Bunday algoritmlar dastlab ko'rib chiqilmagan.
Bizning muammomizni hal qilish uchun ulangan komponentlarni aniqlash algoritmi va minimal oraliqli daraxt algoritmi ko'proq mos keladi, ammo ma'lum bo'lishicha, ularni hal qilinayotgan muammoga "boshqa" qo'llash va yaxshi echimni olish mumkin emas. Buni tushuntirish uchun bunday algoritmlarning ishlash mantiqini muammomizga nisbatan koβrib chiqamiz.
Grafikni ko'rib chiqing , bunda cho'qqilar tomonlar to'plamidir , va uchlari orasidagi chekka ΠΈ partiyalar orasidagi kunlar farqiga teng vaznga ega ΠΈ . Bog'langan komponentlarni aniqlash algoritmida kirish parametri ko'rsatilgan qayerda , va grafikda og'irligi katta bo'lgan barcha qirralar olib tashlanadi . Faqat eng yaqin ob'ektlar juftligi bog'langan holda qoladi. Algoritmning maqsadi bunday qiymatni tanlashdir , bunda grafik bir nechta bog'langan komponentlarga "ajraladi", bu erda ushbu komponentlarga tegishli tomonlar doimiy bilan belgilanadigan o'xshashlik mezonimizga javob beradi. . Olingan komponentlar klasterlardir.
Minimal kenglikdagi daraxt algoritmi birinchi navbatda grafik asosida quriladi minimal kenglikdagi daraxt, so'ngra eng yuqori og'irlikdagi qirralarni ketma-ket ravishda olib tashlab, grafik bir nechta bog'langan komponentlarga "yiqilib" tushmaguncha, bu komponentlarga tegishli tomonlar ham bizning o'xshashlik mezonimizni qondiradi. Olingan komponentlar klasterlar bo'ladi.
Ko'rib chiqilayotgan masalani hal qilish uchun bunday algoritmlardan foydalanganda 3-rasmdagi kabi vaziyat yuzaga kelishi mumkin.
3-rasm. Yechilayotgan masalaga klasterlash algoritmlarini qo'llash
Aytaylik, to'plam kunlari o'rtasidagi farqning doimiysi 20 kun. Grafik vizual idrok etish qulayligi uchun fazoviy shaklda tasvirlangan. Ikkala algoritm ham 3-klasterli yechim ishlab chiqardi, uni alohida klasterlarga joylashtirilgan partiyalarni bir-biri bilan birlashtirish orqali osongina yaxshilash mumkin! Ko'rinib turibdiki, bunday algoritmlarni hal qilinayotgan masalaning o'ziga xos xususiyatlariga mos ravishda o'zgartirish kerak va ularni bizning masalamizni hal qilishda sof shaklda qo'llash yomon natijalar beradi.
Shunday qilib, biz vazifamiz uchun o'zgartirilgan grafik algoritmlari uchun kod yozishni va o'z velosipedimizni qayta ixtiro qilishni boshlashdan oldin (ularning siluetlarida biz kvadrat g'ildiraklarning konturlarini ko'rishimiz mumkin edi), biz yana bunday muammoga ilmiy yondashishga qaror qildik, xususan: uni hal qilish uchun mavjud algoritmlarni o'zgartirishlarsiz qo'llash mumkinligiga umid qilib, uni boshqa diskret muammoni optimallashtirishga kamaytirishga harakat qiling.
Shunga o'xshash klassik muammo bo'yicha yana bir qidiruv muvaffaqiyatli bo'ldi! Biz diskret optimallashtirish muammosini topishga muvaffaq bo'ldik, uning formulasi bizning muammomizning formulasi bilan 1 dan 1 ga to'g'ri keladi. Bu vazifa bo'lib chiqdi qoplama muammosini o'rnatish. Keling, o'ziga xos xususiyatlarimiz bilan bog'liq holda muammoning formulasini taqdim qilaylik.
Cheklangan to'plam mavjud va oila uning barcha ajratilgan tomonlar kichik to'plamlari, shundayki, har bir kichik to'plamning barcha partiya juftliklari uchun sanalardagi farq oiladan konstantalardan oshmaydi . Qoplama oila deb ataladi elementlari tegishli bo'lgan eng kam quvvat , shundayki, to'plamlar birlashmasi oiladan barcha tomonlarning to'plamini berishi kerak .
Ushbu muammoning batafsil tahlilini topish mumkin ΠΈ Qoplash muammosini va uning modifikatsiyalarini amaliy qo'llashning boshqa variantlarini topish mumkin
Muammoni hal qilish algoritmi
Biz echilishi kerak bo'lgan muammoning matematik modelini belgilab oldik. Endi uni yechish algoritmini koβrib chiqamiz. Kichik to'plamlar oiladan quyidagi tartib orqali osongina topish mumkin.
- To'plamdan to'plamlarni joylashtiring ularning sanalarining kamayish tartibida.
- Minimal va maksimal to'plam sanalarini toping.
- Har kun uchun minimal sanadan maksimalgacha, sanalari farq qiladigan barcha partiyalarni toping dan ortiq emas (shuning uchun qiymat Juft raqamni olish yaxshiroqdir).
To'plamlar oilasini shakllantirish protsedurasining mantiqiyligi da kunlar 4-rasmda keltirilgan.
4-rasm. Partiyalarning kichik to'plamlarini shakllantirish
Ushbu protsedura hamma uchun kerak emas boshqa barcha partiyalarni ko'rib chiqing va ularning sanalaridagi farqni yoki joriy qiymatdan tekshiring sanasi boshqacha bo'lgan to'plamni topmaguningizcha chapga yoki o'ngga siljiting doimiy qiymatining yarmidan ko'pi bilan. Barcha keyingi elementlar, ham o'ngga, ham chapga harakatlanayotganda, biz uchun qiziq bo'lmaydi, chunki ular uchun kunlardagi farq faqat ortadi, chunki massivdagi elementlar dastlab buyurtma qilingan. Ushbu yondashuv partiyalar soni va ularning sanalarining tarqalishi sezilarli darajada katta bo'lganda vaqtni sezilarli darajada tejaydi.
To'plamni qoplash muammosi -qiyin, ya'ni tezkor (kirish ma'lumotlarining polinomiga teng ish vaqti bilan) va uni hal qilishning aniq algoritmi yo'q. Shuning uchun, to'plamni qoplash muammosini hal qilish uchun tezkor ochko'z algoritm tanlandi, bu, albatta, aniq emas, lekin quyidagi afzalliklarga ega:
- Kichik o'lchamli muammolar uchun (va bu bizning holatimizda) optimalga juda yaqin bo'lgan echimlarni hisoblab chiqadi. Muammoning hajmi oshgani sayin, yechim sifati yomonlashadi, lekin baribir juda sekin;
- Amalga oshirish juda oson;
- Tez, chunki uning ishlash vaqti taxminiy .
Ochko'z algoritm quyidagi qoida asosida to'plamlarni tanlaydi: har bir bosqichda hali qamrab olinmagan elementlarning maksimal sonini qamrab oladigan to'plam tanlanadi. Algoritmning batafsil tavsifi va uning psevdokodini topish mumkin
Yechilayotgan masalaning test maβlumotlari boβyicha bunday ochkoβz algoritmning toβgβriligini boshqa maβlum algoritmlar, masalan, ehtimollik ochkoβzlik algoritmi, chumolilar koloniyasi algoritmi va boshqalar bilan taqqoslash amalga oshirilmagan. Yaratilgan tasodifiy ma'lumotlar bo'yicha bunday algoritmlarni solishtirish natijalarini topish mumkin
Algoritmni amalga oshirish va amalga oshirish
Ushbu algoritm tilda amalga oshirildi 1Π‘ va ulangan "Qaldiq siqish" deb nomlangan tashqi ishlovga kiritilgan WMS-tizim. Biz tilda algoritmni amalga oshirmadik C ++ va uni tashqi Native komponentidan foydalaning, bu to'g'riroq bo'ladi, chunki kod tezligi pastroq C ++ marta va ba'zi misollarda shunga o'xshash kod tezligidan o'nlab marta tezroq 1Π‘. Tilda 1Π‘ Algoritm ishlab chiqish vaqtini tejash va mijozning ishlab chiqarish bazasida nosozliklarni tuzatish qulayligi uchun amalga oshirildi. Algoritmning natijasi 5-rasmda keltirilgan.
5-rasm. Qoldiqlarni "siqish" uchun ishlov berish
5-rasmda ko'rsatilgan omborda saqlash kameralaridagi tovarlarning joriy qoldiqlari klasterlarga bo'linganligini ko'rsatadi, ular doirasida tovarlar partiyalarining sanalari bir-biridan 30 kundan ko'p bo'lmagan farq qiladi. Buyurtmachi omborda saqlash muddati yillar bilan hisoblangan metall balli klapanlarni ishlab chiqaradi va saqlaydi, bunday sana farqini e'tiborsiz qoldirish mumkin. E'tibor bering, bunday qayta ishlash hozirda ishlab chiqarishda va operatorlarda tizimli ravishda qo'llaniladi WMS partiya klasterining yaxshi sifatini tasdiqlang.
Xulosa va davomi
Bunday amaliy muammoni hal qilishda biz olgan asosiy tajriba paradigmadan foydalanish samaradorligini tasdiqlashdir: matematika. muammo bayoni mashhur mat. model mashhur algoritm muammoning o'ziga xos xususiyatlarini hisobga olgan holda algoritm. Diskret optimallashtirish 300 yildan ortiq vaqtdan beri mavjud bo'lib, bu vaqt ichida odamlar ko'plab muammolarni ko'rib chiqishga muvaffaq bo'lishdi va ularni hal qilishda katta tajriba to'plashdi. Avvalo, ushbu tajribaga murojaat qilish tavsiya etiladi va shundan keyingina g'ildirakni qayta ixtiro qilishni boshlang.
Keyingi maqolada biz optimallashtirish algoritmlari haqidagi hikoyani davom ettiramiz va eng qiziqarli va ancha murakkabini ko'rib chiqamiz: kirish sifatida paketli klasterlash algoritmidan olingan ma'lumotlardan foydalanadigan hujayra qoldiqlarini optimal "siqishni" uchun algoritm.
Maqolani tayyorladi
Roman Shangin, loyihalar bo'limi dasturchisi,
Birinchi BIT kompaniyasi, Chelyabinsk
Manba: www.habr.com