Diszkrét matematika a WMS-hez: termékek tömörítési algoritmus a tárolókban (1. rész)

A cikkben arról beszélünk, hogy miként oldottuk meg a raktáron belüli szabad cellák hiányának problémáját és a diszkret optimalizálás algoritmusának kidolgozásáról egy ilyen feladat megoldására. Beszámolunk arról is, hogyan "építettük" fel az optimalizálási feladat matematikai modelljét, és milyennel váratlan nehézségekkel szembesültünk a bemeneti adatok feldolgozása során az algoritmushoz.

Ha érdeklik a matematika alkalmazásai az üzletben, és nem fél a kemény, 5. osztályos szintű képletátalakításoktól, akkor szeretettel várjuk a folytatásban!

A cikk hasznos lesz azok számára, akik bevezetik WMS-rendszereket, dolgoznak a raktározási vagy gyártási logisztika területén, valamint programozóknak, akik érdeklődnek a matematika üzleti alkalmazásai és a folyamatok optimalizálása iránt a vállalatban.

Bevezető rész

Ez a publikáció folytatja azon cikkek sorozatát, amelyekben megosztjuk sikeres tapasztalatainkat az optimalizáló algoritmusok raktári folyamatokba történő bevezetéséről.

A előző cikkben leírja a raktár specifikumait, ahol bevezettük a WMS-rendszert, valamint elmondja, miért kellett megoldanunk a termékmaradványok csoportosításának feladatát a WMS-rendszer bevezetése során, és hogy hogyan tettük ezt.

Amikor befejeztük az optimalizálási algoritmusokról szóló cikk írását, nagyon hosszúra sikeredett, ezért az összegyűjtött anyagot két részre osztottuk:

• Az első részben (ez a cikk) arról mesélünk, hogyan "építettük" fel a feladat matematikai modelljét, és hogy milyen komoly nehézségekkel szembesültünk a bemeneti adatok feldolgozása és átalakítása során az algoritmushoz.
• A második részben részletesen megvizsgáljuk az algoritmus implementálását C++, végzünk egy számítási kísérletet és összefoglaljuk azokat a tapasztalatokat, amelyeket a "intelligens technológiák" üzleti folyamatokba való bevezetése során szereztünk.

Hogyan olvassuk el a cikket. Ha olvastad az előző cikket, azonnal áttérhetsz az "Existing Solutions Overview" fejezetre, ha nem, akkor a problémák leírása a lenti spoilerben található.

A megoldandó probléma leírása a megbízó raktárában

Szűk keresztmetszetek a folyamatokban

2018-ban projektet indítottunk a WMS-rendszer bevezetésére a "LD Kereskedelmi Ház" raktárában Cseljabinszkban. Az "1C-Logistics: Raktárkezelés 3" terméket 20 munkahelyre telepítettük: operátorok WMS, raktárosok, targonca vezetők. A raktár közepes méretű, körülbelül 4000 m2, 5000 rekesszel és 4500 SKU-val rendelkezik. A raktárban saját gyártású golyós szelepek találhatók különböző méretekben, 1 kg-tól 400 kg-ig. A raktáron lévő készletek tételre vannak tárolva, mivel szükség van a FIFO alapján történő kiválasztásra.

A raktári folyamatok automatizálásának tervezése során szembesültünk a készletek nem optimális tárolásával kapcsolatos problémával. A szelepek tárolásának és elhelyezésének sajátossága az, hogy egy rekeszben csak egy tétel azonosságú áruk tárolhatók (lásd 1. ábra). A termékek naponta érkeznek a raktárba, és minden érkezés egy külön tételt jelent. Összesen, egy hónap raktározási munkája során 30 különböző tétel keletkezik, mindegyiket külön rekeszben kell tárolni. A termékek gyakran nem teljes raklapokban, hanem darabokban kerülnek kiválasztásra, és ennek következtében a darabválasztási zónában számos rekeszben a következő kép figyelhető meg: egy 1 m3-nél nagyobb térfogatú rekeszben több darab szelep található, amelyek az űrtartalomnak kevesebb mint 5-10%-át teszik ki.

1. ábra. Néhány darab a rekeszben

