ProHoster > blog > internetnieuws > Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn

In het artikel wordt beschreven hoe u dit kunt implementeren WMS-systeem werden we geconfronteerd met de noodzaak om een ​​niet-standaard clusterprobleem op te lossen en welke algoritmen we gebruikten om dit op te lossen. We zullen u vertellen hoe we een systematische, wetenschappelijke aanpak hebben toegepast om het probleem op te lossen, welke moeilijkheden we tegenkwamen en welke lessen we hebben geleerd.

Deze publicatie vormt het begin van een reeks artikelen waarin we onze succesvolle ervaring delen met het implementeren van optimalisatie-algoritmen in magazijnprocessen. Het doel van de serie artikelen is om het publiek kennis te laten maken met de soorten optimalisatieproblemen van magazijnoperaties die zich voordoen in vrijwel elk middelgroot en groot magazijn, en om te vertellen over onze ervaringen met het oplossen van dergelijke problemen en de valkuilen die we onderweg tegenkomen. . De artikelen zullen nuttig zijn voor degenen die in de magazijnlogistiek werken, implementeren WMS-systemen, maar ook programmeurs die geïnteresseerd zijn in toepassingen van wiskunde in het bedrijfsleven en de optimalisatie van processen in een onderneming.

Knelpunt in processen

In 2018 hebben we een project afgerond dat we moesten implementeren WMS-systemen in het magazijn van het bedrijf “Trading House “LD” in Tsjeljabinsk. We hebben het product “1C-Logistics: Warehouse Management 3” geïmplementeerd voor 20 werkplekken: operators WMS, winkeliers, heftruckchauffeurs. Het gemiddelde magazijn is ongeveer 4 m2 groot, het aantal cellen is 5000 en het aantal SKU's is 4500. In het magazijn worden kogelkranen uit eigen productie opgeslagen in verschillende maten van 1 kg tot 400 kg. De voorraad in het magazijn wordt in batches opgeslagen, omdat het nodig is goederen te selecteren op basis van FIFO.

Bij het ontwerpen van automatiseringsschema's voor magazijnprocessen werden we geconfronteerd met het bestaande probleem van niet-optimale voorraadopslag. De specifieke kenmerken van opslag- en stuwkranen zijn zodanig dat één opslagcel slechts artikelen uit één batch kan bevatten. Dagelijks arriveren producten in het magazijn en elke aankomst is een aparte batch. In totaal worden als resultaat van 1 maand magazijngebruik 30 afzonderlijke batches gecreëerd, ondanks het feit dat ze allemaal in een aparte cel moeten worden opgeslagen. Producten worden vaak niet in hele pallets geselecteerd, maar in stukken, en als gevolg daarvan wordt in veel cellen in de stukselectiezone het volgende beeld waargenomen: in een cel met een volume van meer dan 1 m3 staan ​​verschillende stukken kranen die nemen minder dan 5-10% van het celvolume in beslag.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn Fig 1. Foto van verschillende goederen in een cel

Het is duidelijk dat de opslagcapaciteit niet optimaal wordt benut. Om me de omvang van de ramp voor te stellen, kan ik cijfers geven: gemiddeld zijn er 1 tot 3 cellen van dergelijke cellen met een volume van meer dan 100 m300 met ‘minuscule’ balansen tijdens verschillende perioden van de werking van het magazijn. Omdat het magazijn relatief klein is, wordt deze factor tijdens de drukke seizoenen een “knelpunt” en vertraagt ​​dit de magazijnprocessen aanzienlijk.

Probleem oplossing idee

Er ontstond een idee: batches restjes met de dichtstbijzijnde data zouden moeten worden teruggebracht tot één enkele batch, en dergelijke restjes met een verenigde batch zouden compact samen in één cel moeten worden geplaatst, of in meerdere, als er niet genoeg ruimte in één is om de hele hoeveelheid restjes.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn
Fig. 2. Schema voor het comprimeren van residuen in cellen

Hierdoor kunt u de bezette magazijnruimte die wordt gebruikt voor het plaatsen van nieuwe goederen aanzienlijk verminderen. In een situatie waarin de magazijncapaciteit overbelast is, is een dergelijke maatregel uiterst noodzakelijk, omdat er anders eenvoudigweg niet voldoende vrije ruimte is om nieuwe goederen te huisvesten, wat zal leiden tot een stop in de magazijnplaatsings- en bevoorradingsprocessen. Eerder vóór de implementatie WMS-systems voerden deze handeling handmatig uit, wat niet effectief was, omdat het zoeken naar geschikte residuen in de cellen vrij lang duurde. Nu we met de introductie van een WMS-systeem hebben besloten om het proces te automatiseren, te versnellen en intelligent te maken.

