Die artikel beskryf hoe om te implementeer WMS-stelsel, het ons gekonfronteer met die behoefte om 'n nie-standaard groeperingsprobleem op te los en watter algoritmes ons gebruik het om dit op te los. Ons sal jou vertel hoe ons 'n sistematiese, wetenskaplike benadering toegepas het om die probleem op te los, watter probleme ons teëgekom het en watter lesse ons geleer het.
Hierdie publikasie begin met 'n reeks artikels waarin ons ons suksesvolle ervaring in die implementering van optimaliseringsalgoritmes in pakhuisprosesse deel. Die doel van die reeks artikels is om die gehoor vertroud te maak met die tipes optimaliseringsprobleme van pakhuisbedrywighede wat in bykans enige medium en groot pakhuis ontstaan, asook om te vertel van ons ervaring met die oplossing van sulke probleme en die slaggate wat langs die pad teëgekom word. . Die artikels sal nuttig wees vir diegene wat in die pakhuis logistieke bedryf werk, implementeer WMS-stelsels, sowel as programmeerders wat belangstel in toepassings van wiskunde in besigheid en optimalisering van prosesse in 'n onderneming.
Bottelnek in prosesse
In 2018 het ons 'n projek voltooi om te implementeer WMS-stelsels by die pakhuis van die maatskappy "Trading House "LD" in Chelyabinsk. Ons het die produk "1C-Logistics: Warehouse Management 3" geïmplementeer vir 20 werkplekke: operateurs WMS, stoormanne, vurkhyserbestuurders. Die gemiddelde pakhuis is ongeveer 4 duisend m2, die aantal selle is 5000 en die aantal SKU's is 4500. Die pakhuis stoor balkleppe van ons eie produksie van verskillende groottes van 1 kg tot 400 kg. Voorraad in die pakhuis word in bondels gestoor, aangesien daar 'n behoefte is om goedere volgens EIEU te kies.
Toe ons pakhuisproses-outomatiseringskemas ontwerp het, het ons te doen gekry met die bestaande probleem van nie-optimale voorraadberging. Die besonderhede van die stoor en stoor van hyskrane is sodanig dat een eenheidstoorsel slegs items uit een bondel kan bevat. Produkte kom daagliks by die pakhuis aan en elke aankoms is 'n aparte bondel. In totaal, as gevolg van 1 maand se pakhuisbedryf, word 30 afsonderlike groepe geskep, ten spyte van die feit dat elkeen in 'n aparte sel gestoor moet word. Produkte word dikwels nie in hele palette geselekteer nie, maar in stukke, en gevolglik word die volgende prentjie in die stuk seleksiesone in baie selle waargeneem: in 'n sel met 'n volume van meer as 1 m3 is daar verskeie stukke hyskrane wat beslaan minder as 5-10% van die selvolume.
Fig 1. Foto van verskeie stukke goedere in 'n sel
Dit is duidelik dat bergingskapasiteit nie optimaal benut word nie. Om die omvang van die ramp voor te stel, kan ek syfers gee: gemiddeld is daar van 1 tot 3 selle van sulke selle met 'n volume van meer as 100 m300 met "minuskule" saldo's gedurende verskillende tydperke van die pakhuis se werking. Aangesien die pakhuis relatief klein is, word hierdie faktor gedurende die pakhuis besige seisoene 'n "bottelnek" en vertraag pakhuisprosesse aansienlik.
Probleemoplossing idee
'n Idee het ontstaan: groepe oorskiet met die naaste datums moet tot een enkele bondel verminder word, en sulke oorskiet met 'n verenigde bondel moet kompak saam geplaas word in een sel, of in verskeie, as daar nie genoeg spasie in een is om die hele hoeveelheid oorskiet.
Fig.2. Skema vir die saampersing van residue in selle
Dit laat jou toe om die besette pakhuisspasie wat gebruik sal word vir nuwe goedere wat geplaas word, aansienlik te verminder. In 'n situasie waar pakhuiskapasiteit oorlaai is, is so 'n maatreël uiters noodsaaklik, anders kan daar eenvoudig nie genoeg vrye spasie wees om nuwe goedere te akkommodeer nie, wat sal lei tot 'n stop in die pakhuisplasing en aanvullingsprosesse. Voorheen voor implementering WMS-stelsels het hierdie bewerking met die hand uitgevoer, wat ondoeltreffend was, aangesien die proses van soek na geskikte residue in die selle redelik lank was. Nou, met die bekendstelling van 'n WMS-stelsel, het ons besluit om die proses te outomatiseer, dit te bespoedig en intelligent te maak.
Die proses om so 'n probleem op te los word in 2 fases verdeel:
- in die eerste stadium vind ons groepe groepe naby aan datum vir kompressie;
- in die tweede stadium, vir elke groep groepe bereken ons die mees kompakte plasing van die oorblywende goedere in die selle.
In die huidige artikel sal ons fokus op die eerste fase van die algoritme, en laat dekking van die tweede fase vir die volgende artikel.
Soek vir 'n wiskundige model van die probleem
Voordat ons gaan sit het om kode te skryf en ons wiel weer uit te vind, het ons besluit om hierdie probleem wetenskaplik te benader, naamlik: formuleer dit wiskundig, reduseer dit tot 'n bekende diskrete optimaliseringsprobleem en gebruik effektiewe bestaande algoritmes om dit op te los, of neem hierdie bestaande algoritmes as 'n basis en verander dit na die besonderhede van die praktiese probleem wat opgelos word.
Aangesien dit duidelik uit die besigheidsformulering van die probleem volg dat ons met versamelings te doen het, sal ons so 'n probleem in terme van versamelingsteorie formuleer.
laat – die stel van alle groepe van die res van 'n sekere produk in 'n pakhuis. Laat – gegewe konstante van dae. Laat – 'n subset van bondels, waar die verskil in datums vir alle pare bondels in die subset nie 'n konstante oorskry nie . Ons moet die minimum aantal onsamehangende subversamelings vind , sodanig dat alle subversamelings saamgeneem sou baie gee .
Met ander woorde, ons moet groepe of groepe van soortgelyke partye vind, waar die ooreenkomsmaatstaf bepaal word deur die konstante . Hierdie taak herinner ons aan die bekende groeperingsprobleem. Dit is belangrik om te sê dat die probleem onder oorweging verskil van die groeperingsprobleem deurdat ons probleem 'n streng gedefinieerde voorwaarde het vir die kriterium van ooreenkoms van troselemente, bepaal deur die konstante , maar in die groeperingsprobleem is daar nie so 'n toestand nie. Die verklaring van die groeperingsprobleem en inligting oor hierdie probleem kan gevind word
So, ons het daarin geslaag om die probleem te formuleer en 'n klassieke probleem met 'n soortgelyke formulering te vind. Nou is dit nodig om bekende algoritmes te oorweeg om dit op te los, om nie die wiel weer uit te vind nie, maar om die beste praktyke te neem en dit toe te pas. Om die groeperingsprobleem op te los, het ons die gewildste algoritmes oorweeg, naamlik: -beteken -beteken, algoritme vir die identifisering van gekoppelde komponente, minimum spanboom-algoritme. 'n Beskrywing en ontleding van sulke algoritmes kan gevind word
Om ons probleem op te los, groeperingsalgoritmes -beteken en -middele is glad nie van toepassing nie, aangesien die aantal trosse nooit vooraf bekend is nie en sulke algoritmes neem nie die konstante dae beperking in ag nie. Sulke algoritmes is aanvanklik van oorweging weggegooi.
Om ons probleem op te los, is die algoritme vir die identifisering van gekoppelde komponente en die minimum spanboom-algoritme meer geskik, maar, soos dit geblyk het, kan dit nie “kop-aan” toegepas word op die probleem wat opgelos word en 'n goeie oplossing kry nie. Om dit te verduidelik, kom ons kyk na die logika van werking van sulke algoritmes in verhouding tot ons probleem.
Beskou die grafiek , waarin die hoekpunte die stel partye is , en die rand tussen die hoekpunte и het 'n gewig gelyk aan die verskil van dae tussen groepe и . In die algoritme vir die identifisering van gekoppelde komponente word die invoerparameter gespesifiseer Waar , en in die grafiek alle rande waarvoor die gewig groter is, word verwyder . Slegs die naaste pare voorwerpe bly verbind. Die punt van die algoritme is om so 'n waarde te kies , waarin die grafiek “uitmekaar val” in verskeie gekoppelde komponente, waar die partye wat aan hierdie komponente behoort, sal voldoen aan ons ooreenkomsmaatstaf, bepaal deur die konstante . Die resulterende komponente is trosse.
Die minimum spanboom-algoritme bou eers op 'n grafiek minimum spanboom, en verwyder dan agtereenvolgens rande met die hoogste gewig totdat die grafiek in verskeie gekoppelde komponente "uitmekaar val", waar die partye wat aan hierdie komponente behoort ook aan ons ooreenkomsmaatstaf sal voldoen. Die resulterende komponente sal trosse wees.
Wanneer sulke algoritmes gebruik word om die probleem wat oorweeg word op te los, kan 'n situasie soos in Figuur 3 ontstaan.
Fig 3. Toepassing van groeperingsalgoritmes op die probleem wat opgelos word
Kom ons sê ons konstante vir die verskil tussen bondeldae is 20 dae. Grafiek is in ruimtelike vorm uitgebeeld vir gemak van visuele persepsie. Albei algoritmes het 'n 3-kluster-oplossing geproduseer, wat maklik verbeter kan word deur die groepe wat in aparte trosse geplaas is, met mekaar te kombineer! Dit is duidelik dat sulke algoritmes aangepas moet word om aan te pas by die besonderhede van die probleem wat opgelos word, en die toepassing daarvan in sy suiwer vorm vir die oplossing van ons probleem sal swak resultate lewer.
Dus, voordat ons kode begin skryf het vir grafiekalgoritmes wat vir ons taak aangepas is en ons eie fiets herontdek het (in die silhoeëtte waarvan ons reeds die buitelyne van vierkantige wiele kon onderskei), het ons weer besluit om so 'n probleem wetenskaplik te benader, naamlik: probeer om dit te reduseer na 'n ander diskrete probleemoptimalisering, in die hoop dat bestaande algoritmes om dit op te los toegepas kan word sonder veranderinge.
Nog 'n soektog na 'n soortgelyke klassieke probleem was suksesvol! Ons het daarin geslaag om 'n diskrete optimaliseringsprobleem te vind, waarvan die formulering 1 uit 1 saamval met die formulering van ons probleem. Hierdie taak het geblyk te wees stel bedekking probleem. Kom ons stel die formulering van die probleem in verhouding tot ons besonderhede voor.
Daar is 'n eindige stel en familie van al sy onsamehangende subgroepe van partye, sodat die verskil in datums vir alle pare partye van elke subset van die familie konstantes nie oorskry nie . 'n Bedekking word 'n familie genoem van die minste krag, waarvan die elemente behoort , sodanig dat die vereniging van versamelings van die familie moet die stel van alle partye gee .
'n Gedetailleerde ontleding van hierdie probleem kan gevind word и Ander opsies vir die praktiese toepassing van die bedekkingsprobleem en sy wysigings kan gevind word
Algoritme om die probleem op te los
Ons het besluit op die wiskundige model van die probleem wat opgelos moet word. Kom ons kyk nou na die algoritme om dit op te los. Subsets van die familie kan maklik gevind word deur die volgende prosedure.
- Rangskik bondels uit 'n stel in dalende volgorde van hul datums.
- Vind die minimum en maksimum bondeldatums.
- Vir elke dag van die minimum datum tot die maksimum, vind alle bondels waarvan die datums verskil nie meer as (dus die waarde Dit is beter om die ewe getal te neem).
Logika van die prosedure vir die vorming van 'n familie van stelle by dae word in Figuur 4 voorgestel.
Fig.4. Vorming van subgroepe van partye
Hierdie prosedure is nie vir almal nodig nie gaan deur alle ander groepe en kyk na die verskil in hul datums, of van die huidige waarde beweeg links of regs totdat jy 'n bondel kry waarvan die datum verskil met meer as die helfte van die waarde van die konstante. Alle daaropvolgende elemente, wanneer hulle beide na regs en na links beweeg, sal nie vir ons interessant wees nie, aangesien die verskil in dae vir hulle net sal toeneem, aangesien die elemente in die skikking aanvanklik georden is. Hierdie benadering sal aansienlik tyd bespaar wanneer die aantal partytjies en die verspreiding van hul datums aansienlik groot is.
Die stelbedekkingsprobleem is -moeilik, wat beteken dat daar geen vinnige (met bedryfstyd gelyk aan 'n polinoom van die insetdata) en akkurate algoritme is om dit op te los nie. Daarom, om die stelbedekkingsprobleem op te los, is 'n vinnige gulsige algoritme gekies, wat natuurlik nie akkuraat is nie, maar die volgende voordele het:
- Vir klein probleme (en dit is presies ons geval), bereken dit oplossings wat redelik naby aan die optimum is. Soos die omvang van die probleem toeneem, verswak die kwaliteit van die oplossing, maar steeds redelik stadig;
- Baie maklik om te implementeer;
- Vinnig, aangesien sy looptydskatting is .
Die gulsige algoritme kies stelle op grond van die volgende reël: in elke stadium word 'n stel gekies wat die maksimum aantal elemente dek wat nog nie gedek is nie. 'n Gedetailleerde beskrywing van die algoritme en sy pseudokode kan gevind word
'n Vergelyking van die akkuraatheid van so 'n gulsige algoritme op toetsdata van die probleem wat opgelos word met ander bekende algoritmes, soos die waarskynlike gulsige algoritme, die mierkolonie-algoritme, ens., is nie gemaak nie. Die resultate van vergelyking van sulke algoritmes op gegenereerde ewekansige data kan gevind word
Implementering en implementering van die algoritme
Hierdie algoritme is in die taal geïmplementeer 1S en is ingesluit in 'n eksterne verwerking genaamd "Residue Compression" waaraan gekoppel is WMS-stelsel. Ons het nie die algoritme in die taal geïmplementeer nie C ++ en gebruik dit vanaf 'n eksterne inheemse komponent, wat meer korrek sou wees, aangesien die spoed van die kode laer is C + + keer en in sommige voorbeelde selfs tientalle keer vinniger as die spoed van soortgelyke kode aan 1S. Op die tong 1S Die algoritme is geïmplementeer om ontwikkelingstyd en gemak van ontfouting by die kliënt se produksiebasis te bespaar. Die resultaat van die algoritme word in Figuur 5 aangebied.
Fig.5. Verwerking om residue te “compress”.
Figuur 5 toon dat in die gespesifiseerde pakhuis, die huidige saldo's van goedere in stoorselle in groepe verdeel word, waarbinne die datums van die goederegroepe nie meer as 30 dae van mekaar verskil nie. Aangesien die klant metaalkogelkleppe in die pakhuis vervaardig en stoor, waarvan die raklewe in jare bereken word, kan so 'n datumverskil afgeskeep word. Let daarop dat sulke verwerking tans sistematies in produksie en operateurs gebruik word WMS bevestig die goeie gehalte van partytjiegroepering.
Gevolgtrekkings en voortsetting
Die belangrikste ervaring wat ons opgedoen het met die oplossing van so 'n praktiese probleem is bevestiging van die doeltreffendheid van die gebruik van die paradigma: wiskunde. probleemstelling bekende mat. model bekende algoritme algoritme wat die besonderhede van die probleem in ag neem. Diskrete optimalisering bestaan al meer as 300 jaar, en gedurende hierdie tyd het mense daarin geslaag om baie probleme te oorweeg en baie ondervinding op te bou om dit op te los. Eerstens is dit meer raadsaam om na hierdie ervaring te wend, en dan eers weer jou wiel te begin uitvind.
In die volgende artikel gaan ons voort met die storie oor optimaliseringsalgoritmes en kyk na die interessantste en baie meer komplekse: 'n algoritme vir optimale "kompressie" van selreste, wat data wat van die bondelgroeperingsalgoritme ontvang is, gebruik as invoer.
Het die artikel voorberei
Roman Shangin, programmeerder van die projekte-afdeling,
Eerste BIT-maatskappy, Chelyabinsk
Bron: will.com