Nem optimális a raktári kapacitás kihasználása. A probléma mértékének ismeretében a következő adatokat hozhatom fel: átlagosan az 1 m3-nél nagyobb rekeszek száma, amelyekben "elhanyagolható" maradék található, a raktár működési időszakai alatt 100-tól 300-ig terjed. Mivel a raktár viszonylag kicsi, a raktári terhelési szezonokban ez a tényező "szűk keresztmetszetté" válik, amely jelentősen lassítja a raktári folyamatokat, mint a be- és kirakodás.

A probléma megoldásának ötlete

Felmerült az ötlet: a legközelebbi dátummal rendelkező maradék tételeket egy közös tételbe egyesíteni, és ezeket a megszorított tételeket kompakt módon egy rekeszben, vagy néhány rekeszben elhelyezni, ha az egy rekeszbe nem fér el az összes maradék mennyisége. Az ilyen "összenyomás" példáját a 2. ábra mutatja.

2. ábra. A maradékok összenyomásának ábrázolása a rekeszekben

Ez jelentősen csökkenti a raktározási területet, amelyeket az újonnan beérkező áruk számára fognak használni. Amikor a raktári kapacitás túlterhelt, ez a lépés rendkívül szükséges, különben előfordulhat, hogy nem marad szabad hely az új áruk elhelyezésére, ami a raktározási és táplálkozási folyamatok leállását eredményezi, és ennek következtében a beérkezés és kiszállítás leállását is. A WMS-rendszer bevezetése előtt ezt a műveletet kézzel hajtották végre, ami nem volt hatékony, mivel a megfelelő készletek keresési folyamata elég hosszú volt. Most, a WMS-rendszer bevezetésével automatikussá tettük, felgyorsítottuk és intelligenssé tettük ezt a folyamatot.

A feladat megoldásának folyamata két lépésre oszlik:

• az első lépésben közel álló, időpont szerint csoportosított tételeket keresünk a tömörítéshez (ehhez a feladathoz tartozik) az előző cikk);
• a második lépésben pedig minden egyes tételcsoporthoz kiszámítjuk a lehető legkompaktabb készletelhelyezést a rekeszekben.

A jelen cikkben a szakasz második lépésére összpontosítunk.

A meglévő megoldások áttekintése

Mielőtt áttérnénk az általunk kidolgozott algoritmusok leírására, érdemes rövid áttekintést adni az már a piacon lévő rendszerekről, WMSamelyek megvalósítják ezt a fajta optimális tömörítési funkciót.

Elsősorban érdemes megjegyezni a „1C: Vállalat 8. WMS Logisztika. Raktárkezelés 4” terméket, amely a 1C cég tulajdona és forgalmazza, és a negyedik generációhoz tartozik WMS-szoftverek, amelyeket az AXELOT cég fejlesztett ki. Ennél a rendszerben be van jelentve a tömörítési funkció, amely arra hivatott, hogy egy közös rekeszbe egyesítse a szétszórt készleteket. Fontos megjegyezni, hogy a tömörítési funkció egy ilyen rendszerben más lehetőségeket is tartalmaz, például a termékek elhelyezésének kiigazítását a rekeszekben az ABC osztályok szerint, de ezekre nem térünk ki.

Ha elemezzük a "1C: Vállalat 8. WMS Logisztika. Raktárkezelés 4" rendszer kódját (amely ezen funkció részében nyílt), akkor a következőket lehet megállapítani. A készletkompressziós algoritmus meglehetősen primitív lineáris logikát valósít meg, és nem beszélhetünk semmiféle "optimális" kompresszióról. Természetesen nem számol a tételek klaszterezésével. Néhány ügyfél, akinél ilyen rendszer került bevezetésre, panaszkodott a kompresszió tervezésének eredményeire. Például, a gyakorlatban gyakran előfordult, hogy 100 db termék készlete egy raktári cellából egy másikba lett tervezve, ahol 1 db termék fekszik, holott időköltségek szempontjából optimálisabb lett volna az ellenkezője.

A termékek készletkompressziójának funkciója sok külföldi WMS-rendszerben is meg van hirdetve, de sajnos sem valós visszajelzésünk nincs az algoritmusok hatékonyságáról (ez üzleti titok), sem pedig információnk azok logikai mélységéről (zárt forráskódú szoftver), ezért nem tudunk véleményt mondani.