Het proces om een ​​dergelijk probleem op te lossen is verdeeld in 2 fasen:

  • in de eerste fase vinden we groepen batches die qua datum bijna klaar zijn voor compressie;
  • in de tweede fase berekenen we voor elke groep batches de meest compacte plaatsing van de resterende goederen in de cellen.

In het huidige artikel zullen we ons concentreren op de eerste fase van het algoritme en de tweede fase overlaten aan het volgende artikel.

Zoek naar een wiskundig model van het probleem

Voordat we aan de slag gingen om code te schrijven en ons wiel opnieuw uit te vinden, besloten we dit probleem wetenschappelijk te benaderen, namelijk: het wiskundig te formuleren, het terug te brengen tot een bekend discreet optimalisatieprobleem en effectieve bestaande algoritmen te gebruiken om het op te lossen, of om deze bestaande algoritmen te nemen als basis en pas ze aan aan de specifieke kenmerken van het praktische probleem dat wordt opgelost.

Omdat uit de zakelijke formulering van het probleem duidelijk volgt dat we met verzamelingen te maken hebben, zullen we een dergelijk probleem formuleren in termen van de verzamelingenleer.

Laten Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn – de verzameling van alle batches van de rest van een bepaald product in een magazijn. Laten Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn – gegeven constante van dagen. Laten Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn – een subset van batches, waarbij het verschil in data voor alle paren batches in de subset een constante niet overschrijdt Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. We moeten het minimum aantal disjuncte deelverzamelingen vinden Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn, zodat alle subsets Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn bij elkaar genomen zou veel opleveren Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn.

Met andere woorden, we moeten groepen of clusters van soortgelijke partijen vinden, waarbij het gelijkheidscriterium wordt bepaald door de constante Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. Deze taak herinnert ons aan het bekende clusterprobleem. Het is belangrijk om te zeggen dat het beschouwde probleem verschilt van het clusterprobleem doordat ons probleem een ​​strikt gedefinieerde voorwaarde heeft voor het criterium van gelijkenis van clusterelementen, bepaald door de constante Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn, maar bij het clusterprobleem bestaat een dergelijke voorwaarde niet. De verklaring van het clusterprobleem en informatie over dit probleem zijn te vinden here.

We zijn er dus in geslaagd het probleem te formuleren en een klassiek probleem met een vergelijkbare formulering te vinden. Nu is het noodzakelijk om bekende algoritmen te overwegen om het probleem op te lossen, om niet het wiel opnieuw uit te vinden, maar om de beste praktijken te gebruiken en deze toe te passen. Om het clusterprobleem op te lossen, hebben we de meest populaire algoritmen overwogen, namelijk: Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn-middelen, Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn-middelen, algoritme voor het identificeren van verbonden componenten, minimaal spanning tree-algoritme. Een beschrijving en analyse van dergelijke algoritmen is te vinden here.

Om ons probleem op te lossen, clusteren we algoritmen Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn-betekent en Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn-middelen zijn helemaal niet van toepassing, omdat het aantal clusters nooit vooraf bekend is Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn en dergelijke algoritmen houden geen rekening met de constante beperking van het aantal dagen. Dergelijke algoritmen werden aanvankelijk buiten beschouwing gelaten.
Om ons probleem op te lossen zijn het algoritme voor het identificeren van verbonden componenten en het minimum spanning tree-algoritme geschikter, maar het bleek dat ze niet ‘frontaal’ kunnen worden toegepast op het probleem dat wordt opgelost en een goede oplossing kunnen opleveren. Laten we, om dit uit te leggen, eens kijken naar de werkingslogica van dergelijke algoritmen in relatie tot ons probleem.

Beschouw de grafiek Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn, waarin de hoekpunten de verzameling partijen zijn Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijnen de rand tussen de hoekpunten Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn и Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn heeft een gewicht dat gelijk is aan het verschil in dagen tussen batches Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn и Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. In het algoritme voor het identificeren van aangesloten componenten wordt de invoerparameter gespecificeerd Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijnWaar Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijnen in de grafiek Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn alle randen waarvoor het gewicht groter is, worden verwijderd Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. Alleen de dichtstbijzijnde paren objecten blijven verbonden. Het doel van het algoritme is om een ​​dergelijke waarde te selecteren Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn, waarin de grafiek “uit elkaar valt” in verschillende verbonden componenten, waarbij de partijen die tot deze componenten behoren zullen voldoen aan ons gelijkheidscriterium, bepaald door de constante Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. De resulterende componenten zijn clusters.

