Artikuluak nola inplementatu deskribatzen du WMS-sistema, clustering-arazo ez-estandarra ebazteko beharraren aurrean geunden eta zein algoritmo erabili genituen konpontzeko. Arazoa konpontzeko ikuspegi sistematiko eta zientifiko bat nola aplikatu dugun, zein zailtasun aurkitu ditugun eta zer ikasgai ikasi ditugun kontatuko dizugu.
Argitalpen honek artikulu sorta bat hasten du, non biltegiko prozesuetan optimizazio algoritmoak ezartzeko esperientzia arrakastatsua partekatzen dugun. Artikulu sortaren helburua da ikusleari ia edozein biltegi ertain eta handitan sortzen diren biltegi-eragiketen optimizazio-arazo motak ezagutaraztea, baita arazo horiek konpontzeko dugun esperientzia eta bidean aurkitutako hutsuneak kontatzea ere. . Artikuluak biltegiko logistika industrian lan egiten dutenentzat erabilgarriak izango dira, ezartzeko WMS-sistemak, bai eta negozioetan matematikaren aplikazioetan eta enpresa bateko prozesuen optimizazioan interesa duten programatzaileak ere.
Botila lepoa prozesuetan
2018an, gauzatzeko proiektu bat burutu genuen WMS-Txeliabinsk-eko "Trading House "LD" enpresaren biltegian sistemak. β1C-Logistics: Warehouse Management 3β produktua ezarri dugu 20 lantokitarako: operadoreak WMS, biltegizainak, orga jasotzaileak. Batez besteko biltegia 4 mila m2 ingurukoa da, zelula kopurua 5000 eta SKU kopurua 4500. Biltegiak 1 kg-tik 400 kg-ra bitarteko tamaina desberdinetako gure ekoizpen propioko bola-balbulak gordetzen ditu. Biltegiko inbentarioa loteka gordetzen da, FIFOren arabera salgaiak hautatzeko beharra baitago.
Biltegiko prozesuen automatizazio eskemak diseinatzerakoan, inbentarioa biltegiratze ez-optimoaren arazoarekin topo egin genuen. Garabiak gordetzeko eta gordetzeko zehaztapenak unitateko biltegiratze-gelaxkak lote bateko elementuak soilik izan ditzake. Produktuak egunero iristen dira biltegira eta iriste bakoitza lote bat da. Guztira, 1 hilabeteko biltegiaren funtzionamenduaren ondorioz, 30 sorta bereizi sortzen dira, bakoitza gelaxka batean gorde behar den arren. Produktuak sarritan ez dira paleta osoetan hautatzen, zatika baizik, eta, ondorioz, gelaxka askotan piezak aukeratzeko eremuan honako irudia ikusten da: 1 m3 baino gehiagoko bolumena duen gelaxka batean hainbat garabi pieza daude. zelula-bolumenaren % 5-10 baino gutxiago hartzen dute.
1. irudia. Gelaxka bateko hainbat ondasunen argazkia
Argi dago biltegiratze ahalmena ez dela modu egokian erabiltzen. Hondamendiaren tamaina imajinatzeko, zifrak eman ditzaket: batez beste, 1 eta 3 gelaxka daude 100 m300 baino gehiagoko bolumena duten biltegiaren funtzionamendu-aldi desberdinetan balantze "minuskuluekin". Biltegia nahiko txikia denez, biltegiko lan-denboraldietan faktore hau "botila" bihurtzen da eta biltegiko prozesuak asko moteltzen ditu.
Arazoak konpontzeko ideia
Ideia bat sortu zen: data hurbileneko hondarrak lote bakarrera murriztu behar dira, eta lote bateratua duten hondarrak gelaxka batean edo hainbatetan trinko jarri behar dira, batean leku nahikorik ez badago. hondakinen kopuru osoa.
2. irudia. Zelulan hondarrak konprimitzeko eskema
Horri esker, jarritako ondasun berrietarako erabiliko den biltegi okupatua nabarmen murrizten da. Biltegiaren edukiera gainkargatzen den egoeran, neurri hori oso beharrezkoa da, bestela baliteke salgai berriak sartzeko behar adina leku libre egotea, eta horrek biltegia jartzeko eta hornitzeko prozesuak geldiaraziko ditu. Aurretik ezarri aurretik WMS-sistemek eskuz egiten zuten eragiketa hori, eta ez zen eraginkorra, zeluletan hondakin egokiak bilatzeko prozesua nahiko luzea baitzen. Orain, WMS sistema bat sartuta, prozesua automatizatzea, bizkortzea eta adimentsua izatea erabaki dugu.
Arazo bat konpontzeko prozesua 2 fasetan banatzen da:
- lehen fasean lote-taldeak aurkitzen ditugu konpresiorako datan hurbil;
- bigarren fasean, lote-talde bakoitzeko gelaxketan geratzen diren ondasunen kokapen trinkoena kalkulatzen dugu.
Oraingo artikuluan algoritmoaren lehen fasean zentratuko gara, eta bigarren fasearen estaldura hurrengo artikulurako utziko dugu.
Bilatu problemaren eredu matematiko bat
Kodea idazteko eta gure gurpila berrasmatzeko eseri baino lehen, arazo honi zientifikoki heltzea erabaki genuen, hau da: matematikoki formulatu, optimizazio diskretu-problema ezagun batera murriztu eta lehendik dauden algoritmo eraginkorrak erabiltzea edo lehendik dauden algoritmo hauek hartzea. oinarri gisa eta konpontzen ari den problema praktikoaren berezitasunetara aldatzea.
Multzoez ari garela problemaren formulazio enpresarialetik argi ondorioztatzen denez, multzoen teoriaren arabera formulatuko dugu halako problema bat.
Utzi β Biltegi bateko produktu jakin baten gainerako lote guztien multzoa. Utzi β egunen konstantea emana. Utzi β loteen azpimultzo bat, non azpimultzoko lote bikote guztien daten diferentziak konstante bat gainditzen ez duen . Azpimultzo disjuntuen gutxieneko kopurua aurkitu behar dugu , hala nola azpimultzo guztiak elkarrekin hartuta asko emango lituzke .
Beste era batera esanda, antzeko alderdien talde edo multzoak aurkitu behar ditugu, non antzekotasun irizpidea konstanteak zehazten duen. . Zeregin honek clustering-arazo ezaguna dakarkigu gogora. Garrantzitsua da esatea kontuan hartzen den problema clustering-arazoarengandik desberdina dela, gure problemak kluster elementuen antzekotasun-irizpiderako baldintza hertsiki definitua duelako, konstanteak zehaztuta. , baina clustering arazoan ez dago horrelako baldintzarik. Clustering-arazoaren adierazpena eta arazo honi buruzko informazioa aurki daitezke
Beraz, problema formulatzea eta antzeko formulazio batekin problema klasiko bat aurkitzea lortu genuen. Orain konponbiderako algoritmo ezagunak kontuan hartu behar dira, gurpila ez berrasmatzeko, praktika onak hartu eta aplikatzeko baizik. Clustering arazoa konpontzeko, algoritmo ezagunenak kontuan hartu ditugu, hau da: -esan nahi du -bitartekoak, konektatutako osagaiak identifikatzeko algoritmoa, gutxieneko spanning tree algoritmoa. Algoritmo horien deskribapena eta azterketa aurki daitezke
Gure arazoa konpontzeko, clustering algoritmoak -esan nahi du eta -batez bestekoak ez dira batere aplikagarriak, kluster kopurua ez baita aldez aurretik ezagutzen eta halako algoritmoek ez dute kontuan hartzen etengabeko egunen muga. Halako algoritmoak kontuan hartu gabe utzi ziren hasieran.
Gure arazoa konpontzeko, konektatutako osagaiak identifikatzeko algoritmoa eta spanning tree minimoaren algoritmoa egokiagoak dira, baina, ondorioztatu denez, ezin dira konpontzen ari den arazoari "buruz" aplikatu eta irtenbide ona lortu. Hau azaltzeko, kontuan izan dezagun algoritmo horien funtzionamendu-logika gure problemarekin lotuta.
Demagun grafikoa , zeinetan erpinak alderdien multzoa diren , eta erpinen arteko ertza ΠΈ loteen arteko egunen arteko diferentziaren pisua du ΠΈ . Konektatutako osagaiak identifikatzeko algoritmoan, sarrera-parametroa zehazten da Non , eta grafikoan pisu handiagoa duten ertz guztiak kentzen dira . Objektu bikote hurbilenak bakarrik geratzen dira konektatuta. Algoritmoaren helburua balio hori hautatzea da , grafikoa hainbat osagai konektatutan "erortzen da", non osagai horiei dagozkien alderdiek gure antzekotasun irizpidea beteko duten, konstanteak zehaztuta. . Sortzen diren osagaiak klusterrak dira.
Gutxieneko spanning tree algoritmoa grafiko batean eraikitzen da gutxieneko hedadura-zuhaitza, eta gero pisu handiena duten ertzak sekuentzialki kentzen ditu grafikoa "erortzen" den arte konektatu diren hainbat osagaitan, non osagai horiei dagozkien alderdiek ere gure antzekotasun irizpidea beteko duten. Sortuko diren osagaiak klusterrak izango dira.
Aztertutako arazoa konpontzeko algoritmo horiek erabiltzean, 3. irudian bezala egoera bat sor daiteke.
3. irudia. Clustering algoritmoen aplikazioa ebazten ari den probleman
Demagun loteen egunen arteko aldearen konstantea 20 egunekoa dela. Grafikoa forma espazialean irudikatu zen ikus-pertzepzioa errazteko. Bi algoritmoek 3 multzoko irtenbide bat sortu zuten, eta hori erraz hobe daiteke multzo bereizietan jarritako loteak elkarren artean konbinatuz! Begi bistakoa da halako algoritmoak aldatu behar direla ebazten ari den problemaren berezitasunetara egokitzeko, eta gure arazoaren konponbiderako bere forma hutsean aplikatzeak emaitza txarrak emango ditu.
Beraz, gure zereginerako aldatutako algoritmo grafikoetarako kodea idazten hasi eta gure bizikleta berrasmatzen hasi baino lehen (gurpil karratuen eskemak jada antzeman genitzakeen siluetetan), berriro ere, horrelako arazo bati zientifikoki heltzea erabaki genuen, hots: saiatu beste problema diskretu baten optimizazio batera murrizten, ebazteko dauden algoritmoak aldaketarik gabe aplika daitezkeen itxaropenarekin.
Antzeko arazo klasiko baten beste bilaketa bat arrakastatsua izan da! Optimizazio-problema diskretu bat aurkitzea lortu dugu, zeinaren formulazioa 1etik 1 bat dator gure problemaren formulazioarekin. Zeregin hori izan zen estaldura arazoa ezarri. Aurkez dezagun arazoaren formulazioa gure berezitasunekin lotuta.
Multzo finitu bat dago eta familia bere alderdien azpimultzo disjuntu guztien artean, hala nola, azpimultzo bakoitzeko alderdi bikote guztien daten aldea familiatik ez ditu konstanteak gainditzen . Estalki bati familia deitzen zaio botere gutxienekoa, zeinaren elementuak direnak , hala nola, multzoen batasuna familiatik alderdi guztien multzoa eman beharko luke .
Arazo honen azterketa zehatza aurki daiteke ΠΈ Estalduraren arazoaren eta haren aldaketen aplikazio praktikorako beste aukera batzuk aurki daitezke
Problema konpontzeko algoritmoa
Ebatzi beharreko problemaren eredu matematikoa erabaki dugu. Ikus dezagun orain ebazteko algoritmoa. Azpimultzoak familiatik erraz aurki daiteke hurrengo prozeduraren bidez.
- Antolatu loteak multzo batetik beren daten beheranzko ordenan.
- Aurkitu gutxieneko eta gehienezko loteen datak.
- Egun guztietarako gutxieneko datatik gehienezkora, aurkitu datak desberdinak diren lote guztiak baino gehiago ez (balioa beraz Hobe da zenbaki bikoitia hartzea).
Multzoen familia bat osatzeko prozeduraren logika at egunak 4. irudian azaltzen dira.
4. irudia. Alderdien azpimultzoen eraketa
Prozedura hau ez da beharrezkoa denentzat gainontzeko sorta guztiak aztertu eta haien daten aldea edo uneko balioarekin egiaztatu mugitu ezkerrera edo eskuinera, data ezberdina den lote bat aurkitu arte konstantearen balioaren erdia baino gehiagoz. Ondorengo elementu guztiak, eskuinera zein ezkerrera mugitzen direnean, ez zaizkigu interesgarriak izango, haientzat egunen aldea handitu baino ez baita egingo, matrizeko elementuak hasieran ordenatuta zeudenez. Planteamendu honek denbora aurreztuko du alderdi kopurua eta haien daten hedapena nabarmen handiak direnean.
Multzoaren estalduraren arazoa da -zaila, hau da, ez dago azkar (sarrerako datuen polinomio baten pareko funtzionamendu denborarekin) eta ebazteko algoritmo zehatzik. Hori dela eta, multzo estalduraren arazoa konpontzeko, algoritmo zikoitz azkarra aukeratu zen, zeina, noski, ez da zehatza, baina abantaila hauek ditu:
- Tamaina txikiko arazoetarako (eta hori da hain zuzen gure kasua), optimotik nahiko hurbil dauden irtenbideak kalkulatzen ditu. Arazoaren tamaina handitzen doan heinean, konponbidearen kalitatea okerrera egiten da, baina oraindik nahiko poliki;
- Oso erraza ezartzeko;
- Azkarra, bere exekuzio denboraren estimazioa baita .
Algoritmo gutiziatsuak arau honen arabera hautatzen ditu multzoak: etapa bakoitzean, oraindik estali gabeko elementuen gehieneko kopurua hartzen duen multzo bat hautatzen da. Algoritmoaren eta bere pseudokodearen deskribapen zehatza aurki daiteke
Ebazten ari den problemaren proba-datuetan halako algoritmo gutiziatsu baten zehaztasuna beste algoritmo ezagun batzuekin konparaketarik ez da egin, hala nola probabilitate zikoitz algoritmoarekin, inurri-kolonien algoritmoarekin, etab. Sortutako ausazko datuekin halako algoritmoak alderatzearen emaitzak aurki daitezke
Algoritmoaren ezarpena eta ezarpena
Algoritmo hau hizkuntzan ezarri zen 1S eta konektatu zen "Hondarren konpresioa" izeneko kanpoko prozesamendu batean sartu zen WMS-sistema. Ez dugu algoritmoa hizkuntzan ezarri C ++ eta erabili kanpoko osagai Natibo batetik, zuzenagoa izango litzateke, kodearen abiadura txikiagoa baita C ++ aldiz, eta adibide batzuetan, antzeko kodearen abiadura baino hamar aldiz handiagoa 1S. Mihian 1S Algoritmoa garapen-denbora aurrezteko eta bezeroaren ekoizpen-basean arazketa errazteko inplementatu zen. Algoritmoaren emaitza 5. irudian aurkezten da.
5. irudia. Hondakinak βkonprimitzekoβ prozesatzea
5. irudiak erakusten du zehaztutako biltegian biltegiratze-zeluletako saldoen egungo saldoak multzotan banatzen direla, eta horien barruan salgaien loteen datak 30 egun baino gehiago ez dira elkarren artean desberdinak. Bezeroak biltegian metalezko bola-balbulak ekoizten eta gordetzen dituenez, haien iraupena urtetan kalkulatzen da, data-desberdintasun hori alde batera utzi daiteke. Kontuan izan prozesaketa hori gaur egun sistematikoki erabiltzen dela ekoizpenean, eta operadoreetan WMS alderdien multzokatzearen kalitate ona baieztatzea.
Ondorioak eta jarraipena
Horrelako problema praktiko bat ebatzita lortu dugun esperientzia nagusia paradigma erabiltzearen eraginkortasunaren berrespena da: matematika. arazoaren adierazpena mat famatua. eredua algoritmo ospetsua algoritmoa arazoaren berezitasunak kontuan hartuta. Optimizazio diskretuak 300 urte baino gehiago daramatza, eta denbora horretan jendeak arazo asko kontuan hartzea eta horiek konpontzeko esperientzia handia pilatzea lortu du. Lehenik eta behin, komenigarriagoa da esperientzia honetara jotzea, eta orduan bakarrik hastea zure gurpila berrasmatzen.
Hurrengo artikuluan optimizazio-algoritmoei buruzko istorioarekin jarraituko dugu eta interesgarriena eta askoz konplexuagoa dena aztertuko dugu: zelula-hondakinen βkonpresioβ optimorako algoritmo bat, batch clustering algoritmotik jasotako datuak sarrera gisa erabiltzen dituena.
Artikulua prestatu du
Roman Shangin, proiektuen saileko programatzailea,
Lehen BIT konpainia, Chelyabinsk
Iturria: www.habr.com