Artikeln beskriver hur man implementerar WMS-system stod vi inför behovet av att lösa ett icke-standardiserat klustringsproblem och vilka algoritmer vi använde för att lösa det. Vi kommer att berätta hur vi tillämpade ett systematiskt, vetenskapligt tillvägagångssätt för att lösa problemet, vilka svårigheter vi stötte på och vilka lärdomar vi lärde oss.
Denna publikation inleder en serie artiklar där vi delar vår framgångsrika erfarenhet av att implementera optimeringsalgoritmer i lagerprocesser. Syftet med artikelserien är att bekanta publiken med de typer av optimeringsproblem av lagerdrift som uppstår i nästan alla medelstora och stora lager, samt att berätta om vår erfarenhet av att lösa sådana problem och de fallgropar man stöter på på vägen. . Artiklarna kommer att vara användbara för dem som arbetar inom lagerlogistikbranschen, implementera WMS-system, samt programmerare som är intresserade av tillämpningar av matematik i företag och optimering av processer i ett företag.
Flaskhals i processer
Under 2018 slutförde vi ett projekt att genomföra WMS-system på lagret för företaget "Trading House "LD" i Chelyabinsk. Vi implementerade produkten "1C-Logistics: Warehouse Management 3" för 20 arbetsplatser: operatörer WMS, lagerhållare, truckförare. Det genomsnittliga lagret är cirka 4 tusen m2, antalet celler är 5000 och antalet SKU:er är 4500. Lagret lagrar kulventiler av vår egen produktion av olika storlekar från 1 kg till 400 kg. Inventarier på lagret lagras i partier, eftersom det finns behov av att välja varor enligt FIFO.
När vi utformade system för automatisering av lagerprocesser stod vi inför det befintliga problemet med icke-optimal lagerlagring. Det specifika med lagring och stuvning av kranar är sådana att en enhetslagringscell endast kan innehålla föremål från en batch. Produkterna kommer till lagret dagligen och varje ankomst är en separat batch. Totalt, som ett resultat av 1 månads lagerdrift, skapas 30 separata batcher, trots att var och en ska lagras i en separat cell. Produkter väljs ofta inte i hela pallar, utan i stycken, och som ett resultat, i styckevalszonen i många celler observeras följande bild: i en cell med en volym på mer än 1 m3 finns det flera delar av kranar som upptar mindre än 5-10 % av cellvolymen.
Fig 1. Foto av flera varor i en cell
Det är tydligt att lagringskapaciteten inte utnyttjas optimalt. För att föreställa mig katastrofens omfattning kan jag ge siffror: i genomsnitt finns det från 1 till 3 celler av sådana celler med en volym på mer än 100 m300 med "minuscula" balanser under olika perioder av lagrets drift. Eftersom lagret är relativt litet, blir denna faktor en "flaskhals" under de hektiska säsongerna i lagret och bromsar kraftigt lagerprocesserna.
Problemlösning idé
En idé uppstod: partier av rester med närmast datum bör reduceras till en enda batch, och sådana rester med en enhetlig batch bör placeras kompakt tillsammans i en cell, eller i flera, om det inte finns tillräckligt med utrymme i en för att rymma hela mängden rester.
Fig.2. Schema för att komprimera rester i celler
Detta gör att du avsevärt kan minska det upptagna lagerutrymmet som kommer att användas för nya varor som placeras. I en situation där lagerkapaciteten är överbelastad är en sådan åtgärd extremt nödvändig, annars kanske det helt enkelt inte finns tillräckligt med ledigt utrymme för att ta emot nya varor, vilket kommer att leda till ett stopp i lagerplacerings- och påfyllningsprocesserna. Tidigare innan implementering WMS-systems utförde denna operation manuellt, vilket var ineffektivt, eftersom processen att leta efter lämpliga rester i cellerna var ganska lång. Nu, med introduktionen av ett WMS-system, bestämde vi oss för att automatisera processen, påskynda den och göra den intelligent.
Processen för att lösa ett sådant problem är uppdelad i två steg:
- i det första steget hittar vi grupper av batcher nära datum för komprimering;
- i det andra steget, för varje grupp av partier, beräknar vi den mest kompakta placeringen av de återstående varorna i cellerna.
I den aktuella artikeln kommer vi att fokusera på det första steget av algoritmen och lämna täckning av det andra steget för nästa artikel.
Sök efter en matematisk modell av problemet
Innan vi satte oss ner för att skriva kod och återuppfinna vårt hjul, bestämde vi oss för att närma oss detta problem vetenskapligt, nämligen: formulera det matematiskt, reducera det till ett välkänt diskret optimeringsproblem och använda effektiva befintliga algoritmer för att lösa det, eller ta dessa befintliga algoritmer som grund och modifiera dem till detaljerna i det praktiska problem som löses.
Eftersom det tydligt följer av problemformuleringen att vi har att göra med mängder kommer vi att formulera ett sådant problem i termer av mängdlära.
låt – uppsättningen av alla partier av resten av en viss produkt i ett lager. Låta – given konstant av dagar. Låta – en delmängd av satser, där skillnaden i datum för alla par av satser i delmängden inte överstiger en konstant . Vi måste hitta det minsta antalet disjunkta delmängder , så att alla delmängder tillsammans skulle ge många .
Med andra ord måste vi hitta grupper eller kluster av liknande partier, där likhetskriteriet bestäms av konstanten . Denna uppgift påminner oss om det välkända klustringsproblemet. Det är viktigt att säga att det aktuella problemet skiljer sig från klusterproblemet genom att vårt problem har ett strikt definierat villkor för kriteriet om likhet mellan klusterelement, bestämt av konstanten , men i klustringsproblemet finns inget sådant tillstånd. Redogörelsen för klustringsproblemet och information om detta problem kan hittas
Så vi lyckades formulera problemet och hitta ett klassiskt problem med en liknande formulering. Nu är det nödvändigt att överväga välkända algoritmer för att lösa det, för att inte uppfinna hjulet på nytt, utan för att ta de bästa metoderna och tillämpa dem. För att lösa klustringsproblemet övervägde vi de mest populära algoritmerna, nämligen: -betyder att, -medel, algoritm för att identifiera anslutna komponenter, minimum spaning tree-algoritm. En beskrivning och analys av sådana algoritmer kan hittas
För att lösa vårt problem, klustringsalgoritmer - betyder och -medel är inte tillämpliga alls, eftersom antalet kluster aldrig är känt i förväg och sådana algoritmer tar inte hänsyn till begränsningen för konstanta dagar. Sådana algoritmer förkastades från början.
För att lösa vårt problem är algoritmen för att identifiera anslutna komponenter och algoritmen för minimum spaning tree mer lämpliga, men, som det visade sig, kan de inte appliceras "head-on" på problemet som ska lösas och få en bra lösning. För att förklara detta, låt oss överväga driftlogiken för sådana algoritmer i förhållande till vårt problem.
Tänk på grafen , där hörnen är uppsättningen av partier , och kanten mellan hörnen и har en vikt som är lika med skillnaden mellan dagar mellan batcher и . I algoritmen för att identifiera anslutna komponenter anges ingångsparametern var , och i grafen alla kanter för vilka vikten är större tas bort . Endast de närmaste objektparen förblir anslutna. Poängen med algoritmen är att välja ett sådant värde , där grafen "faller isär" i flera sammankopplade komponenter, där parterna som tillhör dessa komponenter kommer att uppfylla vårt likhetskriterium, bestämt av konstanten . De resulterande komponenterna är kluster.
Algoritmen för minsta spännträd bygger först på en graf minimum spaning tree, och tar sedan sekventiellt bort kanter med högst vikt tills grafen "faller isär" i flera sammankopplade komponenter, där parterna som tillhör dessa komponenter också kommer att uppfylla vårt likhetskriterium. De resulterande komponenterna kommer att vara kluster.
När man använder sådana algoritmer för att lösa det aktuella problemet kan en situation uppstå som i figur 3.
Fig 3. Tillämpning av klustringsalgoritmer på det problem som ska lösas
Låt oss säga att vår konstant för skillnaden mellan batchdagar är 20 dagar. Graf avbildades i rumslig form för att underlätta visuell uppfattning. Båda algoritmerna producerade en 3-klusterlösning, som enkelt kan förbättras genom att kombinera satserna placerade i separata kluster med varandra! Det är uppenbart att sådana algoritmer måste modifieras för att passa specifikationerna för det problem som löses, och deras tillämpning i sin rena form för att lösa vårt problem kommer att ge dåliga resultat.
Så innan vi började skriva kod för grafalgoritmer modifierade för vår uppgift och återuppfinna vår egen cykel (i vars silhuetter vi redan kunde urskilja konturerna av fyrkantiga hjul), bestämde vi oss återigen för att närma oss ett sådant problem vetenskapligt, nämligen: försök att reducera det till en annan diskret problemoptimering, i hopp om att befintliga algoritmer för att lösa det kan tillämpas utan modifieringar.
En annan sökning efter ett liknande klassiskt problem har varit framgångsrik! Vi lyckades hitta ett diskret optimeringsproblem, vars formulering sammanfaller 1 i 1 med formuleringen av vårt problem. Denna uppgift visade sig vara ställtäckningsproblem. Låt oss presentera problemets formulering i förhållande till våra detaljer.
Det finns en ändlig uppsättning och familj av alla dess osammanhängande delmängder av parter, så att skillnaden i datum för alla par av parter i varje delmängd från familjen inte överstiger konstanterna . En täckning kallas en familj av den minsta makt, vars beståndsdelar tillhöra , så att föreningen av uppsättningar från familjen bör ge uppsättningen av alla parter .
En detaljerad analys av detta problem kan hittas и Andra alternativ för den praktiska tillämpningen av täckningsproblemet och dess modifieringar kan hittas
Algoritm för att lösa problemet
Vi har bestämt oss för den matematiska modellen av problemet som ska lösas. Låt oss nu titta på algoritmen för att lösa det. Delmängder från familjen kan lätt hittas genom följande procedur.
- Ordna partier från en uppsättning i fallande ordning efter datum.
- Hitta lägsta och högsta batchdatum.
- För varje dag från minimidatum till maximum, hitta alla batcher vars datum skiljer sig från inte mer än (alltså värdet Det är bättre att ta det jämna talet).
Logiken i proceduren för att bilda en familj av uppsättningar при dagar visas i figur 4.
Fig.4. Bildande av undergrupper av partier
Denna procedur är inte nödvändig för alla gå igenom alla andra batcher och kontrollera skillnaden i deras datum, eller från det aktuella värdet flytta åt vänster eller höger tills du hittar en batch vars datum är ett annat än med mer än hälften av konstantens värde. Alla efterföljande element, när de flyttas både till höger och till vänster, kommer inte att vara intressanta för oss, eftersom skillnaden i dagar bara kommer att öka för dem, eftersom elementen i arrayen ursprungligen beställdes. Detta tillvägagångssätt kommer avsevärt att spara tid när antalet fester och spridningen av deras datum är avsevärt stort.
Problemet med uppsättningen är -svårt, vilket innebär att det inte finns någon snabb (med drifttid lika med ett polynom av indata) och exakt algoritm för att lösa det. För att lösa uppsättningstäckningsproblemet valdes därför en snabb girig algoritm, som naturligtvis inte är korrekt, men har följande fördelar:
- För små problem (och detta är precis vårt fall) beräknar den lösningar som ligger ganska nära det optimala. När problemets storlek ökar försämras kvaliteten på lösningen, men ändå ganska långsamt;
- Mycket lätt att implementera;
- Snabbt, eftersom dess uppskattning av körtid är .
Den giriga algoritmen väljer uppsättningar baserat på följande regel: i varje steg väljs en uppsättning som täcker det maximala antalet element som ännu inte täcks. En detaljerad beskrivning av algoritmen och dess pseudokod kan hittas
En jämförelse av noggrannheten hos en sådan girig algoritm på testdata av problemet som löses med andra kända algoritmer, såsom den probabilistiska giriga algoritmen, myrkolonialgoritmen, etc., har inte gjorts. Resultaten av att jämföra sådana algoritmer på genererade slumpmässiga data kan hittas
Implementering och implementering av algoritmen
Denna algoritm implementerades i språket 1S och ingick i en extern bearbetning kallad "Residue Compression" som kopplades till WMS-systemet. Vi implementerade inte algoritmen i språket C++ och använd den från en extern Native-komponent, vilket skulle vara mer korrekt, eftersom kodens hastighet är lägre C + + gånger och i vissa exempel till och med tiotals gånger snabbare än hastigheten för liknande kod på 1S. På tungan 1S Algoritmen implementerades för att spara utvecklingstid och enkel felsökning i kundens produktionsbas. Resultatet av algoritmen presenteras i figur 5.
Fig. 5. Bearbetning för att "komprimera" rester
Figur 5 visar att i det angivna lagret är de aktuella saldonen av varor i lagerceller uppdelade i kluster, inom vilka datumen för varupartierna skiljer sig från varandra med högst 30 dagar. Eftersom kunden tillverkar och lagrar metallkulventiler i lagret, vars hållbarhet beräknas i år, kan en sådan datumskillnad negligeras. Observera att sådan bearbetning för närvarande används systematiskt i produktion och operatörer WMS bekräfta den goda kvaliteten på partiklustring.
Slutsatser och fortsättning
Den huvudsakliga erfarenheten som vi fick av att lösa ett sådant praktiskt problem är en bekräftelse på effektiviteten av att använda paradigmet: matematik. problemformulering berömd matta. modell berömd algoritm algoritm som tar hänsyn till problemets detaljer. Diskret optimering har funnits i mer än 300 år, och under denna tid har människor lyckats överväga många problem och samlat på sig mycket erfarenhet av att lösa dem. Först och främst är det mer tillrådligt att vända sig till den här upplevelsen och först därefter börja återuppfinna ditt hjul.
I nästa artikel kommer vi att fortsätta historien om optimeringsalgoritmer och titta på det mest intressanta och mycket mer komplexa: en algoritm för optimal "komprimering" av cellrester, som använder data som tas emot från batchklustringsalgoritmen som input.
Förberedde artikeln
Roman Shangin, programmerare på projektavdelningen,
Första BIT-företaget, Chelyabinsk
Källa: will.com