Het minimum spanning tree-algoritme bouwt eerst voort op een grafiek Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn minimaal opspannende boom, en verwijdert vervolgens achtereenvolgens randen met het hoogste gewicht totdat de grafiek “uit elkaar valt” in verschillende verbonden componenten, waarbij de partijen die tot deze componenten behoren ook aan ons gelijkheidscriterium zullen voldoen. De resulterende componenten zullen clusters zijn.

Wanneer dergelijke algoritmen worden gebruikt om het beschouwde probleem op te lossen, kan zich een situatie voordoen zoals in figuur 3.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn
Figuur 3. Toepassing van clusteralgoritmen op het probleem dat wordt opgelost

Laten we zeggen dat onze constante voor het verschil tussen batchdagen 20 dagen is. Grafiek Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn werd afgebeeld in ruimtelijke vorm voor een gemakkelijke visuele waarneming. Beide algoritmen leverden een oplossing met 3 clusters op, die eenvoudig kan worden verbeterd door de batches die in afzonderlijke clusters zijn geplaatst met elkaar te combineren! Het is duidelijk dat dergelijke algoritmen moeten worden aangepast aan de specifieke kenmerken van het probleem dat wordt opgelost, en de toepassing ervan in zijn pure vorm op de oplossing van ons probleem zal slechte resultaten opleveren.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn
Dus voordat we begonnen met het schrijven van code voor grafiekalgoritmen die voor onze taak waren aangepast en het opnieuw uitvinden van onze eigen fiets (in de silhouetten waarvan we al de contouren van vierkante wielen konden onderscheiden), besloten we opnieuw een dergelijk probleem wetenschappelijk te benaderen, namelijk: probeer het terug te brengen tot een andere discrete probleemoptimalisatie, in de hoop dat bestaande algoritmen om het op te lossen zonder aanpassingen kunnen worden toegepast.

Een andere zoektocht naar een soortgelijk klassiek probleem is succesvol gebleken! We zijn erin geslaagd een discreet optimalisatieprobleem te vinden, waarvan de formulering 1 op 1 samenvalt met de formulering van ons probleem. Deze taak bleek te zijn dekkingsprobleem instellen. Laten we de formulering van het probleem presenteren in relatie tot onze specifieke kenmerken.

Er is een eindige verzameling Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn en familie Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van al zijn onsamenhangende subsets van partijen, zodat het verschil in data voor alle paren partijen van elke subset Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van de familie Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn constanten niet overschrijdt Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn. Een bedekking wordt een familie genoemd Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van de minste macht, waartoe de elementen behoren Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn, zodat de vereniging van verzamelingen Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van de familie Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn moet de set van alle partijen geven Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn.

Een gedetailleerde analyse van dit probleem is te vinden hier и here. Er zijn andere opties voor de praktische toepassing van het overkoepelende probleem en de wijzigingen ervan here.

Algoritme voor het oplossen van het probleem

We hebben besloten welk wiskundig model het probleem moet oplossen. Laten we nu eens kijken naar het algoritme om dit op te lossen. Subsets Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van de familie Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn kunt u eenvoudig vinden via de volgende procedure.

  1. Rangschik batches uit een set Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn in aflopende volgorde van hun data.
  2. Zoek de minimale en maximale batchdatums.
  3. Voor elke dag Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn van de minimumdatum tot de maximumdatum, vind alle batches waarvan de datums afwijken Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn maximaal Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn (dus de waarde Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn Het is beter om het even getal te nemen).

Logica van de procedure voor het vormen van een familie van sets Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn bij Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn dagen wordt weergegeven in Figuur 4.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn
Afb.4. Vorming van subsets van partijen

Deze procedure is niet voor iedereen noodzakelijk Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn doorloop alle andere batches en controleer het verschil in hun datums, of ten opzichte van de huidige waarde Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn beweeg naar links of rechts totdat u een batch vindt waarvan de datum afwijkt Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn met meer dan de helft van de waarde van de constante. Alle volgende elementen zullen, wanneer ze zowel naar rechts als naar links bewegen, niet interessant voor ons zijn, omdat voor hen het verschil in dagen alleen maar zal toenemen, aangezien de elementen in de array aanvankelijk waren geordend. Deze aanpak zal aanzienlijk tijd besparen wanneer het aantal feesten en de spreiding van hun data aanzienlijk groot zijn.

