Článek popisuje, jak implementovat WMS-systému jsme stáli před potřebou vyřešit nestandardní problém shlukování a jaké algoritmy jsme k jeho řešení použili. Řekneme vám, jak jsme při řešení problému uplatnili systematický vědecký přístup, s jakými obtížemi jsme se setkali a jaká ponaučení jsme se naučili.
Tato publikace začíná sérii článků, ve kterých sdílíme naše úspěšné zkušenosti s implementací optimalizačních algoritmů ve skladových procesech. Účelem série článků je seznámit posluchače s typy optimalizačních problémů skladových operací, které vznikají téměř v každém středním a velkém skladu, a také vyprávět o našich zkušenostech s řešením těchto problémů a úskalích, s nimiž se na cestě setkáváme. . Články budou užitečné pro ty, kteří pracují v odvětví skladové logistiky, implementují WMS-systémy, ale i programátory, kteří se zajímají o aplikace matematiky v podnikání a optimalizaci procesů v podniku.
Úzké místo v procesech
V roce 2018 jsme dokončili projekt k realizaci WMS-systémy ve skladu společnosti “Trading House “LD” v Čeljabinsku. Implementovali jsme produkt „1C-Logistics: Warehouse Management 3“ pro 20 pracovišť: operátorů WMS, skladníci, řidiči vysokozdvižných vozíků. Průměrný sklad je cca 4 tisíce m2, počet článků 5000 a počet SKU 4500. Ve skladu jsou uloženy kulové kohouty vlastní výroby různých velikostí od 1 kg do 400 kg. Zásoby ve skladu jsou skladovány v dávkách, protože je potřeba vybírat zboží podle FIFO.
Při navrhování schémat automatizace skladových procesů jsme se potýkali s existujícím problémem neoptimálního skladování zásob. Specifika skladování a zakládání jeřábů jsou taková, že jedna jednotková skladová buňka může obsahovat pouze položky z jedné šarže. Produkty přicházejí na sklad denně a každý příchod je samostatná dávka. Celkem je v důsledku 1 měsíce skladového provozu vytvořeno 30 samostatných dávek, a to přesto, že by každá měla být uložena v samostatné buňce. Výrobky se často nevybírají v celých paletách, ale po kusech, a v důsledku toho je v zóně výběru kusů v mnoha buňkách pozorován následující obrázek: v buňce o objemu větším než 1 m3 je několik kusů jeřábů, které zabírají méně než 5-10 % objemu buňky.
Obr 1. Fotografie několika kusů zboží v buňce
Je zřejmé, že kapacita úložiště není využívána optimálně. Abych si představil rozsah katastrofy, mohu uvést čísla: v průměru se jedná o 1 až 3 buněk takových buněk o objemu větším než 100 m300 s „minimálními“ zůstatky v různých obdobích provozu skladu. Vzhledem k tomu, že sklad je relativně malý, stává se tento faktor během rušných období skladu „úzkým hrdlem“ a značně zpomaluje skladové procesy.
Nápad na řešení problému
Vznikl nápad: dávky zbytků s nejbližšími daty by se měly zredukovat na jednu dávku a takové zbytky se sjednocenou dávkou by se měly umístit kompaktně dohromady do jedné buňky nebo do několika, pokud v jedné není dostatek místa pro umístění celé množství zbytků.
Obr.2. Schéma pro kompresi zbytků v buňkách
To vám umožní výrazně snížit obsazený skladový prostor, který bude využit pro umístění nového zboží. V situaci, kdy je skladová kapacita přetížena, je takové opatření krajně nutné, jinak prostě nemusí být dostatek volného místa pro umístění nového zboží, což povede k zastavení procesů umisťování a doplňování skladu. Dříve před realizací WMS-systémy tuto operaci prováděly ručně, což bylo neúčinné, protože proces hledání vhodných zbytků v buňkách byl poměrně dlouhý. Nyní, se zavedením systému WMS, jsme se rozhodli proces automatizovat, zrychlit a učinit jej inteligentním.
Proces řešení takového problému je rozdělen do 2 fází:
- v první fázi najdeme skupiny dávek, které jsou časově blízké pro kompresi;
- ve druhé fázi vypočítáme pro každou skupinu dávek nejkompaktnější umístění zbývajícího zboží v buňkách.
V aktuálním článku se zaměříme na první fázi algoritmu a pokrytí druhé fáze si necháme na příští článek.
Hledejte matematický model problému
Než jsme se posadili k psaní kódu a znovu vynalezli naše kolo, rozhodli jsme se přistoupit k tomuto problému vědecky, konkrétně: formulovat jej matematicky, zredukovat jej na dobře známý problém diskrétní optimalizace a použít k jeho vyřešení účinné existující algoritmy, nebo použít tyto existující algoritmy. jako základ a upravovat je podle specifik řešeného praktického problému.
Protože z obchodní formulace problému jasně vyplývá, že se zabýváme množinami, zformulujeme takový problém z hlediska teorie množin.
Let – soubor všech šarží zbytku určitého produktu ve skladu. Nechat – daná konstanta dnů. Nechat – podmnožina dávek, kde rozdíl v datech pro všechny páry dávek v podmnožině nepřesahuje konstantu . Musíme najít minimální počet disjunktních podmnožin , takže všechny podmnožiny dohromady by dalo mnoho .
Jinými slovy, potřebujeme najít skupiny nebo shluky podobných stran, kde je kritérium podobnosti určeno konstantou . Tento úkol nám připomíná známý problém shlukování. Je důležité říci, že uvažovaný problém se liší od problému shlukování v tom, že náš problém má přesně definovanou podmínku pro kritérium podobnosti prvků shluku, určenou konstantou , ale v problému shlukování žádná taková podmínka neexistuje. Lze nalézt prohlášení o problému shlukování a informace o tomto problému
Podařilo se nám tedy zformulovat problém a najít klasický problém s podobnou formulací. Nyní je nutné zvážit dobře známé algoritmy pro jeho řešení, abychom znovu nevynalezli kolo, ale vzali osvědčené postupy a aplikovali je. Abychom vyřešili problém shlukování, zvážili jsme nejoblíbenější algoritmy, konkrétně: -prostředek, -prostředky, algoritmus pro identifikaci připojených komponent, algoritmus minimálního spanning tree. Popis a analýzu takových algoritmů lze nalézt
Chcete-li vyřešit náš problém, shlukovací algoritmy - znamená a -prostředky nejsou vůbec použitelné, protože počet shluků není nikdy předem znám a takové algoritmy neberou v úvahu konstantní omezení dnů. Takové algoritmy byly původně vyřazeny z úvahy.
K vyřešení našeho problému je vhodnější algoritmus pro identifikaci připojených komponent a algoritmus minimálního spanning tree, ale jak se ukázalo, nelze je aplikovat „přímo“ na řešený problém a získat dobré řešení. Abychom to vysvětlili, podívejme se na logiku fungování takových algoritmů ve vztahu k našemu problému.
Zvažte graf , ve kterém jsou vrcholy množinou stran a hrana mezi vrcholy и má váhu rovnou rozdílu dnů mezi dávkami и . V algoritmu pro identifikaci připojených komponent je specifikován vstupní parametr Kde a v grafu všechny hrany, u kterých je hmotnost větší, jsou odstraněny . Spojeny zůstávají pouze nejbližší dvojice objektů. Smyslem algoritmu je vybrat takovou hodnotu , ve kterém se graf „rozpadne“ na několik propojených komponent, přičemž strany patřící do těchto komponent splní naše kritérium podobnosti, určené konstantou . Výsledné komponenty jsou shluky.
Algoritmus minimálního spanning tree nejprve staví na grafu minimální kostru a poté postupně odstraňuje hrany s nejvyšší váhou, dokud se graf „nerozpadne“ na několik spojených komponent, kde strany patřící do těchto komponent také splní naše kritérium podobnosti. Výsledné komponenty budou shluky.
Při použití takových algoritmů k řešení uvažovaného problému může nastat situace jako na obrázku 3.
Obr. 3. Aplikace shlukovacích algoritmů na řešený problém
Řekněme, že naše konstanta pro rozdíl mezi dávkovými dny je 20 dnů. Graf byl zobrazen v prostorové formě pro snadné vizuální vnímání. Oba algoritmy vytvořily 3-klastrové řešení, které lze snadno vylepšit vzájemným zkombinováním dávek umístěných v samostatných shlucích! Je zřejmé, že takovéto algoritmy je třeba upravit tak, aby vyhovovaly specifikům řešeného problému, a jejich aplikace v čisté podobě na řešení našeho problému bude dávat špatné výsledky.
Než jsme tedy začali psát kód pro grafové algoritmy upravené pro náš úkol a znovu vynalézat vlastní jízdní kolo (v jehož siluetách jsme již mohli rozeznat obrysy čtvercových kol), rozhodli jsme se opět k takovému problému přistoupit vědecky, totiž: pokuste se jej zredukovat na další optimalizaci diskrétního problému v naději, že stávající algoritmy pro jeho řešení lze použít bez úprav.
Další hledání podobného klasického problému bylo úspěšné! Podařilo se nám najít diskrétní optimalizační problém, jehož formulace se 1 v 1 shoduje s formulací našeho problému. Tento úkol se ukázal být nastavit krycí problém. Uveďme formulaci problému ve vztahu k našim specifikům.
Existuje konečná množina a rodina všech svých nesouvislých podmnožin stran, takže rozdíl v datech pro všechny dvojice stran každé podmnožiny od rodiny nepřekračuje konstanty . Krytina se nazývá rodina nejmenší síly, jejíž prvky patří , takové, že spojení množin od rodiny by měl dát soubor všech stran .
Podrobnou analýzu tohoto problému lze nalézt и Lze nalézt další možnosti praktické aplikace problému krytiny a jejích úprav
Algoritmus pro řešení problému
Rozhodli jsme se pro matematický model řešeného problému. Nyní se podívejme na algoritmus pro jeho řešení. Podmnožiny od rodiny lze snadno najít následujícím postupem.
- Uspořádejte dávky ze sady v sestupném pořadí jejich dat.
- Najděte minimální a maximální data šarže.
- Pro každý den od minimálního data po maximum najděte všechny šarže, jejichž data se liší ne více než (tedy hodnota Je lepší vzít sudé číslo).
Logika postupu pro vytvoření rodiny množin na dnů je znázorněno na obrázku 4.
Obr.4. Tvorba podmnožin stran
Tento postup není nutný pro každého projděte všechny ostatní dávky a zkontrolujte rozdíl v jejich datech nebo od aktuální hodnoty pohybujte doleva nebo doprava, dokud nenajdete dávku, jejíž datum se liší od o více než polovinu hodnoty konstanty. Všechny následující prvky při pohybu doprava i doleva pro nás nebudou zajímavé, protože u nich se rozdíl ve dnech pouze zvýší, protože prvky v poli byly původně uspořádány. Tento přístup výrazně ušetří čas, když je počet večírků a rozptyl jejich termínů výrazně velký.
Problém pokrytí sady je -obtížný, což znamená, že neexistuje žádný rychlý (s operačním časem rovným polynomu vstupních dat) a přesný algoritmus pro jeho řešení. Proto byl pro vyřešení problému s množinou pokrytí zvolen rychlý chamtivý algoritmus, který samozřejmě není přesný, ale má následující výhody:
- Pro malé problémy (a to je přesně náš případ) počítá řešení, která jsou zcela blízká optimu. S rostoucí velikostí problému se kvalita řešení zhoršuje, ale stále docela pomalu;
- Velmi snadné provedení;
- Rychlý, protože jeho odhad doby provozu je .
Chamtivý algoritmus vybírá množiny na základě následujícího pravidla: v každé fázi je vybrána množina, která pokrývá maximální počet dosud nepokrytých prvků. Podrobný popis algoritmu a jeho pseudokódu lze nalézt
Porovnání přesnosti takového hltavého algoritmu na testovacích datech řešeného problému s jinými známými algoritmy, jako je pravděpodobnostní hltivý algoritmus, algoritmus mravenčí kolonie atd., nebylo provedeno. Výsledky porovnání těchto algoritmů na generovaných náhodných datech lze nalézt
Implementace a implementace algoritmu
Tento algoritmus byl implementován v jazyce 1S a byl zahrnut do externího zpracování nazvaného „Komprese zbytků“, ke kterému bylo připojeno WMS-Systém. Algoritmus jsme v jazyce neimplementovali C ++ a použít jej z externí nativní komponenty, což by bylo správnější, protože rychlost kódu je nižší C + + krát a v některých příkladech dokonce desetkrát rychlejší než rychlost podobného kódu na 1S. Na jazyku 1S Algoritmus byl implementován za účelem úspory času při vývoji a snadného ladění ve výrobní základně zákazníka. Výsledek algoritmu je znázorněn na obrázku 5.
Obr.5. Zpracování za účelem „komprese“ zbytků
Obrázek 5 ukazuje, že v zadaném skladu jsou aktuální stavy zboží ve skladových buňkách rozděleny do shluků, v rámci kterých se data dávek zboží od sebe neliší o více než 30 dní. Vzhledem k tomu, že zákazník vyrábí a skladuje ve skladu kovové kulové kohouty, jejichž doba použitelnosti je počítána v letech, lze takový rozdíl datumů zanedbat. Všimněte si, že takové zpracování se v současné době systematicky používá ve výrobě a operátorech WMS potvrdit dobrou kvalitu party clusteringu.
Závěry a pokračování
Hlavní zkušeností, kterou jsme získali při řešení takového praktického problému, je potvrzení účinnosti použití paradigmatu: matematika. problémové prohlášení slavná podložka. Modelka slavný algoritmus algoritmus zohledňující specifika problému. Diskrétní optimalizace existuje již více než 300 let a za tuto dobu se lidem podařilo zvážit spoustu problémů a nashromáždit mnoho zkušeností s jejich řešením. V první řadě je vhodnější obrátit se na tuto zkušenost a teprve poté začít znovu objevovat své kolo.
V příštím článku budeme pokračovat v příběhu o optimalizačních algoritmech a podíváme se na to nejzajímavější a mnohem složitější: algoritmus pro optimální „kompresi“ buněčných zbytků, který jako vstup využívá data získaná z algoritmu dávkového shlukování.
Článek připravil
Roman Shangin, programátor projektového oddělení,
První společnost BIT, Čeljabinsk
Zdroj: www.habr.com