Diskrétna matematika pre WMS: Algoritmus na kompresiu tovaru v bunkách (časť 1)

V tomto článku vám povieme, ako sme vyriešili problém nedostatku voľných buniek v sklade a vyvinuli sme diskrétny optimalizačný algoritmus na vyriešenie takéhoto problému. Porozprávajme sa o tom, ako sme „zostavili“ matematický model optimalizačného problému a o ťažkostiach, s ktorými sme sa neočakávane stretli pri spracovaní vstupných údajov pre algoritmus.

Ak vás zaujímajú aplikácie matematiky v biznise a nebojíte sa strnulých premien identity vzorcov na úrovni 5. ročníka, tak vitajte v mačke!

Článok bude užitočný pre tých, ktorí implementujú WMS-systémy, pracuje v odvetví skladovej alebo výrobnej logistiky, ako aj programátori, ktorí sa zaujímajú o aplikácie matematiky v podnikaní a optimalizáciu procesov v podniku.

Úvodná časť

Táto publikácia pokračuje v sérii článkov, v ktorých sa delíme o naše úspešné skúsenosti s implementáciou optimalizačných algoritmov v skladových procesoch.

В predchádzajúci článok popisuje špecifiká skladu, kde sme realizovali WMS-systém, a tiež vysvetľuje, prečo sme pri implementácii potrebovali vyriešiť problém zhlukovania dávok zvyšného tovaru WMS-systémy a ako sme to urobili.

Keď sme dokončili písanie článku o optimalizačných algoritmoch, ukázalo sa, že je veľmi veľký, a tak sme sa rozhodli rozdeliť nahromadený materiál na 2 časti:

• V prvej časti (tento článok) si povieme o tom, ako sme „zostavili“ matematický model problému a o veľkých ťažkostiach, s ktorými sme sa nečakane stretli pri spracovaní a transformácii vstupných dát do algoritmu.
• V druhej časti sa budeme podrobne zaoberať implementáciou algoritmu v jazyku C + +, urobíme výpočtový experiment a zhrnieme skúsenosti, ktoré sme získali pri implementácii takýchto „inteligentných technológií“ do podnikových procesov zákazníka.

Ako čítať článok. Ak ste si prečítali predchádzajúci článok, môžete okamžite prejsť na kapitolu „Prehľad existujúcich riešení“, ak nie, potom je popis riešeného problému v spojleri nižšie.

Popis problému, ktorý sa rieši na sklade zákazníka

Prekážka v procesoch

V roku 2018 sme dokončili projekt na realizáciu WMS-systémy v sklade „Obchodný dom „LD“ v Čeľabinsku. Implementovali sme produkt „1C-Logistics: Warehouse Management 3“ pre 20 pracovísk: operátorov WMS, skladníci, vodiči vysokozdvižných vozíkov. Priemerný sklad je cca 4 tis. m2, počet buniek 5000 a počet SKU 4500. Sklad skladuje guľové kohúty vlastnej výroby rôznych veľkostí od 1 kg do 400 kg. Zásoby na sklade sú skladované v dávkach, keďže je potrebné vyberať tovar podľa FIFO.

Pri návrhu schém automatizácie skladových procesov sme sa stretli s existujúcim problémom neoptimálneho skladovania zásob. Špecifiká skladovacích a ukladacích žeriavov sú také, že jedna jednotková skladovacia bunka môže obsahovať iba položky z jednej šarže (pozri obr. 1). Produkty prichádzajú na sklad denne a každý príchod je samostatná dávka. Celkovo sa v dôsledku 1 mesiaca prevádzky skladu vytvorí 30 samostatných dávok, napriek tomu, že každá by mala byť uložená v samostatnej bunke. Výrobky sa často nevyberajú v celých paletách, ale v kusoch, a preto sa v zóne výberu kusov v mnohých bunkách pozoruje nasledujúci obrázok: v bunke s objemom väčším ako 1 m3 je niekoľko kusov žeriavov, ktoré zaberajú menej ako 5-10% objemu bunky.

Obr 1. Fotografia niekoľkých kusov v bunke

