Artiklen beskriver, hvordan man implementerer WMS-system, stod vi over for behovet for at lÞse et ikke-standardiseret klyngeproblem, og hvilke algoritmer vi brugte til at lÞse det. Vi vil fortÊlle dig, hvordan vi anvendte en systematisk, videnskabelig tilgang til at lÞse problemet, hvilke vanskeligheder vi stÞdte pÄ, og hvilke erfaringer vi lÊrte.
Denne publikation indleder en rĂŠkke artikler, hvori vi deler vores succesfulde erfaring med implementering af optimeringsalgoritmer i lagerprocesser. FormĂ„let med serien af ââartikler er at gĂžre publikum bekendt med de typer af optimeringsproblemer af lagerdrift, der opstĂ„r i nĂŠsten alle mellemstore og store varehuse, samt at fortĂŠlle om vores erfaring med at lĂžse sĂ„danne problemer og de faldgruber, man stĂžder pĂ„ undervejs. . Artiklerne vil vĂŠre nyttige for dem, der arbejder i lagerlogistikbranchen, implementere WMS-systemer, samt programmĂžrer, der er interesserede i anvendelser af matematik i erhvervslivet og optimering af processer i en virksomhed.
Flaskehals i processer
I 2018 afsluttede vi et projekt, der skulle implementeres WMS-systemer pĂ„ lageret i virksomheden âTrading House âLDâ i Chelyabinsk. Vi implementerede produktet "1C-Logistics: Warehouse Management 3" til 20 arbejdspladser: operatĂžrer WMS, lagerholdere, gaffeltruckchauffĂžrer. Det gennemsnitlige lager er omkring 4 tusinde m2, antallet af celler er 5000 og antallet af SKU'er er 4500. Lageret opbevarer kugleventiler af vores egen produktion i forskellige stĂžrrelser fra 1 kg til 400 kg. Beholdningen pĂ„ lageret opbevares i partier, da der er behov for at udvĂŠlge varer efter FIFO.
Ved design af lagerprocesautomatiseringsordninger stod vi over for det eksisterende problem med ikke-optimal lageropbevaring. Specifikationerne for opbevaring og stuvning af kraner er sÄdan, at en enhedslagercelle kun kan indeholde varer fra én batch. Produkter ankommer til lageret dagligt, og hver ankomst er en separat batch. I alt, som et resultat af 1 mÄneds lagerdrift, oprettes 30 separate batches, pÄ trods af at hver skal opbevares i en separat celle. Produkter udvÊlges ofte ikke i hele paller, men i stykker, og som fÞlge heraf ses fÞlgende billede i stykvalgszonen i mange celler: I en celle med et volumen pÄ mere end 1 m3 er der flere stykker kraner, som optager mindre end 5-10% af cellevolumenet.
Fig 1. Foto af flere stykker varer i en celle
Det er tydeligt, at lagerkapaciteten ikke bliver udnyttet optimalt. For at forestille mig omfanget af katastrofen kan jeg give tal: I gennemsnit er der fra 1 til 3 celler af sÄdanne celler med et volumen pÄ mere end 100 m300 med "minuskulÊre" balancer i forskellige perioder af lagerets drift. Da lageret er relativt lille, bliver denne faktor i de travle sÊsoner pÄ lageret en "flaskehals" og bremser lagerprocesserne kraftigt.
Idé til problemlÞsning
En idĂ© opstod: partier af rester med de nĂŠrmeste datoer skulle reduceres til Ă©n enkelt batch, og sĂ„danne rester med en samlet batch skulle placeres kompakt sammen i Ă©n celle eller i flere, hvis der ikke er plads nok i Ă©n til at rumme hele mĂŠngden af âârester.
Fig.2. Skema til komprimering af rester i celler
Dette giver dig mulighed for betydeligt at reducere den besatte lagerplads, der vil blive brugt til nye varer, der placeres. I en situation, hvor lagerkapaciteten er overbelastet, er en sĂ„dan foranstaltning yderst nĂždvendig, ellers kan der simpelthen ikke vĂŠre nok ledig plads til at rumme nye varer, hvilket vil fĂžre til et stop i lagerplacering og genopfyldningsprocesser. Tidligere fĂžr implementering WMS-systemer udfĂžrte denne operation manuelt, hvilket var ineffektivt, da processen med at sĂžge efter passende rester i cellerne var ret lang. Nu, med introduktionen af ââet WMS-system, besluttede vi at automatisere processen, fremskynde den og gĂžre den intelligent.
Processen med at lÞse et sÄdant problem er opdelt i 2 faser:
- i det fÞrste trin finder vi grupper af batches tÊt pÄ dato for komprimering;
- i anden fase beregner vi for hver gruppe af partier den mest kompakte placering af de resterende varer i cellerne.
I den aktuelle artikel vil vi fokusere pĂ„ den fĂžrste fase af algoritmen og lade dĂŠkningen af ââden anden fase blive til den nĂŠste artikel.
SĂžg efter en matematisk model af problemet
FĂžr vi satte os ned for at skrive kode og genopfinde vores hjul, besluttede vi at gribe dette problem videnskabeligt an, nemlig: formulere det matematisk, reducere det til et velkendt diskret optimeringsproblem og bruge effektive eksisterende algoritmer til at lĂžse det, eller tage disse eksisterende algoritmer som grundlag og modificere dem til detaljerne i det praktiske problem, der skal lĂžses.
Da det klart fÞlger af problemformuleringens forretningsmÊssige formulering, at vi har med mÊngder at gÞre, vil vi formulere en sÄdan problemstilling ud fra mÊngdelÊre.
Lad 
â sĂŠttet af alle partier af resten af ââet bestemt produkt pĂ„ et lager. Lade 
â givet konstant af dage. Lade 
â en delmĂŠngde af batches, hvor forskellen i datoer for alle par af batches i delmĂŠngden ikke overstiger en konstant 
. Vi skal finde det mindste antal usammenhÊngende delmÊngder 
, sÄdan at alle delmÊngder 
tilsammen ville give mange 
.
Vi skal med andre ord finde grupper eller klynger af lignende parter, hvor lighedskriteriet er bestemt af konstanten 
. Denne opgave minder os om det velkendte klyngeproblem. Det er vigtigt at sige, at problemet under overvejelse adskiller sig fra klyngeproblemet ved, at vores problem har en strengt defineret betingelse for kriteriet om lighed mellem klyngeelementer, bestemt af den konstante 
, men i klyngeproblemet er der ingen sĂ„dan betingelse. RedegĂžrelsen af ââklyngeproblemet og oplysninger om dette problem kan findes
SÄ det lykkedes os at formulere problemet og finde et klassisk problem med en lignende formulering. Nu er det nÞdvendigt at overveje velkendte algoritmer til at lÞse det, for ikke at genopfinde hjulet, men for at tage den bedste praksis og anvende dem. For at lÞse klyngeproblemet overvejede vi de mest populÊre algoritmer, nemlig: 
-midler, 
-midler, algoritme til at identificere forbundne komponenter, minimum spÊndingstrÊ-algoritme. En beskrivelse og analyse af sÄdanne algoritmer kan findes
For at lÞse vores problem, klynge algoritmer 
- betyder og 
-midler er slet ikke anvendelige, da antallet af klynger aldrig kendes pÄ forhÄnd 
og sÄdanne algoritmer tager ikke hÞjde for den konstante dages begrÊnsning. SÄdanne algoritmer blev oprindeligt kasseret fra overvejelse.
For at lĂžse vores problem er algoritmen til at identificere forbundne komponenter og minimum spanning tree-algoritmen mere egnede, men som det viste sig, kan de ikke anvendes "head-on" pĂ„ det problem, der skal lĂžses, og opnĂ„ en god lĂžsning. For at forklare dette, lad os overveje logikken i driften af ââsĂ„danne algoritmer i forhold til vores problem.
Overvej grafen 
, hvor hjÞrnerne er sÊttet af partier 
, og kanten mellem hjÞrnerne 
О 
har en vÊgt svarende til forskellen pÄ dage mellem batch 
О 
. I algoritmen til at identificere tilsluttede komponenter er inputparameteren angivet 
Hvor 
, og i grafen 
alle kanter, hvor vÊgten er stÞrre, fjernes 
. Kun de nÊrmeste par af objekter forbliver forbundet. Pointen med algoritmen er at vÊlge en sÄdan vÊrdi 
, hvor grafen "falder fra hinanden" i flere forbundne komponenter, hvor parterne, der tilhÞrer disse komponenter, vil opfylde vores lighedskriterium, bestemt af konstanten 
. De resulterende komponenter er klynger.
MinimumspÊndingstrÊ-algoritmen bygger fÞrst pÄ en graf 
minimum spanning tree, og derefter sekventielt fjerner kanter med den hÞjeste vÊgt, indtil grafen "falder fra hinanden" i flere forbundne komponenter, hvor parterne, der tilhÞrer disse komponenter, ogsÄ vil opfylde vores lighedskriterium. De resulterende komponenter vil vÊre klynger.
NÄr man bruger sÄdanne algoritmer til at lÞse det pÄgÊldende problem, kan der opstÄ en situation som i figur 3.
Fig. 3. Anvendelse af klyngealgoritmer til det problem, der skal lĂžses
Lad os sige, at vores konstant for forskellen mellem batchdage er 20 dage. Kurve 
blev afbildet i rumlig form for at lette visuel opfattelse. Begge algoritmer producerede en 3-klynge lĂžsning, som nemt kan forbedres ved at kombinere batchene placeret i separate klynger med hinanden! Det er indlysende, at sĂ„danne algoritmer skal modificeres for at passe til det specifikke problem, der lĂžses, og deres anvendelse i sin rene form til lĂžsningen af ââvores problem vil give dĂ„rlige resultater.
SÄ fÞr vi begyndte at skrive kode til grafalgoritmer modificeret til vores opgave og genopfinde vores egen cykel (i hvis silhuetter vi allerede kunne skelne konturerne af firkantede hjul), besluttede vi igen at nÊrme os et sÄdant problem videnskabeligt, nemlig: prÞv at reducere det til en anden diskret problemoptimering i hÄb om, at eksisterende algoritmer til at lÞse det kan anvendes uden Êndringer.
Endnu en sĂžgning efter et lignende klassisk problem har vĂŠret vellykket! Det lykkedes os at finde et diskret optimeringsproblem, hvis formulering falder 1 i 1 sammen med formuleringen af ââvores problem. Denne opgave viste sig at vĂŠre sĂŠt dĂŠkningsproblem. Lad os prĂŠsentere problemformuleringen i forhold til vores detaljer.
Der er et begrÊnset sÊt 
og familie 
af alle dets usammenhÊngende delmÊngder af parter, sÄledes at forskellen i datoer for alle par af parter i hver delmÊngde 
fra familien 
ikke overstiger konstanter 
. En dÊkning kaldes en familie 
af den mindste magt, hvis elementer hÞrer til 
, sĂ„dan at foreningen af ââsĂŠt 
fra familien 
bÞr give sÊt af alle parter 
.
En detaljeret analyse af dette problem kan findes Đž Andre muligheder for den praktiske anvendelse af dĂŠkningsproblemet og dets modifikationer kan findes
Algoritme til at lĂžse problemet
Vi har besluttet os for den matematiske model for det problem, der skal lÞses. Lad os nu se pÄ algoritmen til at lÞse det. UndersÊt 
fra familien 
kan nemt findes ved fĂžlgende procedure.
- Arranger batches fra et sĂŠt
i faldende rĂŠkkefĂžlge efter deres datoer. - Find minimum og maksimum batchdatoer.
- For hver dag fra minimumsdatoen til maksimum, find alle batches, hvis datoer afviger fra ikke mere end (altsÄ vÊrdien Det er bedre at tage det lige tal).
i faldende rÊkkefÞlge efter deres datoer.
fra minimumsdatoen til maksimum, find alle batches, hvis datoer afviger fra 
ikke mere end 
(altsÄ vÊrdien 
Det er bedre at tage det lige tal). Logikken i proceduren til at danne en familie af sÊt 
ĐżŃĐž 
dage er vist i figur 4.
Fig.4. Dannelse af undergrupper af partier
Denne procedure er ikke nÞdvendig for alle 
gÄ gennem alle andre batches og kontroller forskellen i deres datoer eller fra den aktuelle vÊrdi 
flyt til venstre eller hÞjre, indtil du finder en batch, hvis dato er forskellig fra 
med mere end halvdelen af ââvĂŠrdien af ââkonstanten. Alle efterfĂžlgende elementer, nĂ„r de flyttes bĂ„de til hĂžjre og venstre, vil ikke vĂŠre interessante for os, da forskellen i dage kun vil stige for dem, da elementerne i arrayet oprindeligt blev bestilt. Denne tilgang vil betydeligt spare tid, nĂ„r antallet af fester og spredningen af ââderes datoer er vĂŠsentligt stort.
SÊttets dÊkningsproblem er 
-svÊrt, hvilket betyder, at der ikke er nogen hurtig (med driftstid svarende til et polynomium af inputdataene) og nÞjagtig algoritme til at lÞse det. Derfor blev der valgt en hurtig grÄdig algoritme for at lÞse det sÊt dÊkkende problem, som selvfÞlgelig ikke er nÞjagtig, men har fÞlgende fordele:
- For smĂ„ problemer (og det er netop vores tilfĂŠlde) beregner den lĂžsninger, der er ret tĂŠt pĂ„ det optimale. EfterhĂ„nden som problemets stĂžrrelse Ăžges, forringes kvaliteten af ââlĂžsningen, men stadig ret langsomt;
- Meget let at implementere;
- Hurtig, da dens kĂžretidsestimat er .
.Den grÄdige algoritme udvÊlger sÊt baseret pÄ fÞlgende regel: PÄ hvert trin vÊlges et sÊt, der dÊkker det maksimale antal elementer, der endnu ikke er dÊkket. En detaljeret beskrivelse af algoritmen og dens pseudokode kan findes
En sammenligning af nĂžjagtigheden af ââen sĂ„dan grĂ„dig algoritme pĂ„ testdata af problemet, der lĂžses, med andre kendte algoritmer, sĂ„som den sandsynlige grĂ„dige algoritme, myrekolonialgoritmen osv., er ikke blevet foretaget. Resultaterne af at sammenligne sĂ„danne algoritmer pĂ„ genererede tilfĂŠldige data kan findes
Implementering og implementering af algoritmen
Denne algoritme blev implementeret i sproget 1ĐĄ og indgik i en ekstern behandling kaldet "Residue Compression", som var forbundet med WMS-system. Vi implementerede ikke algoritmen i sproget C++ og brug det fra en ekstern Native-komponent, hvilket ville vĂŠre mere korrekt, da kodens hastighed er lavere C + + gange og i nogle eksempler endda titusinder gange hurtigere end hastigheden af ââlignende kode pĂ„ 1ĐĄ. PĂ„ tungen 1ĐĄ Algoritmen blev implementeret for at spare udviklingstid og nem fejlfinding i kundens produktionsbase. Resultatet af algoritmen er vist i figur 5.
Fig.5. Behandling for at "komprimere" rester
Figur 5 viser, at i det angivne lager er de aktuelle saldi af varer i lagerceller opdelt i klynger, inden for hvilke datoerne for varepartierne afviger fra hinanden med hÞjst 30 dage. Da kunden producerer og opbevarer metalkugleventiler pÄ lageret, hvis holdbarhed er beregnet i Är, kan en sÄdan datoforskel negligeres. BemÊrk, at en sÄdan forarbejdning i Þjeblikket bruges systematisk i produktion og operatÞrer WMS bekrÊfte den gode kvalitet af festklynger.
Konklusioner og fortsĂŠttelse
Den vigtigste erfaring, vi fik fra at lĂžse et sĂ„dant praktisk problem, er bekrĂŠftelse af effektiviteten af ââat bruge paradigmet: matematik. problemformulering 
berÞmt mÄtte. model 
berÞmte algoritme 
algoritme, der tager hÞjde for problemets detaljer. Diskret optimering har eksisteret i mere end 300 Är, og i lÞbet af denne tid har folk formÄet at overveje en masse problemer og akkumulere en masse erfaring med at lÞse dem. FÞrst og fremmest er det mere tilrÄdeligt at vende sig til denne oplevelse, og fÞrst derefter begynde at genopfinde dit hjul.
I den nÊste artikel vil vi fortsÊtte historien om optimeringsalgoritmer og se pÄ det mest interessante og meget mere komplekse: en algoritme til optimal "komprimering" af cellerester, som bruger data modtaget fra batch-klyngealgoritmen som input.
Forberedte artiklen
Roman Shangin, programmĂžr for projektafdelingen,
FĂžrste BIT-selskab, Chelyabinsk
Kilde: www.habr.com
