Artiklis kirjeldatakse, kuidas seda rakendada WMS-süsteem, seisime silmitsi vajadusega lahendada mittestandardne klastriprobleem ja milliseid algoritme me selle lahendamiseks kasutasime. Räägime teile, kuidas rakendasime probleemi lahendamisel süstemaatilist, teaduslikku lähenemist, milliseid raskusi me kokku puutusime ja milliseid õppetunde saime.
See väljaanne alustab artiklite sarja, milles jagame oma edukaid kogemusi optimeerimisalgoritmide rakendamisel laoprotsessides. Artiklite sarja eesmärk on tutvustada publikule laotoimingute optimeerimisprobleemide liike, mis tekivad peaaegu igas keskmises ja suures laos, samuti rääkida meie kogemustest selliste probleemide lahendamisel ja lõksudest, mis sellel teel kokku puutusid. . Artiklid on kasulikud neile, kes töötavad lao logistika valdkonnas, rakendavad WMS-süsteemid, aga ka programmeerijad, kes on huvitatud matemaatika rakendamisest äritegevuses ja protsesside optimeerimisest ettevõttes.
Pudelikael protsessides
2018. aastal saime elluviimiseks valmis projekti WMS-süsteemid Tšeljabinskis asuva ettevõtte “Trading House “LD” laos. Võtsime kasutusele toote “1C-Logistics: Warehouse Management 3” 20 töökoha jaoks: operaatorid WMS, laohoidjad, tõstukijuhid. Keskmine ladu on ca 4 tuhat m2, lahtrite arv 5000 ja SKUde arv 4500. Laos hoitakse erinevas mõõdus meie omatoodangu kuulventiile alates 1 kg kuni 400 kg. Laovarusid hoitakse partiidena, kuna on vaja kaupu valida FIFO järgi.
Laoprotsesside automatiseerimise skeemide kavandamisel seisime silmitsi olemasoleva probleemiga mitteoptimaalse laovarude ladustamisega. Kraanade ladustamise ja paigutamise spetsiifika on selline, et üks lahter võib sisaldada ainult ühe partii esemeid. Tooted jõuavad lattu iga päev ja iga saabumine on eraldi partii. Kokku tekib 1-kuulise laotöö tulemusena 30 eraldi partiid, hoolimata asjaolust, et iga partii tuleks hoida eraldi lahtris. Tooted valitakse sageli mitte tervete kaubaaluste, vaid tükkidena ja selle tulemusena on paljudes lahtrites tükivaliku tsoonis järgmine pilt: lahtris, mille maht on üle 1 m3, on mitu kraanade tükki, mis hõivavad vähem kui 5-10% raku mahust.
Joonis 1. Foto mitmest kaubatükist lahtris
On selge, et mälumahtu ei kasutata optimaalselt. Katastroofi ulatuse ettekujutamiseks võin anda arvud: keskmiselt on lao erinevatel tööperioodidel selliseid kambreid, mille maht on üle 1 m3 ja mille saldo on väike, 100 kuni 300. Kuna ladu on suhteliselt väike, siis kiirel laohooajal muutub see tegur “pudelikaelaks” ja aeglustab oluliselt laoprotsesse.
Probleemi lahenduse idee
Tekkis idee: lähimate kuupäevadega jääkide partiid tuleks vähendada üheks partiiks ja sellised ühtse partiiga jäägid paigutada kompaktselt ühte lahtrisse või mitmesse, kui ühes ei ole piisavalt ruumi lahtrisse mahutamiseks. kogu jääkide kogus.
Joonis 2. Skeem rakkudes jääkide kokkupressimiseks
See võimaldab oluliselt vähendada hõivatud laopinda, mida kasutatakse uute kaupade paigutamiseks. Olukorras, kus lao maht on ülekoormatud, on selline meede äärmiselt vajalik, sest vastasel juhul ei pruugi uute kaupade mahutamiseks lihtsalt piisavalt vaba ruumi olla, mis toob kaasa lao paigutamise ja täiendamise protsesside seiskumise. Varem enne rakendamist WMS-süsteemid tegid selle toimingu käsitsi, mis oli ebaefektiivne, kuna rakkudes sobivate jääkide otsimise protsess oli üsna pikk. Nüüd, WMS-süsteemi kasutuselevõtuga, otsustasime protsessi automatiseerida, kiirendada ja muuta see intelligentseks.
Sellise probleemi lahendamise protsess on jagatud kaheks etapiks:
- esimeses etapis leiame tihendamiseks lähedased partiide rühmad;
- teises etapis arvutame iga partiide rühma jaoks ülejäänud kaupade kõige kompaktsema paigutuse lahtrites.
Käesolevas artiklis keskendume algoritmi esimesele etapile ja jätame teise etapi kajastamise järgmisele artiklile.
Otsige probleemi matemaatilist mudelit
Enne kui asusime koodi kirjutama ja oma ratast uuesti leiutama, otsustasime läheneda sellele probleemile teaduslikult, nimelt: sõnastada see matemaatiliselt, taandada see tuntud diskreetseks optimeerimisprobleemiks ja kasutada selle lahendamiseks tõhusaid olemasolevaid algoritme või kasutada neid olemasolevaid algoritme. aluseks ja modifitseerida neid vastavalt lahendatava praktilise probleemi spetsiifikale.
Kuna ülesande ärilisest sõnastusest tuleneb selgelt, et tegemist on hulkadega, siis sõnastame sellise probleemi hulgateooria mõttes.
Laskma – laos oleva teatud toote ülejäänud partiide kogum. Lase – antud päevade konstant. Lase – partiide alamhulk, kus alamhulga kõigi partiide paaride kuupäevade erinevus ei ületa konstanti . Peame leidma disjunkteeruvate alamhulkade minimaalse arvu , nii et kõik alamhulgad kokku võttes annaks palju .
Teisisõnu peame leidma sarnaste osapoolte rühmad või klastrid, kus sarnasuse kriteeriumi määrab konstant . See ülesanne tuletab meile meelde tuntud klastriprobleemi. Oluline on öelda, et vaadeldav probleem erineb klastriprobleemist selle poolest, et meie probleemil on klastri elementide sarnasuse kriteeriumi jaoks rangelt määratletud tingimus, mille määrab konstant , kuid klastriprobleemis sellist tingimust pole. Klasterdamisprobleemi avaldus ja teave selle probleemi kohta leiate
Seega õnnestus meil probleem sõnastada ja leida klassikaline sarnase sõnastusega probleem. Nüüd on vaja mõelda selle lahendamiseks tuntud algoritmidele, et mitte jalgratast uuesti leiutada, vaid võtta parimad tavad ja neid rakendada. Klasterdamisprobleemi lahendamiseks kaalusime kõige populaarsemaid algoritme, nimelt: - tähendab -vahendid, ühendatud komponentide tuvastamise algoritm, minimaalse ulatuva puu algoritm. Selliste algoritmide kirjelduse ja analüüsi leiate
Meie probleemi lahendamiseks klasterdamisalgoritmid -tähendab ja -vahendid ei ole üldse rakendatavad, kuna klastrite arv pole kunagi ette teada ja sellised algoritmid ei võta konstantse päevade piirangut arvesse. Sellised algoritmid jäeti esialgu kaalumisest kõrvale.
Meie probleemi lahendamiseks sobivad paremini ühendatud komponentide identifitseerimise algoritm ja minimaalse ulatusega puu algoritm, kuid nagu selgus, ei saa neid lahendatavale probleemile "peapeale" rakendada ja head lahendust saada. Selle selgitamiseks vaatleme selliste algoritmide toimimise loogikat seoses meie probleemiga.
Mõelge graafikule , mille tipud on poolte hulk , ja tippude vaheline serv и mille kaal on võrdne partiide päevade vahega и . Ühendatud komponentide tuvastamise algoritmis on määratud sisendparameeter Kus , ja graafikul eemaldatakse kõik servad, mille kaal on suurem . Seotuks jäävad vaid lähimad objektide paarid. Algoritmi mõte on valida selline väärtus , milles graafik “lahkub” mitmeks ühendatud komponendiks, kus nendesse komponentidesse kuuluvad osapooled vastavad meie konstandiga määratud sarnasuse kriteeriumile . Saadud komponendid on klastrid.
Minimaalse ulatuva puu algoritm põhineb kõigepealt graafikul minimaalse ulatusega puu ja seejärel eemaldab järjestikku suurima kaaluga servad, kuni graafik “lahkub” mitmeks ühendatud komponendiks, kus nendesse komponentidesse kuuluvad osapooled vastavad ka meie sarnasuse kriteeriumile. Saadud komponendid on klastrid.
Selliste algoritmide kasutamisel vaadeldava probleemi lahendamiseks võib tekkida olukord nagu joonisel 3.
Joonis 3. Klasterdamisalgoritmide rakendamine lahendatavale probleemile
Oletame, et meie partiipäevade erinevuse konstant on 20 päeva. Graafik kujutati visuaalse tajumise hõlbustamiseks ruumilisel kujul. Mõlemad algoritmid andsid 3-klastrilise lahenduse, mida saab hõlpsasti täiustada, kombineerides eraldi klastritesse paigutatud partiisid üksteisega! On ilmne, et selliseid algoritme tuleb modifitseerida, et need vastaksid lahendatava ülesande spetsiifikale ja nende puhtal kujul rakendamine meie probleemi lahendamisel annab kehvad tulemused.
Niisiis, enne kui hakkasime oma ülesande jaoks kohandatud graafikalgoritmidele koodi kirjutama ja oma jalgratast uuesti leiutama (mille siluettidel oli juba näha ruudukujuliste rataste piirjooni), otsustasime taas läheneda sellisele probleemile teaduslikult, nimelt: proovige seda taandada mõneks muuks eraldiseisvaks probleemi optimeerimiseks, lootuses, et olemasolevaid selle lahendamise algoritme saab muudatusteta rakendada.
Järjekordne sarnase klassikalise probleemi otsimine on olnud edukas! Meil õnnestus leida diskreetne optimeerimisülesanne, mille sõnastus ühtib 1:1 meie ülesande sõnastusega. See ülesanne osutus selleks määrata katmise probleem. Esitame probleemi sõnastuse seoses meie eripäradega.
On piiratud komplekt ja perekond kõigist selle mitteühendatud osapoolte alamhulkadest, nii et iga alamhulga kõigi osapoolte paaride kuupäevade erinevus perekonnast ei ületa konstante . Katet nimetatakse perekonnaks kõige väiksema võimsusega, mille elemendid kuuluvad , nii et komplektide liit perekonnast peaks andma kõigi osapoolte komplekti .
Selle probleemi üksikasjaliku analüüsi leiate и Katteprobleemi ja selle modifikatsioonide praktiliseks rakendamiseks võib leida muid võimalusi
Algoritm probleemi lahendamiseks
Oleme otsustanud lahendada lahendatava ülesande matemaatilise mudeli. Nüüd vaatame selle lahendamise algoritmi. Alamhulgad perekonnast saab hõlpsasti leida järgmise protseduuri abil.
- Korraldage partiid komplektist nende kuupäevade kahanevas järjekorras.
- Leidke partii minimaalne ja maksimaalne kuupäev.
- Igaks päevaks alates minimaalsest kuupäevast kuni maksimumini, otsige üles kõik partiid, mille kuupäevad erinevad mitte rohkem kui (nii et väärtus Parem on võtta paarisarv).
Hulgipere moodustamise protseduuri loogika juures päevad on näidatud joonisel 4.
Joonis 4. Parteide alamhulkade moodustamine
See protseduur pole kõigile vajalik läbima kõik muud partiid ja kontrollima nende kuupäevade erinevust või hetkeväärtust liigutage vasakule või paremale, kuni leiate partii, mille kuupäev erineb rohkem kui poole võrra konstandi väärtusest. Kõik järgnevad elemendid, liikudes nii paremale kui ka vasakule, ei ole meile huvitavad, kuna nende jaoks päevade erinevus ainult suureneb, kuna massiivi elemendid olid algselt tellitud. Selline lähenemine säästab oluliselt aega, kui pidude arv ja nende kuupäevade levik on oluliselt suur.
Komplekti katte probleem on -raske, mis tähendab, et selle lahendamiseks puudub kiire (tööaeg võrdub sisendandmete polünoomiga) ja täpne algoritm. Seetõttu valiti komplekti katmise probleemi lahendamiseks kiire ahne algoritm, mis muidugi ei ole täpne, kuid millel on järgmised eelised:
- Väikeste probleemide jaoks (ja see on täpselt meie juhtum) arvutab see lahendused, mis on üsna optimaalse lähedal. Probleemi suuruse kasvades halveneb lahenduse kvaliteet, kuid siiski üsna aeglaselt;
- Väga lihtne rakendada;
- Kiire, kuna selle tööaja hinnang on .
Ahne algoritm valib hulgad järgmise reegli alusel: igas etapis valitakse hulk, mis katab maksimaalse arvu veel katmata elemente. Algoritmi ja selle pseudokoodi üksikasjalik kirjeldus on leitav
Sellise ahne algoritmi täpsuse võrdlust lahendatava ülesande testandmetel teiste tuntud algoritmidega, nagu tõenäosuslik ahne algoritm, sipelgakoloonia algoritm jne, ei ole tehtud. Selliste algoritmide võrdlemise tulemused genereeritud juhuslike andmete põhjal leiate
Algoritmi juurutamine ja juurutamine
See algoritm rakendati keeles 1S ja see kaasati välisesse töötlusse nimega "Jääkide kokkupressimine", millega ühendati WMS-süsteem. Me ei rakendanud algoritmi keeles C ++ ja kasutada seda välisest algkomponendist, mis oleks õigem, kuna koodi kiirus on väiksem C + + korda ja mõnel näitel isegi kümneid kordi kiiremini kui sarnase koodi sisselülitamise kiirus 1S. Keele peal 1S Algoritmi rakendati arendusaja säästmiseks ja kliendi tootmisbaasis silumise hõlbustamiseks. Algoritmi tulemus on toodud joonisel 5.
Joonis 5. Töötlemine jääkide "pressimiseks".
Jooniselt 5 on näha, et nimetatud laos on laolahtrites kaupade jooksvad jäägid jaotatud klastriteks, mille sees kaubapartiide kuupäevad erinevad üksteisest mitte rohkem kui 30 päeva võrra. Kuna klient toodab ja ladustab laos metallist kuulventiile, mille säilivusaega on arvestatud aastates, siis võib sellise kuupäevade erinevuse arvestamata jätta. Pange tähele, et sellist töötlemist kasutatakse praegu tootmises ja operaatorites süstemaatiliselt WMS kinnitada parteide rühmitamise head kvaliteeti.
Järeldused ja jätk
Peamine kogemus, mille me sellise praktilise probleemi lahendamisest saime, on kinnitus paradigma: matemaatika kasutamise tõhususest. probleemipüstituses kuulus matt. mudel kuulus algoritm algoritmi, võttes arvesse probleemi eripära. Diskreetne optimeerimine on eksisteerinud enam kui 300 aastat ja selle aja jooksul on inimesed jõudnud läbi mõelda palju probleeme ja koguda palju kogemusi nende lahendamisel. Kõigepealt on soovitatav pöörduda selle kogemuse poole ja alles seejärel asuda oma ratast uuesti leiutama.
Järgmises artiklis jätkame optimeerimisalgoritmide lugu ning vaatleme kõige huvitavamat ja palju keerulisemat: rakujääkide optimaalse “tihendamise” algoritmi, mis kasutab sisendina partii klasterdamise algoritmilt saadud andmeid.
Valmistas artikli ette
Roman Shangin, projektide osakonna programmeerija,
Esimene BIT-ettevõte, Tšeljabinsk
Allikas: www.habr.com