Je zrejmé, že skladovacia kapacita sa nevyužíva optimálne. Aby som si predstavil rozsah katastrofy, môžem uviesť čísla: v priemere existuje od 1 do 3 buniek takýchto buniek s objemom viac ako 100 m300 s „minimálnymi“ zostatkami počas rôznych období prevádzky skladu. Keďže sklad je relatívne malý, počas rušných období skladu sa tento faktor stáva „úzkym hrdlom“ a značne spomaľuje skladové procesy preberania a expedície.

Nápad na riešenie problému

Vznikol nápad: dávky zvyškov s najbližšími dátumami by sa mali zredukovať na jednu dávku a takéto zvyšky s jednotnou dávkou by sa mali umiestniť kompaktne spolu do jednej bunky alebo do viacerých, ak v jednej nie je dostatok miesta na umiestnenie celé množstvo zvyškov. Príklad takejto „kompresie“ je znázornený na obrázku 2.

Obr.2. Schéma na kompresiu zvyškov v bunkách

To vám umožní výrazne znížiť obsadené skladové priestory, ktoré budú použité na umiestnenie nového tovaru. V situácii, keď je kapacita skladu preťažená, je takéto opatrenie mimoriadne potrebné, inak jednoducho nemusí byť dostatok voľného miesta na umiestnenie nového tovaru, čo povedie k zastaveniu skladových procesov umiestňovania a doplňovania a v dôsledku toho na zastavenie prijímania a odosielania. Predtým, pred implementáciou systému WMS, sa takáto operácia vykonávala manuálne, čo bolo neefektívne, pretože proces hľadania vhodných zostatkov v bunkách bol dosť dlhý. Teraz, so zavedením systému WMS, sme sa rozhodli tento proces zautomatizovať, zrýchliť a urobiť ho inteligentným.

Proces riešenia takéhoto problému je rozdelený do 2 etáp:

• v prvej fáze nájdeme skupiny dávok s dátumom uzavretia kompresie (vyhradených na túto úlohu predchádzajúci článok);
• v druhej fáze vypočítame pre každú skupinu dávok najkompaktnejšie umiestnenie zvyšného tovaru v bunkách.

V aktuálnom článku sa zameriame na druhú fázu algoritmu.

Preskúmanie existujúcich riešení

Predtým, ako prejdeme k popisu algoritmov, ktoré sme vyvinuli, stojí za to urobiť krátky prehľad systémov, ktoré už existujú na trhu. WMS, ktoré implementujú podobnú funkciu optimálnej kompresie.

V prvom rade je potrebné poznamenať produkt „1C: Enterprise 8. WMS Logistics. Warehouse Management 4", ktorý vlastní a replikuje spoločnosť 1C a patrí do štvrtej generácie WMS-systémy vyvinuté spoločnosťou AXELOT. Tento systém si nárokuje kompresnú funkčnosť, ktorá je navrhnutá tak, aby zjednotila rôznorodé produkty v jednej spoločnej bunke. Za zmienku stojí, že kompresná funkcionalita v takomto systéme zahŕňa aj ďalšie možnosti, napríklad opravu umiestňovania tovaru v bunkách podľa ich tried ABC, tým sa však nebudeme zaoberať.

Ak analyzujete kód systému 1C: Enterprise 8. WMS Logistics. Správa skladu 4" (ktorá je otvorená v tejto časti funkcionality), môžeme uzavrieť nasledovné. Algoritmus reziduálnej kompresie implementuje pomerne primitívnu lineárnu logiku a o žiadnej „optimálnej“ kompresii nemôže byť ani reči. Prirodzene, nezabezpečuje zoskupovanie strán. Viacerí klienti, ktorí mali takýto systém implementovaný, sa sťažovali na výsledky plánovania kompresie. Napríklad často v praxi počas kompresie nastala nasledujúca situácia: 100 ks. Plánuje sa presun zvyšného tovaru z jednej bunky do druhej bunky, kde sa nachádza 1 kus. tovar, aj keď z hľadiska časovej náročnosti je optimálne robiť opak.

Taktiež funkčnosť stlačenia zvyšného tovaru v bunkách je deklarovaná v mnohých zahraničných krajinách. WMS-systémy, ale, žiaľ, nemáme skutočnú spätnú väzbu o účinnosti algoritmov (toto je obchodné tajomstvo), tým menej predstavu o hĺbke ich logiky (proprietárny softvér s uzavretým zdrojom), takže nemôžeme posúdiť.

Vyhľadajte matematický model problému

