Artikkelissa kuvataan, kuinka se toteutetaan WMS-järjestelmässä, kohtasimme tarpeen ratkaista epätyypillinen klusterointiongelma ja mitä algoritmeja käytimme sen ratkaisemiseen. Kerromme sinulle, kuinka sovelsimme systemaattista, tieteellistä lähestymistapaa ongelman ratkaisemiseen, mitä vaikeuksia kohtasimme ja mitä opimme.
Tämä julkaisu aloittaa artikkelisarjan, jossa jaamme onnistuneen kokemuksemme optimointialgoritmien toteuttamisesta varastoprosesseissa. Artikkelisarjan tarkoituksena on esitellä yleisölle millaisia varastotoimintojen optimointiongelmia syntyy lähes missä tahansa keskisuuressa ja suuressa varastossa, sekä kertoa kokemuksistamme tällaisten ongelmien ratkaisemisesta ja matkan varrella tulleista sudenkuopat. . Artikkelit ovat hyödyllisiä niille, jotka työskentelevät varastologistiikka-alalla, toteuttamassa WMS-järjestelmät sekä ohjelmoijat, jotka ovat kiinnostuneita matematiikan sovelluksista liiketoiminnassa ja prosessien optimoinnista yrityksessä.
Pullonkaula prosesseissa
Vuonna 2018 saimme toteutusprojektin valmiiksi WMS-järjestelmät yhtiön “Trading House “LD” varastossa Tšeljabinskissa. Otimme käyttöön tuotteen “1C-Logistics: Warehouse Management 3” 20 työpaikalle: operaattorit WMS, varastonhoitajat, trukinkuljettajat. Keskimääräinen varasto on noin 4 tuhatta m2, kennojen lukumäärä 5000 ja SKU:ita 4500. Varastossa on omaa tuotantoamme palloventtiilejä erikokoisia 1 kg - 400 kg. Varastossa varasto varastoidaan erissä, koska tavarat on valittava FIFO:n mukaan.
Suunnitellessamme varastoprosessien automaatiosuunnitelmia kohtasimme olemassa olevan epäoptimaalisen varaston varastoinnin ongelman. Nosturien varastoinnin ja varastoinnin erityispiirteet ovat sellaiset, että yksi yksikkövarasto voi sisältää vain yhden erän tuotteita. Tuotteet saapuvat varastolle päivittäin ja jokainen saapuminen on erillinen erä. Yhteensä 1 kuukauden varastotoiminnan tuloksena syntyy 30 erillistä erää huolimatta siitä, että jokainen tulisi varastoida erilliseen soluun. Tuotteet valitaan usein ei kokonaisina lavoina, vaan kappaleina, ja sen seurauksena kappaleen valintavyöhykkeellä monissa soluissa havaitaan seuraava kuva: solussa, jonka tilavuus on yli 1 m3, on useita nostureita, jotka vievät alle 5-10 % solun tilavuudesta.
Kuva 1. Kuva useista tavaroista solussa
On selvää, että tallennuskapasiteettia ei käytetä optimaalisesti. Katastrofin laajuuden kuvittelemiseksi voin antaa lukuja: tällaisia soluja, joiden tilavuus on yli 1 m3, on keskimäärin 100 - 300 solua, joiden saldot ovat "pieniä" varaston eri toimintajaksojen aikana. Koska varasto on suhteellisen pieni, varaston kiireisinä aikoina tämä tekijä muodostuu "pullonkaulaksi" ja hidastaa suuresti varastoprosesseja.
Idea ongelman ratkaisuun
Syntyi ajatus: lähimmän päiväyksen omaavat ylijäämäerät tulisi vähentää yhdeksi eräksi ja tällaiset yhtenäisen erän ylijäämät tulisi sijoittaa tiiviisti yhteen soluun tai useampaan, jos yhdessä ei ole tarpeeksi tilaa. koko määrä jäämiä.
Kuva 2. Kaavio jäämien puristamiseksi soluissa
Tämän avulla voit vähentää merkittävästi varattua varastotilaa, jota käytetään uusien tavaroiden sijoittamiseen. Tilanteessa, jossa varastokapasiteetti on ylikuormitettu, tällainen toimenpide on erittäin tarpeellinen, muuten ei välttämättä yksinkertaisesti ole tarpeeksi vapaata tilaa uusien tavaroiden vastaanottamiseen, mikä johtaa varaston sijoitus- ja täydennysprosessien pysähtymiseen. Aikaisemmin ennen käyttöönottoa WMS-järjestelmät suorittivat tämän toimenpiteen manuaalisesti, mikä oli tehotonta, koska sopivien tähteiden etsintä soluista oli melko pitkä. Nyt WMS-järjestelmän käyttöönoton myötä päätimme automatisoida prosessin, nopeuttaa sitä ja tehdä siitä älykkään.
Tällaisen ongelman ratkaisuprosessi on jaettu kahteen vaiheeseen:
- ensimmäisessä vaiheessa löydämme eräryhmiä lähellä pakkausta;
- toisessa vaiheessa laskemme jokaiselle eräryhmälle jäljellä olevien tavaroiden pienimmän sijoituksen soluihin.
Tässä artikkelissa keskitymme algoritmin ensimmäiseen vaiheeseen ja jätämme toisen vaiheen kattavuuden seuraavaan artikkeliin.
Etsi ongelman matemaattinen malli
Ennen kuin aloimme kirjoittaa koodia ja keksiä pyörämme uudelleen, päätimme lähestyä tätä ongelmaa tieteellisesti, nimittäin: muotoilla se matemaattisesti, pelkistää se hyvin tunnetuksi erilliseksi optimointiongelmaksi ja käyttää tehokkaita olemassa olevia algoritmeja sen ratkaisemiseen tai käyttää näitä olemassa olevia algoritmeja. perustaksi ja muokata niitä ratkaistavan käytännön ongelman erityispiirteiden mukaan.
Koska ongelman liiketoiminnallisesta muotoilusta seuraa selvästi, että olemme tekemisissä joukkojen kanssa, muotoilemme tällaisen ongelman joukkoteorian kannalta.
päästää – varastossa olevan tietyn tuotteen jäljellä olevan tuotteen kaikkien erien sarja. Antaa – annettu päivien vakio. Antaa – eräiden osajoukko, jossa kaikkien osajoukon eräparien päivämäärien ero ei ylitä vakiota . Meidän on löydettävä epäyhtenäisten osajoukkojen vähimmäismäärä , niin että kaikki osajoukot yhdessä antaisi paljon .
Toisin sanoen, meidän on löydettävä samankaltaisten puolueiden ryhmiä tai klustereita, joissa samankaltaisuuskriteeri määräytyy vakion perusteella. . Tämä tehtävä muistuttaa meitä hyvin tunnetusta klusterointiongelmasta. On tärkeää sanoa, että tarkasteltava ongelma eroaa klusterointiongelmasta siinä, että ongelmallamme on tiukasti määritelty ehto klusterin elementtien samankaltaisuuskriteerille, jonka määrittää vakio. , mutta klusterointiongelmassa tällaista ehtoa ei ole. Klusterointiongelman lausunto ja tiedot tästä ongelmasta löytyvät
Joten onnistuimme muotoilemaan ongelman ja löytämään klassisen ongelman samanlaisella muotoilulla. Nyt on tarpeen harkita tunnettuja algoritmeja sen ratkaisemiseksi, jotta pyörää ei keksitä uudelleen, vaan parhaat käytännöt otetaan käyttöön ja niitä sovelletaan. Klusterointiongelman ratkaisemiseksi harkitsimme suosituimpia algoritmeja, nimittäin: - tarkoittaa, -välineet, algoritmi yhdistettyjen komponenttien tunnistamiseen, minimivirittävän puun algoritmi. Tällaisten algoritmien kuvaus ja analyysi löytyy
Ongelmamme ratkaisemiseksi klusterointialgoritmit - tarkoittaa ja -keinot eivät sovellu ollenkaan, koska klusterien lukumäärää ei koskaan tiedetä etukäteen ja tällaiset algoritmit eivät ota huomioon vakiopäivien rajoitusta. Tällaiset algoritmit jätettiin alun perin pois harkinnasta.
Ongelmamme ratkaisemiseen sopivampi algoritmi yhdistettyjen komponenttien tunnistamiseen ja minimivirittävän puun algoritmi, mutta kuten kävi ilmi, niitä ei voida soveltaa "päähän" ratkaistavaan ongelmaan ja saada hyvää ratkaisua. Tämän selittämiseksi tarkastelkaamme tällaisten algoritmien toimintalogiikkaa suhteessa ongelmaamme.
Harkitse kaaviota , jossa kärjet ovat joukko osapuolia , ja kärkien välinen reuna и sen paino on yhtä suuri kuin erien välisten päivien ero и . Kytkettyjen komponenttien tunnistamisalgoritmissa määritetään tuloparametri Missä , ja kaaviossa kaikki reunat, joiden paino on suurempi, poistetaan . Vain lähimmät esineparit pysyvät yhteydessä. Algoritmin tarkoitus on valita tällainen arvo , jossa graafi "hajoaa" useiksi toisiinsa liittyviksi komponenteiksi, joissa näihin komponentteihin kuuluvat osapuolet täyttävät samankaltaisuuskriteerimme, joka määräytyy vakiolla . Tuloksena olevat komponentit ovat klustereita.
Vähimmäisvirittävän puun algoritmi rakentuu ensin graafille vähimmäisvirittävän puun ja poistaa sitten peräkkäin painoltaan suurimmat reunat, kunnes graafi "hajoaa" useiksi yhdistetyiksi komponenteiksi, joissa näihin komponentteihin kuuluvat osapuolet myös täyttävät samankaltaisuuskriteerimme. Tuloksena olevat komponentit ovat klustereita.
Tällaisia algoritmeja käytettäessä tarkasteltavan ongelman ratkaisemiseen voi syntyä kuvan 3 kaltainen tilanne.
Kuva 3. Klusterointialgoritmien soveltaminen ratkaistavaan ongelmaan
Oletetaan, että eräpäivien välisen eron vakio on 20 päivää. Kaavio kuvattiin spatiaalisessa muodossa visuaalisen havainnoinnin helpottamiseksi. Molemmat algoritmit tuottivat 3-klusteriratkaisun, jota on helppo parantaa yhdistämällä erillisiin klusteriin sijoitetut erät keskenään! On selvää, että tällaisia algoritmeja on muokattava vastaamaan ratkaistavan ongelman erityispiirteitä, ja niiden soveltaminen puhtaassa muodossaan ongelmamme ratkaisuun antaa huonoja tuloksia.
Joten ennen kuin aloimme kirjoittaa koodia tehtäväämme varten muokatuille graafialgoritmeille ja keksiä uudelleen omaa polkupyöräämme (jonka silueteista pystyimme jo erottamaan neliömäisten pyörien ääriviivat), päätimme jälleen lähestyä tällaista ongelmaa tieteellisesti, nimittäin: yritä pelkistää se toiseen erilliseen ongelman optimointiin siinä toivossa, että olemassa olevia algoritmeja sen ratkaisemiseksi voidaan soveltaa ilman muutoksia.
Toinen samanlaisen klassisen ongelman etsintä on onnistunut! Onnistuimme löytämään diskreetin optimointitehtävän, jonka muotoilu vastaa 1:1:ssä ongelmamme muotoilua. Tämä tehtävä osoittautui aseta peittoongelma. Esitellään ongelman muotoilu suhteessa erityispiirteisiin.
On rajallinen joukko ja perhe kaikista sen erillisistä osapuolten osajoukoista siten, että kunkin osajoukon kaikkien osapuoliparien päivämäärät eroavat perheeltä ei ylitä vakioita . Peitettä kutsutaan perheeksi pienimmän tehon, jonka elementit kuuluvat , niin että joukkojen liitto perheeltä pitäisi antaa kaikkien osapuolten joukko .
Yksityiskohtainen analyysi tästä ongelmasta löytyy и Muita vaihtoehtoja peittoongelman ja sen muunnelmien käytännön soveltamiseen löytyy
Algoritmi ongelman ratkaisemiseksi
Olemme päättäneet ratkaistavan ongelman matemaattisen mallin. Katsotaanpa nyt algoritmia sen ratkaisemiseksi. Osajoukot perheeltä löytyy helposti seuraavalla menettelyllä.
- Järjestä erät sarjasta päivämäärien mukaan laskevassa järjestyksessä.
- Etsi erän vähimmäis- ja enimmäispäivämäärä.
- Joka päivä vähimmäispäivämäärästä enimmäispäivään, etsi kaikki erät, joiden päivämäärät poikkeavat ei enempää kuin (siis arvo On parempi ottaa parillinen luku).
Joukkoperheen muodostamismenettelyn logiikka at päivät on esitetty kuvassa 4.
Kuva 4. Puolueiden osajoukkojen muodostuminen
Tämä menettely ei ole välttämätön kaikille käy läpi kaikki muut erät ja tarkista ero niiden päivämäärissä tai nykyisestä arvosta siirry vasemmalle tai oikealle, kunnes löydät erän, jonka päivämäärä on eri kuin yli puolella vakion arvosta. Kaikki myöhemmät elementit, kun siirretään sekä oikealle että vasemmalle, eivät ole meille mielenkiintoisia, koska niille päivien ero vain kasvaa, koska taulukon elementit tilattiin alun perin. Tämä lähestymistapa säästää merkittävästi aikaa, kun juhlien määrä ja niiden päivämäärät ovat huomattavasti suuret.
Sarjan peittämisongelma on -vaikea, mikä tarkoittaa, että sen ratkaisemiseen ei ole nopeaa (jossa toiminta-aika on yhtä suuri kuin syöttötiedon polynomi) ja tarkkaa algoritmia. Siksi joukon peittoongelman ratkaisemiseksi valittiin nopea ahne algoritmi, joka ei tietenkään ole tarkka, mutta jolla on seuraavat edut:
- Pienikokoisille ongelmille (ja tämä on juuri meidän tapauksemme) se laskee ratkaisut, jotka ovat melko lähellä optimia. Ongelman koon kasvaessa ratkaisun laatu heikkenee, mutta silti melko hitaasti;
- Erittäin helppo toteuttaa;
- Nopea, koska sen käyttöaikaarvio on .
Ahne algoritmi valitsee joukot seuraavan säännön perusteella: jokaisessa vaiheessa valitaan joukko, joka kattaa maksimimäärän vielä kattamattomia elementtejä. Yksityiskohtainen kuvaus algoritmista ja sen pseudokoodista löytyy
Sellaisen ahnealgoritmin tarkkuuden vertailua ratkaistavan ongelman testidatalla muihin tunnettuihin algoritmeihin, kuten todennäköisyyspohjaiseen ahneusalgoritmiin, muurahaisyhdyskuntaalgoritmiin jne., ei ole tehty. Tulokset tällaisten algoritmien vertaamisesta generoituun satunnaisdataan löytyy
Algoritmin toteutus ja toteutus
Tämä algoritmi toteutettiin kielellä 1S ja se sisällytettiin ulkoiseen käsittelyyn nimeltä "Residue Compression", joka oli yhdistetty WMS-järjestelmä. Emme toteuttaneet algoritmia kielellä C ++ ja käyttää sitä ulkoisesta natiivikomponentista, mikä olisi oikeampaa, koska koodin nopeus on pienempi C + + kertaa ja joissakin esimerkeissä jopa kymmeniä kertoja nopeammin kuin vastaavan koodin nopeus 1S. Kielen päällä 1S Algoritmi toteutettiin säästämään kehitysaikaa ja helpottamaan virheenkorjausta asiakkaan tuotantokannassa. Algoritmin tulos on esitetty kuvassa 5.
Kuva 5. Käsittely jäämien "puristamiseksi".
Kuvasta 5 näkyy, että määritellyssä varastossa varastosolujen nykyiset tavarasaldot on jaettu klustereihin, joissa tavaraerien päivämäärät eroavat toisistaan enintään 30 päivää. Koska asiakas valmistaa ja varastoi varastossa metallisia palloventtiilejä, joiden säilyvyys on laskettu vuosina, tällainen päivämääräero voidaan jättää huomiotta. Huomaa, että tällaista käsittelyä käytetään tällä hetkellä systemaattisesti tuotannossa ja toimijoissa WMS varmistaa puolueryhmittymän hyvän laadun.
Johtopäätökset ja jatko
Suurin kokemus, jonka saimme tällaisen käytännön ongelman ratkaisemisesta, on vahvistus paradigman käytön tehokkuudesta: matematiikka. ongelman ilmaisu kuuluisa matto. malli kuuluisa algoritmi algoritmi ottaa huomioon ongelman erityispiirteet. Diskreetti optimointi on ollut olemassa yli 300 vuotta, ja tänä aikana ihmiset ovat onnistuneet pohtimaan monia ongelmia ja keräämään paljon kokemusta niiden ratkaisemisesta. Ensinnäkin on suositeltavaa kääntyä tämän kokemuksen puoleen ja vasta sitten aloittaa pyörän keksiminen uudelleen.
Seuraavassa artikkelissa jatkamme tarinaa optimointialgoritmeista ja tarkastelemme mielenkiintoisinta ja paljon monimutkaisempaa: solujäännösten optimaalisen "pakkauksen" algoritmia, joka käyttää syötteenä eräklusterointialgoritmista saatua dataa.
Valmisteli artikkelin
Roman Shangin, projektiosaston ohjelmoija,
Ensimmäinen BIT-yhtiö, Tšeljabinsk
Lähde: will.com