La artikolo priskribas kiel efektivigi WMS-sistemo, ni alfrontis la bezonon solvi ne-norman clustering-problemon kaj kiajn algoritmojn ni uzis por solvi ĝin. Ni rakontos al vi kiel ni aplikis sisteman, sciencan aliron por solvi la problemon, kiajn malfacilaĵojn ni renkontis kaj kiajn lecionojn ni lernis.
Ĉi tiu publikigado komencas serion de artikoloj, en kiuj ni dividas nian sukcesan sperton en efektivigado de optimumigo-algoritmoj en magazenaj procezoj. La celo de la serio de artikoloj estas konigi la spektantaron kun la specoj de optimumigo de problemoj de magazenaj operacioj, kiuj aperas en preskaŭ ajna meza kaj granda magazeno, kaj ankaŭ rakonti pri nia sperto pri solvado de tiaj problemoj kaj la malfacilaĵoj renkontitaj survoje. . La artikoloj estos utilaj al tiuj, kiuj laboras en la magazena loĝistika industrio, efektivigas WMS-sistemoj, same kiel programistoj, kiuj interesiĝas pri aplikoj de matematiko en komerco kaj optimumigo de procezoj en entrepreno.
Botelkolo en procezoj
En 2018, ni kompletigis projekton por efektivigi WMS-sistemoj ĉe la magazeno de la kompanio "Komerca Domo "LD" en Chelyabinsk. Ni efektivigis la produkton "1C-Logistiko: Warehouse Management 3" por 20 laborlokoj: funkciigistoj WMS, magazenistoj, ŝarĝaŭtoj. La averaĝa magazeno estas ĉirkaŭ 4 mil m2, la nombro da ĉeloj estas 5000 kaj la nombro da SKUoj estas 4500. La magazeno stokas pilkvalvojn de nia propra produktado de malsamaj grandecoj de 1 kg ĝis 400 kg. Inventaro en la magazeno estas stokita en aroj, ĉar necesas elekti varojn laŭ FIFO.
Dum desegnado de stokaj procezaj aŭtomatigskemoj, ni alfrontis la ekzistantan problemon de ne-optimuma stokregistro. La specifaĵoj pri stokado kaj stokado de gruoj estas tiaj, ke unu unuopova ĉelo povas nur enhavi erojn de unu aro. Produktoj alvenas al la magazeno ĉiutage kaj ĉiu alveno estas aparta aro. Entute, kiel rezulto de 1 monato da magazena operacio, 30 apartaj aroj estas kreitaj, malgraŭ tio, ke ĉiu devus esti stokita en aparta ĉelo. Ofte oni elektas produktojn ne en tutaj paletoj, sed en pecoj, kaj kiel rezulto, en la zono de elekto de pecoj en multaj ĉeloj oni observas la jenan bildon: en ĉelo kun volumeno de pli ol 1 m3 estas pluraj pecoj de gruoj, kiuj okupas malpli ol 5-10% de la ĉela volumo.
Figo 1. Foto de pluraj varoj en ĉelo
Estas klare, ke stoka kapacito ne estas uzata optimume. Por imagi la skalon de la katastrofo, mi povas doni ciferojn: averaĝe estas de 1 ĝis 3 ĉeloj de tiaj ĉeloj kun volumeno de pli ol 100 m300 kun "minuskulaj" ekvilibroj dum malsamaj periodoj de la funkciado de la magazeno. Ĉar la magazeno estas relative malgranda, dum la magazenaj okupataj sezonoj ĉi tiu faktoro fariĝas "botelkolo" kaj tre malrapidigas stokajn procezojn.
Problema solvo ideo
Ekestis ideo: aroj da restaĵoj kun la plej proksimaj datoj devus esti reduktitaj al unu sola aro, kaj tiaj restaĵoj kun unuigita aro devas esti metitaj kompakte kune en unu ĉelon, aŭ en pluraj, se ne estas sufiĉe da spaco en unu por akomodi la. tuta kvanto da restaĵoj.
Fig.2. Skemo por kunpremi restaĵojn en ĉeloj
Ĉi tio ebligas al vi signife redukti la okupatan stokejon, kiu estos uzata por novaj varoj metitaj. En situacio, kie stokkapacito estas troŝarĝita, tia mezuro estas ekstreme necesa, alie eble simple ne estos sufiĉe libera spaco por gastigi novajn varojn, kio kondukos al halto en la stokejo kaj replenigo procezoj. Antaŭe antaŭ efektivigo WMS-sistemoj faris ĉi tiun operacion permane, kio estis neefika, ĉar la procezo de serĉado de taŭgaj restaĵoj en la ĉeloj estis sufiĉe longa. Nun, kun la enkonduko de WMS-sistemo, ni decidis aŭtomatigi la procezon, akceli ĝin kaj igi ĝin inteligenta.
La procezo de solvado de tia problemo estas dividita en 2 etapoj:
- ĉe la unua etapo ni trovas grupojn de aroj proksimaj en dato por kunpremado;
- en la dua etapo, por ĉiu grupo de aroj ni kalkulas la plej kompaktan lokigon de la ceteraj varoj en la ĉeloj.
En la nuna artikolo ni koncentriĝos pri la unua etapo de la algoritmo, kaj lasos priraportadon de la dua etapo por la sekva artikolo.
Serĉu matematikan modelon de la problemo
Antaŭ ol ni sidiĝis por skribi kodon kaj reinventi nian radon, ni decidis science alproksimigi ĉi tiun problemon, nome: formuli ĝin matematike, redukti ĝin al konata diskreta optimumigo problemo kaj uzi efikajn ekzistantajn algoritmojn por solvi ĝin, aŭ preni ĉi tiujn ekzistantajn algoritmojn. kiel bazo kaj modifi ilin al la specifaĵoj de la praktika problemo solvita.
Ĉar ĝi klare sekvas el la komerca formulo de la problemo, ke ni traktas arojn, ni formulos tian problemon laŭ aroteorio.
Lasu - la aro de ĉiuj aroj de la resto de certa produkto en magazeno. Lasu – donita konstanta de tagoj. Lasu – subaro de aroj, kie la diferenco en datoj por ĉiuj paroj de aroj en la subaro ne superas konstanton . Ni devas trovi la minimuman nombron da disaj subaroj , tia ke ĉiuj subaroj kunprenite donus multajn .
Alivorte, ni devas trovi grupojn aŭ aretojn de similaj partioj, kie la simileckriterio estas determinita per la konstanto . Ĉi tiu tasko memorigas al ni la konatan clustering-problemon. Gravas diri, ke la konsiderata problemo devias de la amasiga problemo en tio, ke nia problemo havas strikte difinitan kondiĉon por la kriterio de simileco de aretelementoj, determinita de la konstanto. , sed en la clustering-problemo ne ekzistas tia kondiĉo. La deklaro de la clustering-problemo kaj informoj pri ĉi tiu problemo troveblas
Do, ni sukcesis formuli la problemon kaj trovi klasikan problemon kun simila formuliĝo. Nun necesas konsideri konatajn algoritmojn por solvi ĝin, por ne reinventi la radon, sed preni la plej bonajn praktikojn kaj apliki ilin. Por solvi la clustering-problemon, ni konsideris la plej popularajn algoritmojn, nome: - signifas -means, algoritmo por identigi koneksajn komponantojn, minimuma spanning-arba algoritmo. Priskribo kaj analizo de tiaj algoritmoj troveblas
Por solvi nian problemon, clustering algoritmoj - signifas kaj -means tute ne aplikeblas, ĉar la nombro da aretoj neniam estas antaŭsciita kaj tiaj algoritmoj ne enkalkulas la konstantan tagan limon. Tiaj algoritmoj estis komence forĵetitaj de konsidero.
Por solvi nian problemon, la algoritmo por identigi koneksajn komponantojn kaj la minimuman ampleksan arbo-algoritmon estas pli taŭgaj, sed, kiel montriĝis, ili ne povas esti aplikataj "fronte" al la problemo solvita kaj akiri bonan solvon. Por klarigi ĉi tion, ni konsideru la logikon de operacio de tiaj algoritmoj rilate al nia problemo.
Konsideru la grafeon , en kiu la verticoj estas la aro de partioj , kaj la rando inter la verticoj и havas pezon egalan al la diferenco de tagoj inter aroj и . En la algoritmo por identigi konektitajn komponantojn, la eniga parametro estas specifita kie , kaj en la grafeo ĉiuj randoj por kiuj la pezo estas pli granda estas forigitaj . Nur la plej proksimaj paroj de objektoj restas ligitaj. La punkto de la algoritmo estas elekti tian valoron , en kiu la grafeo "disfalas" en plurajn ligitajn komponentojn, kie la partioj apartenantaj al tiuj komponentoj kontentigos nian simileckriterion, determinitan per la konstanto . La rezultaj komponentoj estas aretoj.
La minimuma arba algoritmo unue konstruas sur grafeo minimuma ampleksa arbo, kaj tiam sinsekve forigas randojn kun la plej alta pezo ĝis la grafeo "disfalas" en plurajn ligitajn komponentojn, kie la partioj apartenantaj al tiuj komponentoj ankaŭ kontentigos nian simileckriterion. La rezultaj komponantoj estos aretoj.
Kiam oni uzas tiajn algoritmojn por solvi la konsideran problemon, povas aperi situacio kiel en Figuro 3.
Fig. 3. Apliko de clustering-algoritmoj al la problemo solvita
Ni diru, ke nia konstanta por la diferenco inter battaj tagoj estas 20 tagoj. Grafiko estis prezentita en spaca formo por facileco de vida percepto. Ambaŭ algoritmoj produktis 3-grupon solvon, kiu povas esti facile plibonigita kombinante la arojn metitaj en apartaj aretoj inter si! Estas evidente, ke tiaj algoritmoj devas esti modifitaj por konveni al la specifaĵoj de la problemo solvita, kaj ilia aplikado en ĝia pura formo al la solvo de nia problemo donos malbonajn rezultojn.
Do, antaŭ ol ni komencis verki kodon por grafikaj algoritmoj modifitaj por nia tasko kaj reinventi nian propran biciklon (en kies siluetoj ni jam povis distingi la konturojn de kvadrataj radoj), ni denove decidis science trakti tian problemon, nome: provu redukti ĝin al alia diskreta problemoptimumigo, kun la espero ke ekzistantaj algoritmoj por solvi ĝin povas esti aplikataj sen modifoj.
Alia serĉo de simila klasika problemo sukcesis! Ni sukcesis trovi diskretan optimumigan problemon, kies formuliĝo koincidas 1 en 1 kun la formuliĝo de nia problemo. Ĉi tiu tasko montriĝis starigis kovran problemon. Ni prezentu la formulon de la problemo rilate al niaj specifaĵoj.
Estas finia aro kaj familio de ĉiuj ĝiaj disaj subaroj de partioj, tia ke la diferenco en datoj por ĉiuj paroj de partioj de ĉiu subaro de la familio ne superas konstantojn . Kovaĵo nomiĝas familio de la plej malgranda potenco, al kies elementoj apartenas , tia ke la kuniĝo de aroj de la familio devus doni la aron de ĉiuj partioj .
Detala analizo de ĉi tiu problemo troveblas и Aliaj opcioj por la praktika apliko de la kovra problemo kaj ĝiaj modifoj troveblas
Algoritmo por solvi la problemon
Ni decidis pri la matematika modelo de la solvota problemo. Nun ni rigardu la algoritmon por solvi ĝin. Subaroj de la familio facile troveblas per la sekva proceduro.
- Aranĝu arojn el aro en malkreskanta ordo de iliaj datoj.
- Trovu la minimumajn kaj maksimumajn ardatojn.
- Por ĉiu tago de la minimuma dato ĝis la maksimumo, trovu ĉiujn arojn, kies datoj diferencas ne pli ol (do la valoro Estas pli bone preni la paran nombron).
Logiko de la proceduro por formi familion de aroj ĉe tagoj estas prezentita en Figuro 4.
Fig.4. Formado de subaroj de partioj
Ĉi tiu proceduro ne estas necesa por ĉiuj trairu ĉiujn aliajn arojn kaj kontrolu la diferencon en iliaj datoj, aŭ de la nuna valoro movu maldekstren aŭ dekstren ĝis vi trovos aron, kies dato estas malsama al je pli ol duono de la valoro de la konstanto. Ĉiuj postaj elementoj, moviĝante kaj dekstren kaj maldekstren, ne estos interesaj por ni, ĉar por ili la diferenco en tagoj nur pliiĝos, ĉar la elementoj en la tabelo estis komence ordigitaj. Ĉi tiu aliro signife ŝparos tempon kiam la nombro da partioj kaj la disvastiĝo de iliaj datoj estas signife grandaj.
La aro-kovranta problemo estas -malfacila, kio signifas, ke ne ekzistas rapida (kun operacia tempo egala al polinomo de la eniga datumo) kaj preciza algoritmo por solvi ĝin. Tial, por solvi la problemon pri aro, oni elektis rapidan avidan algoritmon, kiu, kompreneble, ne estas preciza, sed havas la jenajn avantaĝojn:
- Por malgrand-grandaj problemoj (kaj ĉi tio estas ĝuste nia kazo), ĝi kalkulas solvojn, kiuj estas sufiĉe proksimaj al la optimumo. Ĉar la grandeco de la problemo pliiĝas, la kvalito de la solvo malboniĝas, sed ankoraŭ sufiĉe malrapide;
- Tre facile efektivigi;
- Rapida, ĉar ĝia rultempa takso estas .
La avida algoritmo elektas arojn surbaze de la sekva regulo: en ĉiu stadio, aro estas elektita kiu kovras la maksimuman nombron da elementoj ankoraŭ ne kovritaj. Detala priskribo de la algoritmo kaj ĝia pseŭdokodo troveblas
Komparo de la precizeco de tia avida algoritmo en testdatenoj de la problemo estanta solvita kun aliaj konataj algoritmoj, kiel ekzemple la probabilisma avida algoritmo, la formikkolonia algoritmo, ktp., ne estis farita. La rezultoj de komparado de tiaj algoritmoj sur generitaj hazardaj datenoj troveblas
Efektivigo kaj efektivigo de la algoritmo
Ĉi tiu algoritmo estis efektivigita en la lingvo 1С kaj estis inkludita en ekstera pretigo nomita "Residue Compression" al kiu estis ligita WMS-sistemo. Ni ne efektivigis la algoritmon en la lingvo C ++ kaj uzu ĝin de ekstera Denaska komponanto, kio estus pli ĝusta, ĉar la rapideco de la kodo estas pli malalta C ++ fojojn kaj en kelkaj ekzemploj eĉ dekoble pli rapide ol la rapideco de simila kodo sur 1С. Sur la lango 1С La algoritmo estis efektivigita por ŝpari disvolvan tempon kaj facilecon de senararigado ĉe la produktadbazo de la kliento. La rezulto de la algoritmo estas prezentita en Figuro 5.
Fig.5. Pretigo por "kunpremi" restaĵojn
Figuro 5 montras, ke en la specifita stokejo, la nunaj ekvilibroj de varoj en stokaj ĉeloj estas dividitaj en aretojn, ene de kiuj la datoj de la varoj diferencas unu de la alia je ne pli ol 30 tagoj. Ĉar la kliento produktas kaj stokas metalajn globvalvojn en la magazeno, kies bretdaŭro estas kalkulita en jaroj, tia datdiferenco povas esti neglektita. Notu ke tia prilaborado estas nuntempe uzata sisteme en produktado, kaj funkciigistoj WMS konfirmi la bonan kvaliton de partia amasiĝo.
Konkludoj kaj daŭrigo
La ĉefa sperto, kiun ni akiris de solvado de tia praktika problemo, estas konfirmo de la efikeco de uzado de la paradigmo: matematiko. problemo deklaro fama mato. modelo fama algoritmo algoritmo konsiderante la specifaĵoj de la problemo. Diskreta optimumigo ekzistas de pli ol 300 jaroj, kaj dum ĉi tiu tempo homoj sukcesis konsideri multajn problemojn kaj amasigi multan sperton pri solvado de ili. Antaŭ ĉio, estas pli konsilinde turni sin al ĉi tiu sperto, kaj nur tiam komenci reinventi vian radon.
En la sekva artikolo ni daŭrigos la rakonton pri optimumigo-algoritmoj kaj rigardos la plej interesan kaj multe pli kompleksan: algoritmon por optimuma "kunpremo" de ĉelaj restaĵoj, kiu uzas datumojn ricevitajn de la grupa algoritmo kiel enigo.
Preparis la artikolon
Roman Shangin, programisto de la projektsekcio,
Unua BIT-firmao, Chelyabinsk
fonto: www.habr.com