Aby sme mohli navrhnúť kvalitné algoritmy na riešenie problému, je najprv potrebné tento problém jasne matematicky formulovať, čo urobíme.

Existuje veľa buniek , ktoré obsahujú zvyšky nejakého tovaru. V nasledujúcom texte budeme takéto bunky nazývať darcovskými bunkami. Označme objem tovaru v bunke $.

Je dôležité povedať, že iba jeden výrobok z jednej šarže alebo niekoľko šarží predtým spojených do klastra (čítaj: predchádzajúci článok), čo je spôsobené špecifikami skladovania a skladovania tovaru. Rôzne produkty alebo rôzne klastre dávok by mali mať svoj vlastný samostatný postup kompresie.

Existuje veľa buniek , do ktorých môžu byť potenciálne umiestnené zvyšky z darcovských buniek. Takéto bunky budeme ďalej nazývať kontajnerovými bunkami. Môžu to byť buď voľné bunky v sklade alebo darcovské bunky z rôznych druhov . Vždy dostatok je podmnožina .

Pre každú bunku od mnohých Boli stanovené kapacitné obmedzenia merané v dm3. Jeden dm3 je kocka so stranami 10 cm Výrobky uložené v sklade sú pomerne veľké, takže v tomto prípade je takáto diskretizácia celkom dostatočná.

Daná matica najkratších vzdialeností v metroch medzi každým párom buniek Kde и patria do súprav и resp.

Označme „náklady“ na presun tovaru z bunky do bunky . Označme „náklady“ na výber kontajnera presunúť do nej zvyšky z iných buniek. Ako presne a v akých jednotkách merania sa budú počítať hodnoty и budeme ďalej uvažovať (pozri časť príprava vstupných údajov), zatiaľ stačí povedať, že takéto hodnoty budú priamo úmerné hodnotám и resp.

Označme podľa premenná, ktorá má hodnotu 1, ak je zvyšok z bunky presunuté do kontajnera a 0 inak. Označme podľa premenná, ktorá má hodnotu 1, ak kontajner obsahuje zvyšný tovar a 0 inak.

Úloha je uvedená nasledovne: musíte nájsť toľko kontajnerov a tak „pripájať“ darcovské bunky k bunkám zásobníka, aby sa minimalizovala funkcia

pod obmedzeniami

Celkovo sa pri výpočte riešenia problému snažíme:

• po prvé, aby sa ušetrila skladovacia kapacita;
• po druhé, aby sa ušetril čas skladníkov.

Posledné obmedzenie znamená, že nemôžeme premiestniť tovar do kontajnera, ktorý sme si nevybrali, a teda nám jeho výber „nevznikol“. Toto obmedzenie tiež znamená, že objem tovaru presúvaného z buniek do kontajnera by nemal presiahnuť kapacitu kontajnera. Riešením problému rozumieme sadu kontajnerov a spôsoby pripojenia darcovských buniek k nádobám.

Táto formulácia optimalizačného problému nie je nová a už od začiatku 80. rokov minulého storočia ju študovalo mnoho matematikov. V zahraničnej literatúre sú 2 optimalizačné problémy s vhodným matematickým modelom: Problém s umiestnením kapacitného zariadenia s jedným zdrojom и Problém s umiestnením viaczdrojového kapacitného zariadenia (o rozdieloch v úlohách si povieme neskôr). Stojí za to povedať, že v matematickej literatúre je formulácia takýchto dvoch optimalizačných problémov formulovaná z hľadiska umiestnenia podnikov v teréne, odtiaľ názov „Umiestnenie zariadenia“. Z veľkej časti ide o poctu tradícii, keďže potreba riešiť takéto kombinatorické problémy po prvý raz prišla z oblasti logistiky, prevažne z vojensko-priemyselného sektora v 50. rokoch minulého storočia. Pokiaľ ide o umiestnenie podniku, tieto úlohy sú formulované takto:

• Je obmedzený počet miest, kde je potenciálne možné umiestniť výrobné podniky (ďalej len výrobné mestá). Pre každé výrobné mesto sú špecifikované náklady na otvorenie podniku v ňom, ako aj obmedzenie výrobnej kapacity podniku otvoreného v ňom.
• Existuje obmedzený počet miest, kde sa klienti skutočne nachádzajú (ďalej len klientské mestá). Pre každé takéto klientske mesto je špecifikovaný objem dopytu po produktoch. Pre jednoduchosť budeme predpokladať, že existuje len jeden produkt, ktorý vyrábajú podniky a spotrebúvajú zákazníci.
• Pre každú dvojicu mesto-výrobca a mesto-klient je určená hodnota dopravných nákladov na dodanie požadovaného objemu produktov od výrobcu ku klientovi.