Matematikai modell keresése

Ahhoz, hogy kvalitásos algoritmusokat tervezhessünk a probléma megoldására, először ezt a problémát világosan matematikai formába kell önteni, ami meg is fog történni.

Számos -ban lévő raktári cella található, amelyben egy adott termék készletei vannak. Ezeket a cellákat ezentúl donor celláknak nevezzük. Az a cellában lévő termék mennyiségét jelöli. $.

Fontos megemlíteni, hogy a tömörítési eljáratban csak egy termék egy tételből, vagy több tétel, amelyet előtte klaszterbe egyesítettek (lásd: az előző cikket), vehet részt, mivel a termékek tárolásának és elhelyezésének sajátosságai ezt indokolják. Különböző termékek vagy különböző tétel klaszterek esetén saját külön tömörítési eljárást kell elindítani.

Számos a donor cellákból potenciálisan elhelyezhető készletek számára. Ezeket a cellákat ezután tároló celláknak nevezzük. Ezek lehetnek a raktárban szabad cellák, valamint donor cellák a -ból. Mindig a halmaz egy részhalmaza. .

Minden a halmazból készletkapacitási korlátokkal rendelkezik. , amelyeket dm3-ben mérünk. Egy dm3 egy 10 cm oldalhosszúságú kockát jelent. A raktárban tárolt termékek viszonylag nagyok, ezért ebben az esetben elegendő ez a diszkrét mérés.

Meg van határozva a legrövidebb távolságok mátrixa méterben minden cellapár között , ahol és tartoznak halmazokhoz és vagy.

Jelöljük a termékek cellából való mozgásához tartozó "költségeket" egy cellába . Jelöljük a konténer kiválasztásának "költségeit" az abba más cellákból származó maradékok áthelyezéséhez. Hogy pontosan és milyen mértékegységben számítjuk ki az értékeket és később tárgyaljuk (lásd a bemeneti adatok előkészítése szakaszt), most elegendő annyit mondani, hogy ezek a mennyiségek arányosak lesznek a és vagy.

jelöljük jelöljük azt a változót, amely 1 értéket vesz fel, ha a cellából az áru a konténerbe , és 0-t ellenkező esetben. Jelöljük azt a változót, amely 1 értéket vesz fel, ha a konténer az áruk maradványait tartalmazza, és 0-t ellenkező esetben.

A feladat így van megfogalmazva: meg kell találni egy olyan konténerhalmazt és így "hozzácsatolni" a donorcellákat a konténer cellákhoz, hogy minimalizáljuk a funkciót

korlátozások mellett

Összességében a probléma megoldása során arra törekszünk,

• egyrészt, hogy csökkentsük a raktározási kapacitásokat;
• másrészt, hogy csökkentsük a raktárosok idejét.

Az utolsó korlátozás azt jelenti, hogy nem mozoghatunk árukat olyan konténerbe, amelyet nem választottunk ki, és így nyilvánvalóan nem "tartottunk költségeket" a kiválasztására. Ez a korlátozás azt is jelenti, hogy az egyes cellákból a konténerbe áthelyezett áruk volumene nem haladhatja meg a konténer kapacitását. A probléma megoldása alatt értjük a konténerek halmazát és a donorcellák konténerekhez való hozzácsatolásának módjait.

Ez a feladatoptimalizálás megfogalmazás nem új, és számos matematikus már az 1980-as évek eleje óta kutatta. A külföldi irodalomban két optimalizálási probléma található megfelelő matematikai modellel: Single-Source Capacitated Facility Location Problem és Multi-Source Capacitated Facility Location Problem (a feladatok közötti különbségekről később beszélünk). Érdemes megemlíteni, hogy a matematikai irodalomban e két optimalizálási feladat megfogalmazásai a vállalatok elhelyezésével kapcsolatos kifejezésekkel bírnak, innen a „Facility Location” elnevezés. Ez nagyrészt hagyomány, mivel a logisztikai területről érkezett először a szükséglet az ilyen kombinatorikus feladatok megoldására, főként a katonai-ipari szektorban az 1950-es években. A vállalatok elhelyezésének vonatkozásában az ilyen feladatok a következőképpen vannak megfogalmazva:

• Van egy véges városok halmaza, ahol potenciálisan elhelyezhetők a termelői üzemek (továbbiakban termelő városok). Minden termelő város esetében meg vannak határozva a vállalat megnyitásának költségei, valamint a megnyitott üzemben a termelési kapacitás korlátai.
• Van egy véges városok halmaza, ahol ténylegesen ügyfelek találhatók (továbbiakban ügyfél városok). Minden ilyen ügyfél város esetében meg van határozva a termék iránti kereslet nagysága. Az egyszerűség kedvéért tegyük fel, hogy az üzemben termelt és az ügyfelek által fogyasztott termék azonos.
• Minden egyes termelő város és ügyfél város párjára meg van határozva a szállítási költségek mértéke a szükséges termékmennyiség gyártójától az ügyfélig.

Meg kell határozni, hogy mely városokban nyissanak üzemeket, és hogyan csatolják az ügyfeleket ezekhez az üzemekhez, úgy, hogy:

• A vállalatok megnyitási és a szállítási költségek összesített értéke minimális legyen;
• Az egy nyitott üzemhez csatlakozó ügyfelek keresletének volumene ne haladja meg ennek az üzemnek a termelési kapacitását.

Most érdemes megemlíteni a két klasszikus feladat közötti egyetlen különbséget:

• Single-Source Capacitated Facility Location Problem – az ügyfél csak egy nyitott üzemtől kap ellátást;
• Multi-Source Capacitated Facility Location Problem – az ügyfél több nyitott üzemtől is egyidejűleg megkaphatja az ellátást.

Ez a két feladat közötti különbség első pillantásra jelentéktelennek tűnhet, de valójában teljesen eltérő kombinatorikus struktúrákat eredményez, és ennek következtében teljesen eltérő algoritmusokat a megoldásukra. A feladatok közötti különbségek az alábbi ábrán találhatók.

Ábra 3. a) Multi-Source Capacitated Facility Location Problem

Ábra 3. b) Single-Source Capacitated Facility Location Problem

Mindkét feladat -nehezen, tehát nincs pontos algoritmus, amely a bemeneti adatok méretének polinomiális idejében megoldaná ezt a feladatot. Egyszerűbb szavakkal: minden pontos algoritmus, amely a feladat megoldására készült, exponenciális időt fog igényelni, bár lehet, hogy gyorsabban, mint a brutális erővel történő átvizsgálás. Mivel a feladat -nehéz, ezért csak közelítő heurisztikákat fogunk figyelembe venni, vagyis olyan algoritmusokat, amelyek stabilan a közel optimális megoldásokat számítanak ki, és elég gyorsan működnek. Ha érdeklődés merül fel ilyen problémák iránt, akkor itt található egy jó összefoglaló oroszul.

Ha a feladatunk termékek optimális tárolására vonatkozó terminológiáját alkalmazzuk, akkor:

• a városok-ügyfelek – donor cellák maradványi termékekkel,
• a városok-termelők – konténer cellák , ahová a többi cellából származó maradványokat szándékoznak elhelyezni,
• szállítási költségek – időtartam költségek a raktáros számára a termékmennyiség mozgatása a donor cellából a konténer cellába ;
• vállalat alapításának költsége – a konténer kiválasztásának költsége , amely egyenlő a konténer cella térfogatával , megszorozva egy bizonyos szabad térfogat megtakarítási tényezővel (a tényező értéke mindig > 1) (lásd a bemeneti adatok előkészítése szakaszt).

Miután a hasonlóság az ismert klasszikus szállítási problémákkal elkészült, fontos kérdésre kell válaszolnunk, amely meghatározza a megoldási algoritmus architektúrájának kiválasztását: a maradványok áthelyezése a donor cellából csak egyetlen konténerbe (Single-Source) lehetséges, vagy a maradványok több konténer cellába (Multi-Source) is áthelyezhetőek?

Érdemes megjegyezni, hogy gyakorlatilag mindkét feladatfelállás létezik. Az alábbiakban felsoroljuk az egyes feladatfelállások előnyeit és hátrányait:

1. táblázat. Az Egyszórás és Többforrásos megoldások előnyei és hátrányai.

