В статье рассказывается как при внедрении WMS-sistema smo se soočili s potrebo po rešitvi nestandardnega problema združevanja v gruče in kakšne algoritme smo uporabili za njegovo rešitev. Povedali vam bomo, kako smo uporabili sistematičen, znanstveni pristop k reševanju problema, na kakšne težave smo naleteli in kaj smo se naučili.
Ta publikacija začenja serijo člankov, v katerih delimo naše uspešne izkušnje pri implementaciji optimizacijskih algoritmov v skladiščne procese. Namen serije člankov je seznaniti občinstvo z vrstami problemov optimizacije skladiščnega poslovanja, ki se pojavljajo v skoraj vsakem srednjem in velikem skladišču, ter povedati o naših izkušnjah pri reševanju takšnih problemov in pasteh, s katerimi se srečujemo na poti. . Članki bodo koristni za tiste, ki delajo v skladiščni logistični industriji, izvajajo WMS-sistemov, pa tudi programerjev, ki jih zanimajo aplikacije matematike v poslovanju in optimizacija procesov v podjetju.
Ozko grlo v procesih
V letu 2018 smo zaključili projekt za izvedbo WMS-sistemi v skladišču podjetja “Trading House “LD” v Čeljabinsku. Implementirali smo produkt »1C-Logistika: Warehouse Management 3« za 20 delovnih mest: operaterji WMS, skladiščniki, viličaristi. Povprečno skladišče je približno 4 tisoč m2, število celic 5000 in število SKU 4500. V skladišču hranimo krogelne ventile lastne proizvodnje različnih velikosti od 1 kg do 400 kg. Zaloga v skladišču je shranjena v serijah, saj je treba izbrati blago po FIFO.
Pri načrtovanju shem avtomatizacije skladiščnih procesov smo se soočili z obstoječim problemom neoptimalnega skladiščenja zalog. Specifičnost skladiščenja in odlaganja žerjavov je takšna, da lahko ena enota skladiščne celice vsebuje le artikle iz ene serije. Izdelki dnevno prihajajo v skladišče in vsak prihod je posebna serija. Skupno se kot rezultat 1 meseca delovanja skladišča ustvari 30 ločenih serij, kljub dejstvu, da bi morala biti vsaka shranjena v ločeni celici. Izdelki se pogosto izbirajo ne v celih paletah, ampak v kosih, zato je v območju izbire kosov v številnih celicah opažena naslednja slika: v celici s prostornino več kot 1 m3 je več kosov žerjavov, ki zavzemajo manj kot 5-10% volumna celice.
Slika 1. Fotografija več kosov blaga v celici
Jasno je, da skladiščne zmogljivosti niso optimalno izkoriščene. Da bi si predstavljal obseg katastrofe, lahko navedem številke: v različnih obdobjih delovanja skladišča je v povprečju od 1 do 3 celic takšnih celic s prostornino več kot 100 m300 z "minimalnimi" bilancami. Ker je skladišče razmeroma majhno, postane ta dejavnik v času skladiščne zasedenosti »ozko grlo« in močno upočasni skladiščne procese.
Ideja za rešitev problema
Pojavila se je ideja: serije ostankov z najbližjimi datumi zmanjšati na eno samo serijo in takšne ostanke z enotno serijo strniti skupaj v eno celico ali v več, če v eni ni dovolj prostora za sprejem celotno količino ostankov.
Slika 2. Shema za stiskanje ostankov v celicah
To vam omogoča znatno zmanjšanje zasedenega skladiščnega prostora, ki se bo uporabljal za vlaganje novega blaga. V situaciji, ko so skladiščne zmogljivosti preobremenjene, je takšen ukrep izjemno potreben, sicer lahko preprosto ne bo dovolj prostega prostora za sprejem novega blaga, kar bo povzročilo zaustavitev procesov postavitve in dopolnjevanja skladišča. Prej pred izvedbo WMS-sistemi so to operacijo izvajali ročno, kar je bilo neučinkovito, saj je bil proces iskanja ustreznih ostankov v celicah precej dolg. Sedaj, z uvedbo sistema WMS, smo se odločili proces avtomatizirati, ga pohitriti in narediti inteligentnega.
Postopek reševanja takšnega problema je razdeljen na 2 stopnji:
- na prvi stopnji najdemo skupine serij, ki so si blizu datuma za stiskanje;
- na drugi stopnji pa za vsako skupino serij izračunamo najbolj kompaktno postavitev preostalega blaga v celice.
V tem članku se bomo osredotočili na prvo stopnjo algoritma, drugo stopnjo pa bomo pustili za naslednji članek.
Poiščite matematični model problema
Preden smo se usedli k pisanju kode in na novo izumili svoje kolo, smo se odločili, da bomo k temu problemu pristopili znanstveno, in sicer: formulirali ga matematično, reducirali na dobro znani problem diskretne optimizacije in za njegovo rešitev uporabili učinkovite obstoječe algoritme ali vzeli te obstoječe algoritme kot osnovo in jih prilagoditi specifiki praktičnega problema, ki ga rešujemo.
Ker iz poslovne postavitve problema jasno izhaja, da imamo opravka z množicami, bomo tak problem formulirali v smislu teorije množic.
Naj – množica vseh serij ostanka določenega proizvoda v skladišču. Pustiti – dana konstanta dni. Pustiti – podmnožica serij, kjer razlika v datumih za vse pare serij v podmnožici ne presega konstante . Najti moramo najmanjše število disjunktnih podmnožic , tako da vse podmnožice skupaj bi dali veliko .
Z drugimi besedami, poiskati moramo skupine ali grozde podobnih strank, kjer je kriterij podobnosti določen s konstanto . Ta naloga nas spomni na dobro znani problem združevanja v gruče. Pomembno je povedati, da se obravnavani problem razlikuje od problema grozdenja v tem, da ima naš problem strogo definiran pogoj za kriterij podobnosti elementov grozda, ki ga določa konstanta , vendar v problemu združevanja v gruče tega pogoja ni. Izjavo o problemu združevanja v gruče in informacije o tem problemu lahko najdete
Tako nam je uspelo formulirati problem in najti klasičen problem s podobno formulacijo. Zdaj je treba razmisliti o dobro znanih algoritmih za njegovo reševanje, da ne bi znova izumljali kolesa, ampak vzeli najboljše prakse in jih uporabili. Za rešitev problema združevanja v gruče smo upoštevali najbolj priljubljene algoritme, in sicer: - pomeni -sredstva, algoritem za identifikacijo povezanih komponent, algoritem minimalnega vpetega drevesa. Opis in analizo takih algoritmov lahko najdete
Za rešitev našega problema, algoritmi združevanja v gruče - pomeni in -sredstva sploh niso uporabna, saj število grozdov ni nikoli vnaprej znano in takšni algoritmi ne upoštevajo omejitve stalnih dni. Takšni algoritmi so bili sprva zavrženi iz obravnave.
Za rešitev našega problema sta sicer primernejša algoritem za identifikacijo povezanih komponent in algoritem minimalnega vpetega drevesa, ki pa ju, kot se je izkazalo, ne moremo uporabiti “čelno” pri rešenem problemu in dobiti dobro rešitev. Da bi to pojasnili, razmislimo o logiki delovanja takih algoritmov v povezavi z našo težavo.
Razmislite o grafu , v kateri so vozlišča množica strank , in rob med oglišči и ima težo, ki je enaka razliki dni med serijami и . V algoritmu za identifikacijo povezanih komponent je določen vhodni parameter Če , in v grafu odstranimo vse robove, za katere je teža večja . Samo najbližji pari predmetov ostanejo povezani. Bistvo algoritma je izbrati takšno vrednost , pri katerem graf »razpade« na več povezanih komponent, pri čemer bodo strani, ki pripadajo tem komponentam, zadostile našemu kriteriju podobnosti, ki ga določa konstanta . Nastale komponente so grozdi.
Algoritem minimalnega vpetega drevesa najprej gradi na grafu minimalno vpeto drevo, nato pa zaporedno odstranjuje robove z največjo težo, dokler graf ne »razpade« na več povezanih komponent, pri čemer bodo stranke, ki pripadajo tem komponentam, prav tako zadovoljile naš kriterij podobnosti. Nastale komponente bodo grozdi.
Pri uporabi takšnih algoritmov za reševanje obravnavanega problema lahko pride do situacije, kot je na sliki 3.
Slika 3. Uporaba algoritmov za združevanje v skupine pri problemu, ki ga rešujemo
Recimo, da je naša konstanta za razliko med paketnimi dnevi 20 dni. Graf je bil upodobljen v prostorski obliki za lažjo vizualno percepcijo. Oba algoritma sta ustvarila rešitev s 3 gručami, ki jo je mogoče enostavno izboljšati s kombiniranjem serij, ki so med seboj postavljene v ločene gruče! Očitno je, da je treba takšne algoritme prilagoditi specifiki problema, ki ga rešujemo, njihova uporaba v čisti obliki za rešitev našega problema pa bo dala slabe rezultate.
Preden smo torej začeli pisati kodo za grafične algoritme, prirejene za našo nalogo, in na novo izumljati lastno kolo (v silhuetah katerega smo že lahko razbrali obrise kvadratnih koles), smo se ponovno odločili, da se takšnega problema lotimo znanstveno, in sicer: poskusite ga zmanjšati na drugo optimizacijo diskretnega problema, v upanju, da bo obstoječe algoritme za njegovo reševanje mogoče uporabiti brez sprememb.
Še eno iskanje podobnega klasičnega problema je bilo uspešno! Uspelo nam je najti diskretni optimizacijski problem, katerega formulacija 1 v 1 sovpada s formulacijo našega problema. Ta naloga se je izkazala za težava s pokrivanjem. Predstavimo formulacijo problema glede na našo specifiko.
Obstaja končna množica и семейство vseh svojih ločenih podmnožic strank, tako da je razlika v datumih za vse pare strank vsake podmnožice od družine ne presega konstante . Покрытием называют семейство najmanjše moči, katere elementi pripadajo , tako da je unija množic od družine mora podati nabor vseh strank .
Podrobno analizo tega problema lahko najdete и Najdete lahko tudi druge možnosti za praktično uporabo problema pokrivanja in njegovih sprememb
Algoritem za rešitev problema
Odločili smo se za matematični model problema, ki ga želimo rešiti. Zdaj pa poglejmo algoritem za njegovo rešitev. Podmnožice od družine zlahka najdete z naslednjim postopkom.
- Razporedite serije iz kompleta v padajočem vrstnem redu njihovih datumov.
- Poiščite najmanjši in največji datum serije.
- Za vsak dan od najnižjega datuma do največjega, poiščite vse serije, katerih datumi se razlikujejo od ne več kot (torej vrednost Bolje je vzeti sodo število).
Logika postopka za oblikovanje družine množic na dni je prikazano na sliki 4.
Slika 4. Oblikovanje podmnožic strank
Ta postopek ni potreben za vse preglejte vse druge serije in preverite razliko v njihovih datumih ali glede na trenutno vrednost premikajte levo ali desno, dokler ne najdete serije, katere datum se razlikuje od za več kot polovico vrednosti konstante. Vsi nadaljnji elementi, ko se premikamo tako v desno kot v levo, nam ne bodo zanimivi, saj se bo zanje razlika v dnevih samo povečala, saj so bili elementi v nizu prvotno urejeni. Ta pristop bo znatno prihranil čas, ko sta število strank in razpon njihovih datumov precej velika.
Задача о покрытии множества является -трудной, а значит для её решения не существует быстрого (с временем работы равному полиному от входных данных) и точного алгоритма. Поэтому для решения задачи о покрытии множества был выбран быстрый жадный алгоритм, который конечно не является точным, но обладает следующими достоинствами:
- Za manjše probleme (in to je prav naš primer) izračuna rešitve, ki so precej blizu optimumu. Z večanjem velikosti problema se kakovost rešitve slabša, a še vedno precej počasi;
- Zelo enostaven za izvedbo;
- Hiter, saj je njegov čas delovanja ocenjen .
Pohlepni algoritem izbira nize na podlagi naslednjega pravila: na vsaki stopnji se izbere niz, ki pokriva največje število elementov, ki še niso zajeti. Podroben opis algoritma in njegove psevdokode lahko najdete
Primerjava natančnosti takega požrešnega algoritma na testnih podatkih problema, ki se rešuje, z drugimi znanimi algoritmi, kot je verjetnostni pohlepni algoritem, algoritem kolonije mravelj itd., ni bila narejena. Najdemo lahko rezultate primerjave takih algoritmov na generiranih naključnih podatkih
Implementacija in implementacija algoritma
Ta algoritem je bil implementiran v jezik 1S in je bil vključen v zunanjo obdelavo, imenovano "Residue Compression", ki je bila povezana z WMS-sistem. Algoritma nismo implementirali v jezik C ++ in ga uporabite iz zunanje Native komponente, kar bi bilo bolj pravilno, saj je hitrost kode manjša C + + krat in v nekaterih primerih celo desetkrat hitreje od hitrosti podobne kode na 1S. Na jeziku 1S Algoritem je bil implementiran, da bi prihranil razvojni čas in olajšal odpravljanje napak v proizvodni bazi stranke. Rezultat algoritma je predstavljen na sliki 5.
Slika 5. Obdelava za "stiskanje" ostankov
Iz slike 5 je razvidno, da so v navedenem skladišču trenutna stanja blaga v skladiščnih celicah razdeljena na grozde, znotraj katerih se datumi serij blaga med seboj razlikujejo za največ 30 dni. Ker kupec proizvaja in skladišči v skladišču kovinske krogelne ventile, katerih rok trajanja se izračuna v letih, lahko takšno datumsko razliko zanemarimo. Upoštevajte, da se taka obdelava trenutno sistematično uporablja v proizvodnji in operaterjih WMS potrditi dobro kakovost združevanja strank.
Sklepi in nadaljevanje
Glavna izkušnja, ki smo jo pridobili pri reševanju takega praktičnega problema, je potrditev učinkovitosti uporabe paradigme: matematika. izjava o težavi slavni mat. model znani algoritem algoritem ob upoštevanju specifike problema. Diskretna optimizacija obstaja že več kot 300 let in v tem času je ljudem uspelo razmisliti o številnih problemih in nabrati veliko izkušenj pri njihovem reševanju. Najprej se je bolj priporočljivo obrniti na to izkušnjo in šele nato začeti na novo izumljati kolo.
В следующей статье мы продолжим рассказ о алгоритмах оптимизации и рассмотрим самое интересное и гораздо более сложное: алгоритм оптимального «сжатия» остатков в ячейках, который использует на входе данные, полученные от алгоритма кластеризации партий.
Pripravil članek
Roman Šangin, programer oddelka za projekte,
Prvo podjetje BIT, Čeljabinsk
Vir: www.habr.com