Musíte nájsť, v ktorých mestách otvoriť podniky a ako k takýmto podnikom pripojiť klientov, aby ste:

• Celkové náklady na otvorenie podnikov a náklady na dopravu boli minimálne;
• Objem dopytu od zákazníkov priradených k akémukoľvek otvorenému podniku nepresahoval výrobnú kapacitu tohto podniku.

Teraz stojí za zmienku jediný rozdiel v týchto dvoch klasických problémoch:

• Problém s umiestnením kapacitného zariadenia s jedným zdrojom – klient je zásobovaný iba z jedného otvoreného zariadenia;
• Problém s umiestnením viaczdrojového kapacitného zariadenia – klient môže byť zásobovaný z viacerých otvorených zariadení súčasne.

Takýto rozdiel medzi týmito dvoma problémami je na prvý pohľad zanedbateľný, ale v skutočnosti vedie k úplne inej kombinatorickej štruktúre takýchto problémov a v dôsledku toho k úplne odlišným algoritmom na ich riešenie. Rozdiely medzi úlohami sú znázornené na obrázku nižšie.

Obr.3. a) Problém s umiestnením viaczdrojového kapacitného zariadenia

Obr.3. b) Problém s umiestnením kapacitného zariadenia s jedným zdrojom

Obe úlohy -náročné, to znamená, že neexistuje presný algoritmus, ktorý by riešil takýto problém v časovom polynóme vo veľkosti vstupných dát. Jednoduchšie povedané, všetky presné algoritmy na riešenie problému budú fungovať v exponenciálnom čase, aj keď možno rýchlejšie ako úplné vyhľadávanie možností. Od úlohy -ťažké, potom budeme brať do úvahy iba približnú heuristiku, teda algoritmy, ktoré budú konzistentne počítať riešenia veľmi blízke optimálnym a budú fungovať pomerne rýchlo. Ak vás takáto úloha zaujala, dobrý prehľad v ruštine nájdete tu.

Ak prejdeme k terminológii nášho problému optimálnej kompresie tovaru v bunkách, potom:

• klientske mestá sú darcovské bunky so zvyšným tovarom,
• výrobné mestá – kontajnerové bunky , do ktorej majú byť umiestnené zvyšky z iných buniek,
• náklady na dopravu - časové náklady skladníka presunúť objem tovaru z darcovskej bunky do kontajnerovej bunky ;
• náklady na otvorenie podniku - náklady na výber kontajnera , ktorý sa rovná objemu kontajnerovej bunky , vynásobený určitým koeficientom pre úsporu voľných objemov (hodnota koeficientu je vždy > 1) (pozri časť príprava vstupných údajov).

Po nakreslení analógie so známymi klasickými riešeniami problému je potrebné odpovedať na dôležitú otázku, od ktorej závisí výber architektúry algoritmu riešenia: presun zvyškov z darcovskej bunky je možný len do jednej a iba jeden kontajner (Single-Source), alebo je možné presunúť zvyšky do niekoľkých buniek kontajnera (Multi-Source)?

Stojí za zmienku, že v praxi prebiehajú obe formulácie problému. Nižšie uvádzame všetky výhody a nevýhody každého takéhoto nastavenia:

Tabuľka 1. Výhody a nevýhody možností Single-Source a Multi-Source.

Keďže možnosť Single-Source má viac výhod a aj s prihliadnutím na fakt, že čím menší je počet zvyškov v darcovských bunkách, tým menší je rozdiel v stupni kompaktnosti kompresie vypočítanej pre oba varianty problému, naša voľba padla na možnosť Single-Source.

Stojí za to povedať, že sa uskutočňuje aj riešenie možnosti Multi-Source. Na jeho riešenie existuje veľké množstvo efektívnych algoritmov, z ktorých väčšina vychádza z riešenia množstva dopravných problémov. Existujú nielen efektívne algoritmy, ale aj elegantné, napr. tu.

Príprava vstupných údajov