Het setdekkingsprobleem is Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn-moeilijk, wat betekent dat er geen snel (met werkingstijd gelijk aan een polynoom van de invoergegevens) en nauwkeurig algoritme is om het op te lossen. Om het setdekkingsprobleem op te lossen, werd daarom gekozen voor een snel hebzuchtig algoritme, dat uiteraard niet nauwkeurig is, maar de volgende voordelen heeft:

  • Voor kleine problemen (en dit is precies ons geval) berekent het oplossingen die vrij dicht bij het optimale liggen. Naarmate de omvang van het probleem toeneemt, gaat de kwaliteit van de oplossing achteruit, maar nog steeds vrij langzaam;
  • Zeer eenvoudig te implementeren;
  • Snel, omdat de geschatte looptijd dat is Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn.

Het hebzuchtige algoritme selecteert sets op basis van de volgende regel: in elke fase wordt een set geselecteerd die het maximale aantal nog niet gedekte elementen omvat. Een gedetailleerde beschrijving van het algoritme en zijn pseudocode kunt u vinden here.

Een vergelijking van de nauwkeurigheid van een dergelijk hebzuchtig algoritme op testgegevens van het probleem dat wordt opgelost met andere bekende algoritmen, zoals het probabilistische hebzuchtige algoritme, het mierenkolonie-algoritme, enz., is niet gemaakt. De resultaten van het vergelijken van dergelijke algoritmen op gegenereerde willekeurige gegevens kunnen worden gevonden op het werk.

Implementatie en implementatie van het algoritme

Dit algoritme is in de taal geïmplementeerd 1S en was opgenomen in een externe verwerking genaamd "Residu Compression" waarmee verbonden was WMS-systeem. We hebben het algoritme niet in de taal geïmplementeerd C ++ en gebruik het vanuit een externe Native component, wat correcter zou zijn, omdat de snelheid van de code lager is C + + keer en in sommige voorbeelden zelfs tientallen keren sneller dan de snelheid van vergelijkbare code 1S. Op de tong 1S Het algoritme werd geïmplementeerd om ontwikkelingstijd en foutopsporing op de productiebasis van de klant te besparen. Het resultaat van het algoritme wordt weergegeven in Figuur 5.

Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn
Afb.5. Verwerking om resten te “comprimeren”.

Figuur 5 laat zien dat in het opgegeven magazijn de actuele goederensaldi in de opslagcellen zijn opgedeeld in clusters, waarbinnen de data van de goederenbatches maximaal 30 dagen van elkaar verschillen. Omdat de klant in het magazijn metalen kogelkranen produceert en opslaat, waarvan de houdbaarheid in jaren wordt berekend, kan een dergelijk datumverschil worden verwaarloosd. Merk op dat een dergelijke verwerking momenteel systematisch wordt gebruikt in de productie en bij operators WMS bevestigen de goede kwaliteit van de partijclustering.

Conclusies en vervolg

De belangrijkste ervaring die we hebben opgedaan bij het oplossen van een dergelijk praktisch probleem is de bevestiging van de effectiviteit van het gebruik van het paradigma: wiskunde. Probleemstelling Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn beroemde mat. model Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn beroemd algoritme Discrete wiskunde bij de implementatie van een WMS-systeem: clustering van batches goederen in een magazijn algoritme dat rekening houdt met de specifieke kenmerken van het probleem. Discrete optimalisatie bestaat al meer dan 300 jaar en gedurende deze tijd zijn mensen erin geslaagd veel problemen te overwegen en veel ervaring op te doen met het oplossen ervan. Allereerst is het beter om van deze ervaring gebruik te maken en pas daarna het wiel opnieuw uit te vinden.

In het volgende artikel gaan we verder met het verhaal over optimalisatie-algoritmen en kijken we naar het meest interessante en veel complexere: een algoritme voor optimale ‘compressie’ van celresten, dat gegevens gebruikt die zijn ontvangen van het batchclusteringalgoritme als invoer.

Het artikel voorbereid
Roman Shangin, programmeur van de projectenafdeling,
Eerste BIT-bedrijf, Tsjeljabinsk

Bron: www.habr.com

Voeg een reactie