Mivel az Egyszórás változat előnyeinek száma magasabb, és figyelembe véve, hogy minél kevesebb a készlet a donor rekeszekben, annál kisebb a tömörítési fok különbsége a két megoldás között, a választásunk az Egyszórás változatra esett.

Meg kell említeni, hogy a Többforrásos megoldás is hasznos lehet. Számos hatékony algoritmus létezik ennek megoldására, amelyek többsége a szállítási feladatok megoldására redukálható. Vannak nemcsak hatékony, hanem elegáns algoritmusok is, például, itt.

A bemeneti adatok előkészítése

Mielőtt nekilátnánk az algoritmus elemzésének és kidolgozásának a feladat megoldására, meg kell határoznunk, hogy milyen adatokat és milyen formában fogunk benyújtani neki. A donor rekeszek termékkészleteivel és a tárolórekeszek kapacitásával nincs probléma, mivel ez triviális – ezeket m3-ben mérjük, de a tárolórekesz használatával kapcsolatos költségekkel és a mozgatás költségmátrixával nem minden olyan egyszerű!

Először nézzük meg a számítást. áru mozgatási költségei a donor rekeszből a konténer rekeszbe. Először is meg kell határoznunk, hogy milyen mértékegységekben számítjuk a mozgatási költségeket. Két nyilvánvaló lehetőség van – méter és másodperc. A „tiszta” méterekben történő számítás értelmetlen. Mutassuk be példával. Tegyük fel, hogy a rekesz az első szinten található, és a rekesz 30 méterre van és a második szinten helyezkedik el:

• A mozgatás be. költségesebb, mint a mozgatás a be. , mivel a második szintről (1,5-2 méter a padlótól) leereszteni könnyebb, mint a második szintre felemelni, bár a megtett távolság ugyanaz lesz;
• 1 db termék mozgatása a rekeszből be. könnyebb lesz, mint 10 db ugyanazon termék mozgatása, bár a megtett távolság ugyanaz lesz.

A mozgatási költségeket jobb másodpercekben figyelembe venni, mivel ez lehetővé teszi a szintek közötti különbség és a mozgatott termék mennyiségének figyelembevételét is. A másodpercekben történő költségszámításhoz fel kell bontanunk a mozgatási műveletet elemi összetevőkre, és időméréseket kell végeznünk minden egyes elemi összetevő végrehajtásához.

Tegyük fel, hogy a rekeszből rekeszbe mozgatják a db terméket. Tegyük fel, hogy – a munkavállaló átlagos mozgási sebessége a raktárban, m/s-ban mérve. Tegyük fel, hogy és – az egyes műveletek elvégzésének átlagos sebessége, amit egy alkalommal 4 dm3 terméknél vesznek fel (az a közép, amit egy munkavállaló a raktárban végez műveletek során). Tegyük fel, hogy és a rekeszek magassága, ahonnan a műveleteket végzik. Például, az első szint (padló) átlagos magassága 1 m, a második szint 2 m és így tovább. Akkor az általános idő kiszámítására vonatkozó formula a mozgatási művelet elvégzésére a következő:

A 2. táblázat tartalmazza az egyes elemi műveletek végrehajtásának időstatisztikáját, amelyet a raktári dolgozók gyűjtöttek össze a tárolt áru sajátosságainak figyelembevételével.

Művelet megnevezése	Jelölés	Átlagérték
A munkavállaló átlagos mozgási sebessége a raktárban		1,5 m/s
Az egy művelet elvégzésének átlagos sebessége, hogy elhelyezze (4 dm3 termék esetén)		2,4 másodperc

2. táblázat. A raktári műveletek átlagos végrehajtási ideje

Megállapítottuk a mozgatási költségek számításának módját. Most meg kell deríteni, hogyan számítsuk ki a konténer rekesz kiválasztásának költségeitItt minden sokkal, sokkal bonyolultabb, mint a szállítási költségekkel kapcsolatosan, mivel:

• először is, a költségeknek közvetlenül kell függniük a cellák térfogatától – ugyanazt a maradékot a donor cellákból jobban egy kisebb konténerbe tenni, mint egy nagyba, feltéve, hogy ez a térfogat teljes mértékben elfér mindkét konténerben. Így az összköltségek minimalizálása érdekében a konténerek kiválasztásakor arra törekszünk, hogy megtakarítsuk a „deficites” szabad raktártér elérhetőségét a kiválasztási zónában a további termékek elhelyezésének elvégzéséhez. A 4. ábrán bemutatásra kerülnek a maradékok különböző méretű konténerekbe való szállítása és e szállítási lehetőségek következményei a további raktári műveletek során.
• másodszor, mivel az alapfeladatunkban minimalizálni kell az összes költséget, ami a szállítási költségek és a konténer kiválasztásával kapcsolatos költségek összege, a cellák térfogatát köbméterben valahogyan össze kell hangolni a másodpercekkel, ami közel sem trivális feladat.

4. ábra. A maradékok szállításának lehetőségei különböző kapacitású konténerekbe.

A 4. ábrán pirossal van ábrázolva a maradék térfogata, ami már nem fér el a konténerben a következő termékek elhelyezésének második szakaszában.

Segít összekapcsolni a köbméteres konténerkiválasztási költségeket a szállítási idő másodperceivel az alábbi követelmények figyelembevételével a probléma megoldásához:

• Szükséges, hogy a donor cellából a konténer cellába áthelyezendő maradékok minden esetben el legyenek helyezve, ha ez csökkenti az összes konténer cellák számát, amelyben a termék található.
• Meg kell tartani az egyensúlyt a konténerek térfogata és a szállítási idő költségei között: például, ha az új megoldásváltozatban a térfogatban jelentős nyereség tapasztalható a korábbi megoldáshoz képest, míg az időbeliségi kiadás minimális, akkor az új megoldásváltozatot kell választani.

Kezdjük az utolsó követelménnyel. Annak érdekében, hogy konkretizáljuk a sokértelmű 'egyensúly' szót, felmérést végeztünk a raktári munkatársak körében, hogy kiderítsük a következőt. Legyen egy konténer cella térfogata , amelybe a maradék termékek áthelyezése a donor cellákból van előírva és ennek a szállításnak az összidőtartama egyenlő . Legyen még néhány alternatív lehetőség a termékek ugyanazon donor sejtekből való elhelyezésére más konténerekben, ahol minden elhelyezésnek megvannak a saját értékelései. , ahol < és , ahol >.

Felvetődik a kérdés: milyen minimális térfogatnyereség elfogadható, a megadott időveszteség mellett? elfogadható, a megadott időveszteség értékénél. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

5. ábra. A minimálisan elfogadható térfogatmegtakarítás és az üzemelési idő különbségének növekedése közötti kapcsolat diagramja.

Tehát, ha a további időköltség 40 másodperc, akkor csak akkor vagyunk hajlandók ezt felvállalni, ha a térfogatnyereség legalább 500 dm³. Annak ellenére, hogy a függésben van egy kis nemlinearitás, a további számítások egyszerűsítése érdekében tekintsük a mennyiségek közötti kapcsolatot lineárisnak, amelyet egy egyenlőtlenség ír le.

Az alábbi ábrán megvizsgáljuk a termékek konténerekbe való elhelyezésének következő módjait.

6. ábra. A. variáció: 2 konténer, összterfogat 400 dm³, összidő 150 másodperc.

6. ábra. B. variáció: 2 konténer, összterfogat 600 dm³, összidő 190 másodperc.

6. ábra. C. variáció: 1 konténer, összterfogat 400 dm³, összidő 200 másodperc.

A konténerek választásának (a) variációja előnyösebb, mint az eredeti variáció, mivel az egyenlőtlenség teljesül: (800-400)/10 >= 150-120, ami azt jelenti, hogy 40 >= 30. A (b) variáció kevésbé előnyös, mint az eredeti, mivel az egyenlőtlenség nem teljesül: (800-600)/10 >= 190-150, amiből következik, hogy 20 >= 40. De a (c) variáció nem illeszkedik ehhez a logikához! Vizsgáljuk meg ezt a variációt részletesebben. Egyrészről az egyenlőtlenség (800-400)/10 >= 200-120, ami azt jelenti, hogy az egyenlőtlenség 40 >= 80 nem teljesül, ami azt sugallja, hogy a térfogatnyereség nem ér annyira nagy időveszteséget.