Pred začatím analýzy a vývoja algoritmu na riešenie problému je potrebné rozhodnúť, aké dáta a v akej forme ich budeme podávať ako vstup. Neexistujú žiadne problémy s objemom zostávajúceho tovaru v darcovských bunkách a kapacitou kontajnerových buniek, pretože je to triviálne - takéto množstvá sa budú merať v m3, ale s nákladmi na použitie kontajnerovej bunky a maticou pohyblivých nákladov nie je všetko je to také jednoduché!

Najprv sa pozrime na výpočet náklady na presun tovaru z darcovskej bunky do kontajnerovej bunky. V prvom rade je potrebné rozhodnúť, v akých merných jednotkách budeme kalkulovať náklady na pohyb. Dve najzreteľnejšie možnosti sú metre a sekundy. Nemá zmysel počítať cestovné náklady v „čistých“ metroch. Ukážme si to na príklade. Nechajte bunku nachádza na prvej vrstve, bunke odstránené o 30 metrov a umiestnené na druhom poschodí:

• Presťahovanie sa z в drahšie ako sťahovanie в , pretože ísť dole z druhej vrstvy (1,5-2 metre od podlahy) je jednoduchšie ako ísť hore na druhú, aj keď vzdialenosť bude rovnaká;
• Presuňte 1 ks. tovar z bunky в Bude to jednoduchšie ako presunúť 10 kusov. rovnaký produkt, aj keď vzdialenosť bude rovnaká.

Je lepšie zvážiť náklady na presun v sekundách, pretože to umožňuje zohľadniť rozdiel v úrovniach aj rozdiel v množstve presunutého tovaru. Aby sme zohľadnili náklady na pohyb v sekundách, musíme operáciu pohybu rozložiť na jej základné zložky a zmerať čas potrebný na dokončenie každej základnej zložky.

Nechajte z cely sa pohybuje PC. tovar v kontajneri , nechať – priemerná rýchlosť pohybu pracovníka v sklade meraná v m/sec. Nechaj и – priemerné rýchlosti odberu a vloženia jednorazových operácií pri objeme tovaru 4 dm3 (priemerný objem, ktorý zamestnanec naraz odoberie na sklade pri vykonávaní operácií). Nechaj и výška buniek, z ktorých sa vykonávajú operácie take a put, resp. Napríklad priemerná výška prvého poschodia (poschodia) je 1 m, druhého poschodia je 2 m atď. Potom je vzorec na výpočet celkového času na dokončenie operácie presunu Ďalšie:

Tabuľka 2 zobrazuje štatistiku času vykonania každej základnej operácie, zhromaždenú zamestnancami skladu, berúc do úvahy špecifiká skladovaného tovaru.

názov operácie	Označenie	Zlý
Priemerná rýchlosť pracovníka pohybujúceho sa po sklade		1,5 m/s
Priemerná rýchlosť vkladania jednej operácie (pri objeme produktu 4 dm3)		2,4 sek

Tabuľka 2. Priemerný čas na dokončenie skladových operácií

Rozhodli sme sa pre spôsob výpočtu nákladov na sťahovanie. Teraz musíme zistiť, ako vypočítať náklady na výber kontajnerovej bunky. Všetko je tu oveľa, oveľa komplikovanejšie ako náklady na sťahovanie, pretože:

• po prvé, náklady by mali byť priamo závislé od objemu bunky – rovnaký objem zvyškov prenesených z darcovských buniek je lepšie umiestniť do nádoby s menším objemom ako do veľkej nádoby, za predpokladu, že sa takýto objem úplne zmestí do oboch nádob. Minimalizáciou celkových nákladov na výber kontajnerov sa teda snažíme ušetriť „nedostatkové“ voľné skladové kapacity vo výberovom priestore na vykonávanie následných operácií umiestňovania tovaru do buniek. Obrázok 4 ukazuje možnosti presunu zvyškov do veľkých a malých kontajnerov a dôsledky týchto možností presunu v následných skladových operáciách.
• po druhé, keďže pri riešení pôvodného problému potrebujeme presne minimalizovať celkové náklady, a to súčet nákladov na sťahovanie aj nákladov na výber kontajnerov, potom treba objemy buniek v kubických metroch nejako prepojiť so sekundami, čo ani zďaleka nie je triviálne.

Ryža. 4. Možnosti presunu zvyškov do kontajnerov s rôznou kapacitou.

