A cikk leírja, hogyan kell végrehajtani WMS-rendszerben szembesültünk azzal, hogy meg kell oldani egy nem szabványos klaszterezési problémát, és milyen algoritmusokkal oldottuk meg. Elmondjuk, hogyan alkalmaztunk szisztematikus, tudományos megközelítést a probléma megoldásában, milyen nehézségekbe ütköztünk és milyen tanulságokat vontunk le.
Ez a kiadvány egy cikksorozatot indít, amelyben megosztjuk sikeres tapasztalatainkat az optimalizáló algoritmusok raktári folyamatokban történő megvalósításában. A cikksorozat célja, hogy megismertesse a hallgatósággal a raktári műveletek optimalizálási problémáinak típusait, amelyek szinte bármely közepes és nagy raktárban felmerülnek, valamint beszámoljunk az ilyen jellegű problémák megoldásában szerzett tapasztalatainkról és az út során felmerülő buktatókról. . A cikkek hasznosak lesznek azok számára, akik a raktári logisztikai ágazatban, kivitelezésben dolgoznak WMS-rendszerek, valamint programozók, akik érdeklődnek a matematika üzleti életben történő alkalmazásai és a vállalati folyamatok optimalizálása iránt.
Szűk keresztmetszetek a folyamatokban
2018-ban befejeztük a megvalósításra váró projektet WMS-rendszerek a cseljabinszki „Trading House „LD” cég raktárában. Az „1C-Logistics: Warehouse Management 3” terméket 20 munkahelyre vezettük be: üzemeltetők WMS, raktárosok, targoncavezetők. Az átlagos raktár területe körülbelül 4 ezer m2, a cellák száma 5000, az SKU-k száma pedig 4500. A raktárban saját gyártású golyóscsapokat tárolunk, különböző méretű 1 kg-tól 400 kg-ig. A raktárban a készleteket tételesen tárolják, mivel az árukat a FIFO szerint kell kiválasztani.
A raktári folyamatok automatizálási sémáinak tervezésekor szembesültünk a nem optimális készlettárolás fennálló problémájával. A daruk tárolásának és tárolásának sajátosságai olyanok, hogy egy egységtároló cella csak egy tételből származó tételeket tartalmazhat. A termékek naponta érkeznek a raktárba, és minden beérkezés egy külön tétel. Összesen 1 hónapos raktári működés eredményeként 30 külön tétel jön létre, annak ellenére, hogy mindegyiket külön cellában kell tárolni. A termékeket gyakran nem egész raklapokban, hanem darabokban választják ki, és ennek eredményeként a darabkiválasztási zónában sok cellában a következő kép figyelhető meg: egy 1 m3-nél nagyobb térfogatú cellában több daru darab van, a sejttérfogat kevesebb mint 5-10%-át foglalják el.
1. ábra: Több árucikk fényképe egy cellában
Nyilvánvaló, hogy a tárolókapacitást nem használják ki optimálisan. A katasztrófa mértékének elképzeléséhez számokat tudok közölni: átlagosan 1-3 ilyen cella van, amelyek térfogata meghaladja az 100 m300-t, „minimális” egyenlegekkel a raktár működésének különböző időszakaiban. Mivel a raktár viszonylag kicsi, a raktári forgalmas időszakokban ez a tényező „szűk keresztmetszetté” válik, és nagymértékben lelassítja a raktári folyamatokat.
Probléma megoldási ötlet
Felmerült egy ötlet: a legközelebbi dátummal rendelkező maradékokat egyetlen tételre kell csökkenteni, és az egységes tétellel rendelkező maradékokat tömören egy cellába, vagy többbe kell helyezni, ha az egyikben nincs elég hely a teljes mennyiségű maradékot.
2. ábra. A sejtekben lévő maradékok tömörítésének sémája
Ez lehetővé teszi, hogy jelentősen csökkentse az elfoglalt raktárterületet, amelyet az új áruk elhelyezésére használnak majd. Olyan helyzetben, amikor a raktár kapacitása túlterhelt, egy ilyen intézkedés rendkívül szükséges, ellenkező esetben előfordulhat, hogy egyszerűen nem lesz elég szabad hely az új áruk befogadására, ami a raktár elhelyezési és feltöltési folyamatainak leállásához vezet. Korábban a megvalósítás előtt WMS-rendszerek ezt a műveletet manuálisan hajtották végre, ami nem volt hatékony, mivel a megfelelő maradékanyagok keresése a sejtekben meglehetősen hosszú volt. Most, a WMS rendszer bevezetésével úgy döntöttünk, hogy automatizáljuk a folyamatot, felgyorsítjuk és intelligenssé tesszük.
Az ilyen probléma megoldásának folyamata 2 szakaszra oszlik:
- az első szakaszban a tömörítéshez közeli kötegcsoportokat találunk;
- a második szakaszban minden tételcsoportra kiszámítjuk a maradék áruk legtömörebb elhelyezését a cellákban.
Ebben a cikkben az algoritmus első szakaszára fogunk összpontosítani, és a második szakasz ismertetését a következő cikkre hagyjuk.
Keresse meg a probléma matematikai modelljét
Mielőtt leültünk volna kódot írni és újra feltalálni a kerekünket, úgy döntöttünk, hogy tudományosan közelítjük meg ezt a problémát, nevezetesen: matematikailag megfogalmazzuk, egy jól ismert diszkrét optimalizálási problémára redukáljuk, és hatékony, meglévő algoritmusokat használunk a megoldására, vagy alkalmazzuk ezeket a meglévő algoritmusokat. alapjául, és módosítsa azokat a megoldandó gyakorlati probléma sajátosságaihoz.
Mivel a probléma üzleti megfogalmazásából egyértelműen következik, hogy halmazokkal van dolgunk, ezért halmazelméleti szempontból fogunk megfogalmazni egy ilyen problémát.
enged – egy raktárban egy bizonyos termék maradékának összes tétele. Hadd – adott napállandó. Hadd – a kötegek egy részhalmaza, ahol az alhalmaz összes tételpárjának dátumbeli különbsége nem haladja meg az állandót . Meg kell találnunk a diszjunkt részhalmazok minimális számát , úgy, hogy az összes részhalmaz együtt sok mindent adna .
Más szóval hasonló pártok csoportjait vagy klasztereit kell találnunk, ahol a hasonlósági kritériumot a konstans határozza meg. . Ez a feladat a jól ismert klaszterezési problémára emlékeztet. Fontos elmondani, hogy a vizsgált probléma abban különbözik a klaszterezési problémától, hogy problémánknak van egy szigorúan meghatározott feltétele a klaszterelemek hasonlósági kritériumának, amelyet a konstans határoz meg. , de a klaszterezési problémában nincs ilyen feltétel. A klaszterezési probléma kijelentése és a problémával kapcsolatos információk megtalálhatók
Így sikerült megfogalmaznunk a problémát, és találtunk egy klasszikus problémát hasonló megfogalmazással. Most jól ismert algoritmusokat kell átgondolnunk a megoldására, hogy ne feltaláljuk újra a kereket, hanem vegyük át a legjobb gyakorlatokat és alkalmazzuk azokat. A klaszterezési probléma megoldásához a legnépszerűbb algoritmusokat vettük figyelembe, nevezetesen: -eszközök -eszközök, algoritmus a kapcsolódó komponensek azonosítására, minimális feszítőfa algoritmus. Az ilyen algoritmusok leírása és elemzése megtalálható
Problémánk megoldására klaszterezési algoritmusok - jelenti és A -eszközök egyáltalán nem alkalmazhatók, mivel a klaszterek száma soha nem ismert előre és az ilyen algoritmusok nem veszik figyelembe az állandó napok megkötését. Az ilyen algoritmusokat kezdetben figyelmen kívül hagyták.
Problémánk megoldására az összekapcsolt komponensek azonosítására szolgáló algoritmus és a minimális feszítőfa algoritmus alkalmasabb, de, mint kiderült, nem alkalmazhatók „fejjel” a megoldandó problémára, és jó megoldást kaphatunk. Ennek magyarázatához nézzük meg az ilyen algoritmusok működési logikáját a problémánkkal kapcsolatban.
Tekintsük a grafikont , amelyben a csúcsok a felek halmaza , és a csúcsok közötti él и súlya megegyezik a tételek közötti napok különbségével и . A csatlakoztatott komponensek azonosítására szolgáló algoritmusban meg van adva a bemeneti paraméter Ahol , és a grafikonon minden olyan élt, amelynél nagyobb a súly, eltávolítjuk . Csak a legközelebbi tárgypárok maradnak kapcsolatban. Az algoritmus lényege egy ilyen érték kiválasztása , amelyben a gráf több összefüggő komponensre „szétbomlik”, ahol az ezekhez a komponensekhez tartozó felek eleget tesznek a konstans által meghatározott hasonlósági kritériumunknak. . Az így kapott komponensek klaszterek.
A minimális feszítőfa algoritmus először egy gráfra épül minimális feszítőfát, majd szekvenciálisan eltávolítja a legnagyobb súllyal bíró éleket, amíg a gráf több összefüggő komponensre „szét nem esik”, ahol az ezekhez a komponensekhez tartozó felek is megfelelnek a hasonlósági kritériumunknak. A kapott komponensek klaszterek lesznek.
Ha ilyen algoritmusokat használunk a szóban forgó probléma megoldására, a 3. ábrához hasonló helyzet állhat elő.
3. ábra Klaszterezési algoritmusok alkalmazása a megoldandó problémára
Tegyük fel, hogy a kötegnapok közötti különbség állandója 20 nap. Grafikon térbeli formában ábrázolták a vizuális észlelés megkönnyítése érdekében. Mindkét algoritmus 3 klaszteres megoldást készített, amely a külön klaszterekbe helyezett kötegek egymással való kombinálásával egyszerűen javítható! Nyilvánvaló, hogy az ilyen algoritmusokat módosítani kell, hogy azok megfeleljenek a megoldandó probléma sajátosságainak, és tiszta formában történő alkalmazásuk problémánk megoldására gyenge eredményeket ad.
Tehát, mielőtt elkezdtünk kódot írni a feladatunknak megfelelően módosított gráfalgoritmusokhoz, és újra feltaláltuk a saját kerékpárunkat (amelynek sziluettjein már kivehettük a négyzet alakú kerekek körvonalait), ismét úgy döntöttünk, hogy egy ilyen problémát tudományosan közelítünk meg, nevezetesen: próbálja meg egy másik diszkrét problémaoptimalizálásra redukálni, abban a reményben, hogy a megoldására meglévő algoritmusok módosítás nélkül alkalmazhatók.
Egy másik hasonló klasszikus probléma keresése sikeres volt! Sikerült egy diszkrét optimalizálási feladatot találnunk, melynek megfogalmazása 1 az 1-ben egybeesik a feladatunk megfogalmazásával. Ez a feladat az lett set fedő probléma. Mutassuk be a probléma megfogalmazását sajátosságainkhoz képest.
Van egy véges halmaz és a család a felek összes diszjunkt részhalmazából úgy, hogy az egyes részhalmazok összes pártpárjának dátumaiban különbség legyen a családtól nem haladja meg az állandókat . A burkolatot családnak nevezik a legkisebb erejű, amelynek elemei tartoznak , így a halmazok uniója a családtól meg kell adnia az összes fél halmazát .
A probléma részletes elemzése megtalálható и A fedőprobléma és annak módosításai gyakorlati alkalmazásának további lehetőségei találhatók
Algoritmus a probléma megoldásához
Elhatároztuk a megoldandó probléma matematikai modelljét. Most nézzük meg a megoldás algoritmusát. Részhalmazok a családtól könnyen megtalálható a következő eljárással.
- Tételek rendezése egy készletből dátumuk szerinti csökkenő sorrendben.
- Keresse meg a tétel minimális és maximális dátumát.
- Minden nap a minimális dátumtól a maximumig keresse meg az összes tételt, amelynek dátumai eltérnek nem több, mint (tehát az érték Jobb a páros számot venni).
A halmazcsalád kialakításának eljárásának logikája -on napokat a 4. ábra mutatja be.
4. ábra. A pártok részhalmazainak kialakulása
Ez az eljárás nem mindenki számára szükséges menjen végig az összes többi tételen, és ellenőrizze a dátumok eltérését, vagy az aktuális értéktől mozgassa balra vagy jobbra, amíg meg nem talál egy tételt, amelynek dátuma eltér a konstans értékének több mint felével. Az összes későbbi elem, amikor jobbra és balra is mozog, nem lesz érdekes számunkra, mivel számukra a napok különbsége csak nő, mivel a tömb elemeit eredetileg rendezték. Ezzel a megközelítéssel jelentősen időt takaríthatunk meg, amikor a felek száma és időpontjaik jelentős mértékben nagyok.
A készlet takarási problémája az -nehéz, ami azt jelenti, hogy nincs gyors (a bemeneti adatok polinomjával egyenlő üzemidővel) és pontos algoritmus a megoldására. Ezért a halmazlefedési probléma megoldására egy gyors mohó algoritmust választottak, amely természetesen nem pontos, de a következő előnyökkel rendelkezik:
- Kis méretű problémákra (és pontosan ez a mi esetünk) olyan megoldásokat számol, amelyek egészen közel állnak az optimumhoz. A probléma méretének növekedésével a megoldás minősége romlik, de még mindig meglehetősen lassan;
- Nagyon könnyen kivitelezhető;
- Gyors, mivel a becsült futási idő az .
A mohó algoritmus a következő szabály alapján választ ki halmazokat: minden szakaszban kiválaszt egy halmazt, amely lefedi a még le nem fedett elemek maximális számát. Az algoritmus részletes leírása és pszeudokódja megtalálható
Nem készült egy ilyen mohó algoritmus pontosságának összehasonlítása a megoldandó probléma tesztadataira más ismert algoritmusokkal, mint például a valószínűségi mohó algoritmus, a hangyatelep algoritmus stb. Az ilyen algoritmusok generált véletlenszerű adatokon történő összehasonlításának eredményei megtalálhatók
Az algoritmus megvalósítása és megvalósítása
Ezt az algoritmust implementálták a nyelven 1S és a "Residue Compression" nevű külső feldolgozásba került, amelyhez csatlakozott WMS-rendszer. Nem implementáltuk az algoritmust a nyelven C ++ és külső Native komponensből használja, ami helyesebb lenne, mivel a kód sebessége kisebb C + + alkalommal, és néhány példában akár tízszer gyorsabban, mint a hasonló kód sebessége 1S. A nyelven 1S Az algoritmust a fejlesztési idő megtakarítása és a hibakeresés megkönnyítése érdekében vezették be az ügyfél termelési bázisán. Az algoritmus eredményét az 5. ábra mutatja be.
5. ábra. Feldolgozás a maradékok „tömörítésére”.
Az 5. ábrán látható, hogy a megadott raktárban a tárolócellákban lévő aktuális áruegyenlegek klaszterekre vannak felosztva, amelyeken belül az árutételek dátumai legfeljebb 30 nappal térnek el egymástól. Mivel a megrendelő fémgolyós szelepeket gyárt és tárol a raktárban, amelyek eltarthatósági idejét években számolják, így az ilyen időpont eltérés elhanyagolható. Vegye figyelembe, hogy az ilyen feldolgozást jelenleg szisztematikusan alkalmazzák a termelésben és az üzemeltetőkben WMS megerősíti a pártcsoportosítás jó minőségét.
Következtetések és folytatás
A fő tapasztalat, amit egy ilyen gyakorlati probléma megoldásából szereztünk, a paradigma: matematika használatának hatékonyságának megerősítése. problémafelvetés híres gyékény. modell híres algoritmus algoritmus a probléma sajátosságait figyelembe véve. A diszkrét optimalizálás több mint 300 éve létezik, és ezalatt az idő alatt az embereknek sikerült sok problémát mérlegelni, és sok tapasztalatot halmoztak fel azok megoldásában. Mindenekelőtt célszerűbb ehhez az élményhez fordulni, és csak ezután kezdeni újra feltalálni a kereket.
A következő cikkben folytatjuk az optimalizálási algoritmusokról szóló történetet, és megvizsgáljuk a legérdekesebbet és sokkal összetettebbet: a sejtmaradványok optimális „tömörítésére” szolgáló algoritmust, amely a kötegelt klaszterezési algoritmustól kapott adatokat használja bemenetként.
Elkészítette a cikket
Roman Shangin, a projektrészleg programozója,
Első BIT cég, Cseljabinszk
Forrás: will.com