De másrészről, a (c) variációval nem csak a foglalt összterfogatot csökkentjük, hanem a foglalt cellák számát is, ami az említett számítási megoldások első fontos követelménye. Nyilvánvaló, hogy a követelmény teljesítéséhez valamilyen pozitív konstansot kell hozzáadni az egyenlőtlenség bal oldalához. , és ezt a konstansot csak akkor kell hozzáadni, amikor a konténerek száma csökken. Emlékezzünk, hogy — ez a változó 1, amikor a konténer választva van, és 0, amikor a konténer ki van választva. nem lett kiválasztva. Jelöljük meg, – több tartály az eredeti megoldásban és – több tartály az új megoldásban. Általános formában az új egyenlőtlenség így fog kinézni:

A fenti egyenlőtlenség átalakításával kapjuk

Ebből következően van egy képletünk az összköltség kiszámítására valamely megoldásváltozat esetén:

De most felmerül a kérdés: milyen értéke kell, hogy legyen ennek a konstansnak ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Legyen – a raktár egy zónájának rekeszei közötti maximális távolság, ami az esetünkben 100 m. Legyen – a raktáron lévő rekesz-tartály maximális térfogata, ami az esetünkben 1000 dm3.

Az első módszer a mennyiség kiszámítására. Vizsgáljuk meg azt a helyzetet, amikor van 2 tartály az első sorban, amelyekben már fizikailag van áru, tehát ezek önálló rekesz-donorok, és az áruk ugyanabba a rekeszbe való mozgatásának költsége természetesen 0. Meg kell találni egy olyan konstans értéket , amelynél mindig érdemes lenne az 1-es tartályból a 2-es tartályba mozgatni a maradékokat. Az értékek helyettesítésével és az előző egyenlőtlenségbe kapjuk:

amiből következik

Az elemi műveletek átlagos végrehajtási idejének értékeinek helyettesítésével a fenti képletbe kapjuk

A mennyiség kiszámításának második módja. Vizsgáljuk meg azt a helyzetet, amikor vannak rekesz-donorok, ahonnan árut terveznek mozgatni az 1-es tartályba. Jelöljük – a donor rekesz és az 1-es tartály közötti távolságot. Van továbbá egy 2-es tartály, amiben már vannak áruk, és a térfogata lehetővé teszi, hogy befogadja a maradékokat az összes rekeszből. Az egyszerűség kedvéért feltételezzük, hogy a donor rekeszekből a tartályokba mozgatott áru térfogata azonos és . Meg kell találni egy olyan konstans értéket , amelynél az összes maradék elhelyezése a rekeszekben a 2-es tartályban mindig kedvezőbb lenne, mint különböző tartályokban elhelyezni őket: Az egyenlőtlenség átalakításával kapjuk

Ahhoz, hogy "megerősítsük" a mennyiség értékét

, fogadjuk el, hogy = 0. Az átlagos rekeszek száma, amelyek általában részt vesznek a maradékok tömörítési eljárásában, 10. Az ismert értékek helyettesítésével az alábbi konstans értéket kapjuk Válasszuk ki a legnagyobb értéket, amelyet minden változat alapján számoltunk, ez lesz a mennyiség értéke

az adott tárolóparaméterekhez. Most a teljesség kedvéért rögzítsük a képletet az összes költség kiszámítására valamely elfogadható megoldás esetén egy bizonyos megengedett megoldás esetén :

Most már, az összes kolosszus erőfeszítés után az input adatok átalakításában, elmondhatjuk, hogy az összes bemeneti adat a megfelelő formába került és készen áll az optimalizáló algoritmus használatára.

Zárás

A gyakorlat azt mutatja, hogy az input adatok előkészítésének és átalakításának munkaköltségét és fontosságát gyakran alábecsülik. Ebben a cikkben különös figyelmet fordítottunk erre a lépésre, hogy megmutassuk, hogy csak megfelelően, minőségben előkészített input adatok tehetik az algoritmus által számolt megoldásokat igazán értékessé az ügyfél számára. Igen, sok képletet leírtunk, de már a kata előtt figyelmeztettünk 🙂

A következő cikkben végre elérjük azt, amiért az előző 2 publikáció készült – a diszkrét optimalizálási algoritmust.

A cikket készítette
Roman Shangin, a projektek osztály programozója,
a First Bit cég, Cseljabinszk

Forrás: habr.com