Obrázok 4 zobrazuje červenou farbou objem zvyškov, ktoré sa už nezmestia do kontajnera v druhej fáze umiestňovania následného tovaru.

Pomôže prepojiť kubické metre nákladov na výber kontajnera so sekundami nákladov na presun nasledujúcich požiadaviek na vypočítané riešenia problému:

• Je nevyhnutné, aby sa zostatky z darcovského zásobníka v každom prípade presunuli do zásobníka, ak sa tým zníži celkový počet zásobníkov obsahujúcich produkt.
• Je potrebné udržiavať rovnováhu medzi objemom kontajnerov a časom stráveným presunom: napríklad ak pri novom riešení problému v porovnaní s predchádzajúcim riešením je prírastok objemu veľký, ale strata času je malá , potom je potrebné zvoliť novú možnosť.

Začnime poslednou požiadavkou. Aby sme objasnili nejednoznačné slovo „zostatok“, uskutočnili sme prieskum medzi zamestnancami skladu, aby sme zistili nasledovné. Nech existuje kontajnerová bunka objemu , ku ktorému je priradený pohyb zvyšného tovaru z darcovských buniek a celkový čas takéhoto pohybu sa rovná . Nech existuje niekoľko alternatívnych možností na umiestnenie rovnakého množstva tovaru z rovnakých darcovských buniek do iných kontajnerov, kde každé umiestnenie má svoje vlastné odhady Kde < и Kde >.

Je položená otázka: aký je minimálny prírastok objemu prijateľné pre danú hodnotu časovej straty ? Vysvetlíme si to na príklade. Pôvodne mali byť telesné pozostatky uložené do kontajnera s objemom 1000 dm3 (1 m3) a doba presunu bola 70 sekúnd. Je tu možnosť umiestniť zvyšky do inej nádoby s objemom 500 dm3 a časom 130 sekúnd. Otázka: sme pripravení stráviť ďalších 60 sekúnd času skladníka na presun tovaru, aby sme ušetrili 500 dm3 voľného objemu? Na základe výsledkov prieskumu zamestnancov skladu bol zostavený nasledujúci diagram.

Ryža. 5. Diagram závislosti minimálnej prípustnej objemovej úspory od nárastu rozdielu času prevádzky

To znamená, že ak sú dodatočné časové náklady 40 sekúnd, potom sme pripravení ich minúť až vtedy, keď objemový prírastok bude aspoň 500 dm3. Napriek tomu, že v závislosti je mierna nelinearita, pre jednoduchosť ďalších výpočtov budeme predpokladať, že závislosť medzi veličinami je lineárna a je opísaná nerovnicou

Na obrázku nižšie uvažujeme o nasledujúcich spôsoboch umiestňovania tovaru do kontajnerov.

Ryža. 6. Možnosť (a): 2 nádoby, celkový objem 400 dm3, celkový čas 150 sek.

Ryža. 6. Možnosť (b): 2 nádoby, celkový objem 600 dm3, celkový čas 190 sek.

Ryža. 6. Možnosť (c): 1 nádoba, celkový objem 400 dm3, celkový čas 200 sek.

Možnosť (a) na výber kontajnerov je výhodnejšia ako pôvodná možnosť, pretože nerovnosť platí: (800-400)/10>=150-120, čo znamená 40 >= 30. Možnosť (b) je menej výhodná ako pôvodná možnosť možnosť , keďže nerovnosť neplatí: (800-600)/10>=190-150, čo znamená 20 >= 40. Ale možnosť (c) do takejto logiky nezapadá! Zvážme túto možnosť podrobnejšie. Na jednej strane nerovnosť (800-400)/10>=200-120, čo znamená, že nerovnosť 40 >= 80 neplatí, čo naznačuje, že nárast objemu nestojí za takú veľkú stratu v čase.

Ale na druhej strane v tejto možnosti (c) nielenže znížime celkový obsadený objem, ale znížime aj počet obsadených buniek, čo je prvá z dvoch dôležitých požiadaviek na vyčísliteľné riešenia vyššie uvedených problémov. Je zrejmé, že na to, aby sa táto požiadavka začala plniť, je potrebné pridať nejakú kladnú konštantu na ľavú stranu nerovnosti , a takúto konštantu je potrebné doplniť až vtedy, keď sa zníži počet nádob. Pripomeňme si to je premenná rovná 1, keď kontajner vybraté a 0 pri kontajneri nevybrané. Označme – veľa kontajnerov v počiatočnom riešení a – veľa kontajnerov v novom riešení. Vo všeobecnosti bude nová nerovnosť vyzerať takto:

Transformáciou vyššie uvedenej nerovnosti dostaneme

Na základe toho máme vzorec na výpočet celkových nákladov nejaké riešenie problému:

Teraz však vyvstáva otázka: akú hodnotu by mala mať taká konštanta? ? Je zrejmé, že jeho hodnota musí byť dostatočne veľká, aby bola vždy splnená prvá požiadavka na riešenie problému. Môžete samozrejme vziať hodnotu konštanty rovnú 103 alebo 106, ale rád by som sa vyhol takýmto „magickým číslam“. Ak zvážime špecifiká vykonávania skladových operácií, vieme vypočítať niekoľko fundovaných číselných odhadov hodnoty takejto konštanty.

Nechať – maximálna vzdialenosť medzi skladovými bunkami jednej zóny ABC, v našom prípade rovná 100 m Let – maximálny objem kontajnerovej bunky v sklade, v našom prípade rovný 1000 dm3.

Prvý spôsob výpočtu hodnoty . Zoberme si situáciu, keď sú na prvom poschodí 2 kontajnery, v ktorých sa tovar už fyzicky nachádza, to znamená, že samy sú darcovskými bunkami a náklady na presun tovaru do rovnakých buniek sú prirodzene rovné 0. je potrebné nájsť takú hodnotu pre konštantu , v ktorom by bolo výhodné vždy presúvať zvyšky z kontajnera 1 do kontajnera 2. Nahradenie hodnôt и Vo vyššie uvedenej nerovnosti dostaneme:

z ktorej vyplýva

Nahradením hodnôt priemerného času na vykonávanie základných operácií do vyššie uvedeného vzorca dostaneme

Druhý spôsob výpočtu hodnoty . Uvažujme o situácii, v ktorej existuje darcovské bunky, z ktorých sa plánuje presun tovaru do kontajnera 1. Označme – vzdialenosť od darcovskej bunky do kontajnera 1. K dispozícii je tiež kontajner 2, ktorý už obsahuje tovar a ktorého objem umožňuje umiestniť zvyšok všetkých bunky. Pre jednoduchosť budeme predpokladať, že objem tovaru presunutého z darcovských buniek do kontajnerov je rovnaký a rovný . Je potrebné nájsť takúto hodnotu konštanty , v ktorom je uloženie všetkých zvyškov z bunky do kontajnera 2 by bolo vždy ziskovejšie ako ich umiestnenie do rôznych kontajnerov:

Transformujeme nerovnosť, ktorú dostaneme

S cieľom „posilniť“ hodnotu množstva , predpokladajme, že = 0. Priemerný počet buniek, ktoré sa zvyčajne zúčastňujú na postupe kompresie zostatkov skladu, je 10. Nahradením známych hodnôt množstiev získame nasledujúcu hodnotu konštanty

Berieme najväčšiu hodnotu vypočítanú pre každú možnosť, toto bude hodnota množstva pre dané parametre skladu. Teraz si pre úplnosť napíšme vzorec na výpočet celkových nákladov na nejaké realizovateľné riešenie :

Teraz predsa titánske úsilie Transformáciou vstupných dát môžeme povedať, že všetky vstupné dáta boli prevedené do požadovanej podoby a sú pripravené na použitie v optimalizačnom algoritme.

Záver

Ako ukazuje prax, zložitosť a dôležitosť fázy prípravy a transformácie vstupných údajov pre algoritmus sa často podceňuje. V tomto článku sme práve tejto fáze venovali veľkú pozornosť, aby sme ukázali, že iba kvalitné a inteligentne pripravené vstupné dáta môžu urobiť rozhodnutia vypočítané algoritmom skutočne hodnotné pre klienta. Áno, odvodení vzorcov bolo veľa, ale varovali sme vás ešte pred kata :)

V ďalšom článku sa konečne dostaneme k tomu, na čo boli určené 2 predchádzajúce publikácie - diskrétny optimalizačný algoritmus.

Pripravil článok
Roman Shangin, programátor projektového oddelenia,
Spoločnosť First Bit, Čeľabinsk

Zdroj: hab.com