Diskreetne matemaatika WMS-i jaoks: kaupade pakkimise algoritm rakkudesse (osa 1)

Artiklis räägime, kuidas lahendasime ladude vaba ruumi puudumise probleemi ning ka diskreetse optimeerimise algoritmi väljatöötamisest sellise ülesande lahendamiseks. Jagame, kuidas me «ehitasime» optimeerimise probleemi matemaatilist mudelit ja milliste raskustega me üllatuslikult silmitsi seisisime algoritmi sisendandmete töötlemisel.

Kui teid huvitavad matemaatika rakendused äris ja te ei karda karmide identiteetsete valemite ümberkujundamisi 5. klassi tasemel, olete teretulnud allapoole!

Artikkel on kasulik neile, kes juurutavad WMS-süsteeme, töötavad ladude või tootmislogistika valdkonnas, samuti programmeerijatele, kes on huvitatud matemaatika rakendustest äris ja protsesside optimeerimisest ettevõttes.

Sissejuhatav osa

See publikatsioon jätkab artiklite seeriat, kus jagame oma eduka kogemuse optimeerimisalgoritmide rakendamisel ladude protsessides.

Uues eelnevas artiklis kirjeldatakse ladude spetsiifikat, kus juurutati WMS-süsteem, ning räägitakse, miks oli meil vaja lahendada kaupadest jäänuste partii klasterdamise probleem WMS-süsteemi rakendamisel ning kuidas me seda tegime.

Kui olime lõpetanud artikli kirjutamise optimeerimisalgoritmidest, oli see väga mahukas, seetõttu otsustasime kogutud materjali jagada kaheks osaks:

• Esimeses osas (see artikkel) räägime, kuidas me «ehitasime» optimeerimise probleemi matemaatilist mudelit ja milliste suurte raskustega me üllatuslikult silmitsi seisisime sisendandmete töötlemisel ja ümberkujundamisel algoritmi jaoks.
• Teises osas vaatleme üksikasjalikult algoritmi rakendamist keeles C++, viime läbi arvutuskatsed ja teeme kokkuvõtte kogemustest, mida saime selliste «intelligentsete tehnoloogiate» juurutamisel kliendi äriprotsessides.

Kuidas artiklit lugeda. Kui olete eelmist artiklit lugenud, võite minna otse jaotisse «Olemasolevate lahenduste ülevaade», kui ei, siis lahendatava probleemi kirjeldus on spoileris allpool.

Lahendatava probleemi kirjeldus kliendi laos

Protsesside kitsaskohad

2018. aastal teostasime projekti juurutamise WMS-laodimissüsteemid «Tegemist on kaubamajaga «LD» Chelyabinskis. Rakendasime toote «1C-Logistika: Laohalduse 3» 20 töökohta: operaatorid, laotöötajad, tõstukijuhid. WMSLao pindala on keskmiselt umbes 4000 m2, kus on 5000 raku ja 4500 SKU. Laos hoitakse erinevate suurustega kuulkraane, mis on toodetud iseseisvalt, kaaluvahemikus 1 kg kuni 400 kg. Lao varud hoitakse partii lõikes, kuna on vajadus toote valimiseks FIFO alusel.

Lao automatiseerimise skeemide projekteerimise käigus seisime silmitsi olemasoleva probleemiga, nimelt varude ebapiisava ladustamisega. Kraanide ladustamise ja paigutamise eripära on selline, et ühes loodud ladustamise rakus võib olla ainult ühe partii kaubad (vt joonis 1). Tooted saabuvad lattu iga päev ja iga saabumine on eraldi partiina. Ühes kuus, tööprotsessi käigus, luuakse kokku 30 eraldi partiid, mistõttu peab iga toode olema eraldi rakus. Kaupa sageli ei valita kogu paberi pealt, vaid tükkidena, tulemuseks on see, et tükkide valiku alal on paljudes rakudes järgnev pilt: üle 1m3 mahutavusega rakus on mitu kraani, mis moodustavad alla 5-10% rakust.

Joonis 1. Foto mitmest tükkist rakus

Silmanähtav ebapiisav ladustamise kasutamine. Probleemi mastaapi näitavad numbrid: keskmiselt on selliseid rakke, mille maht ületab 1m3 ja kus on "minimaalsed" jäägid, laos 100 kuni 300 rakkude vahel erinevatel perioodidel. Kuna lao pindala on suhteliselt väike, siis lao koormusperioodidel muutub see tegur „kitsaskohaks“, mis tõsiselt aeglustab vastuvõtu ja väljavõtu protsesse.

Probleemi lahendamise idee

Küsimus tekkis: lähimad jäägirühmad tõmmata ühte ainus partii ja sellised jäägid, millel on ühtne partii, paigutada kompaktselt koos ühte rakku või mitmesse, kui ruumi ei piisa kõikide jääkide mahutamiseks. Taolise „kokku tõmbamise“ näide on kujutatud joonisel 2.

Joonis 2. Jäägide kokkuvõtmise skeem rakus

See võimaldab oluliselt vähendada ladustamisruume, mida kasutatakse uue kauba jaoks. Kui laopinda on ülekoormatud, on selline meede äärmiselt vajalik, vastasel juhul ei pruugi uue kauba paigutamiseks piisavalt ruumi jääda, mis toob kaasa laoprotsesside peatamise ja seetõttu ka vastuvõtu ning saatmise piiratuse. Enne WMS-süsteemi rakendamist tehti see operatsioon käsitsi, mis oli ebaefektiivne, kuna sobivate jääkide leidmine rakkudest oli aeganõudev. Nüüd, WMS-süsteemi rakendamisega, on protsess automatiseeritud, kiirendatud ja muudetud nutikamaks.

Sellise ülesande lahendamise protsess jaguneb kaheks etapiks:

• esimeses etapis otsime kuupäevade poolest lähedasi partiigruppe tihendamiseks (see ülesanne on pühendatud) eelmine artikkel);
• teises etapis arvutame iga partiigrupi jaoks kauba jääkide võimalikult kompaktse paigutuse rakkudes.

Käesolevas artiklis käsitleme algoritmi teist etappi.

Eksisteerivate lahenduste ülevaade

Enne kui liigelda meie välja töötatud algoritmide kirjeldamise juurde, tasub teha lühike ülevaade turul juba olemasolevatest süsteemidest WMS, kus on rakendatud sarnast optimaalse tihendamise funktsionaalsust.

Esiteks tuleb märkida toode '1C: Ettevõte 8. WMS Logistika. Laohalduse 4', mis kuulub ja mida levitab firma 1C ning kuulub neljanda põlvkonna -süsteemide hulka, mille on välja töötanud ettevõte AXELOT. Antud süsteemis on välja reklaamitud tihendamise funktsionaalsus, mis on mõeldud kaupa erinevate jääkide ühendamiseks ühte ühisesse rakku. Tuleb märgata, et sellise süsteemi tihendamise funktsionaalsus hõlmab ka teisi võimalusi, näiteks kaupade paigutuse parandamist rakkudes vastavalt nende ABC klassidele, kuid sellele me ei peatuma. WMS-süsteemide, mille on välja töötanud AXELOT. Antud süsteemis on väljendatud kokkusurumise funktsionaalsust, mis on mõeldud kaupadest eraldi jääkide ühendamiseks ühte ühisesse lahtrisse. Tuleb märkida, et kokkusurumise funktsionaalne ülesanne hõlmab ka muid võimalusi, näiteks kaupade paigutuse parandamine lahtrites vastavalt nende ABC klassidele, kuid me ei peatugi neil.

Kui analüüsida süsteemi „1C: ettevõte 8. WMS logistika. Laohaldus 4“ koodi (mis on antud funktsionaalsuse osas avatud), saab järeldada järgmist. Jääkide kokkusurumise algoritm rakendab üsna primitiivset lineaarselt loogikat ning ei saa rääkida mingist „optimaalsest“ kokkusurumisest. Loomulikult ei hõlma see ka partiide klastri loomist. Mitmed kliendid, kellele selline süsteem on juurutatud, on kaebanud kokkusurumise planeerimise tulemuste üle. Näiteks juhtub sageli praktikas, et jääke 100 tk ühest rakust plaanitakse transportida teise rakku, kus on 1 tk kaupa, kuigi ajakulu optimaalsuse seisukohalt oleks vastupidi parem.

Samuti on kauba jääkide kokkusurumise funktsioon välja kuulutatud paljudes välismaal, WMS-süsteemides, kuid kahjuks ei ole meil ei tegelikke ülevaateid algoritmide töö efektiivsuse kohta (see on kommertsalane), ega ka arusaamu nende loogika sügavusest (proprietaarne tarkvara suletud koodiga), seega ei saa me hinnata.

Matemaatilise mudeli leidmine ülesande jaoks

Kvaliteetsete algoritmide projekteerimiseks ülesande lahendamiseks on kõigepealt vajalik see ülesanne selgelt matemaatiliselt formuleerida, mida me ka teeme.

On olemas palju rakke , kus asuvad mõne kauba jäägid. Edasi nimetame selliseid rakke doonorirakkudeks. Määratleme kauba mahu, mis asub rakus $.

Oluline on öelda, et kokkusurumise protseduuris võib osaleda ainult ühe partii kaup, või mitme partii kaup, mis on eelnevalt koondatud klastrisse (loe eelmist artiklit), mis on tingitud kaupade säilitamise ja paigutamise eripärast. Erinevate kaupade või erinevate partii klastrite puhul peaks käivituma oma eraldi kokkusurumise protseduur.

On olemas palju rakke , kuhu saavad potentsiaalselt paigutada doonorirakkudest jäägid. Selliseid rakke nimetame edaspidi konteinerirakkudeks. Need võivad olla nii vabade rakud laos kui ka doonorirakud mitmetest . Alati on hulk alamhulk .

Iga raku hulgas on määratletud mahupiirangud , mõõdetud dm3-des. Üks dm3 on kuubik, mille küljed on 10 cm. Ladustatavad tooted on piisavalt suured, seega selline diskreetimine on täiesti piisav.

On määratud lühimade kauguste maatriks meetrites iga kahe rakku paari vahel , kus ja kuuluvad hulkadesse ja vastavalt.

Tähistame «kulud» kaupade liigutamiseks rakust rakku . Tähistame «kulud» konteineri valimiseks kaupade üleveoks teistest rakkudest. Kuidas ja millistes mõõtühikutes väärtused arvutatakse ja arutame edasi (vt jaotist sisendandmete ettevalmistamine), praegu on piisav öelda, et need suurused on otseselt proportsionaalsed suurustega ja vastavalt.

Tähistame läbi muutuja, mis on 1, kui jäänused rakust liigutatakse konteinerisse , ja 0 vastupidisel juhul. Tähistame läbi muutuja, mis on 1, kui konteiner sisaldab tootejäänuseid, ja 0 vastupidisel juhul.

Ülesanne on nii: on vajalik leida selline konteinerite kogum ja seega „manustada“ donarakkud konteinerirakkudega, et minimeerida funktsiooni

piirangute juures

Kokkuvõttes püüame ülesande lahendamise käigus:

• esiteks, säästa laoruume;
• teiseks, säästa ladude töötajate aega.

Viimane piirang tähendab, et me ei tohi liikuda tooteid konteinerisse, mida me ei ole valinud, samuti ei tohi me „kanda kulusid“ selle valimisele. Samuti tähendab see piirang, et üle kantud kaupade maht rakust konteinerisse ei tohi ületada konteineri mahutavust. Ülesande lahendusena mõistame konteinerite kogumit ja viise donorakkude kinnitamiseks konteineritega.

See optimeerimisülesande vormulatsioon ei ole uus ja on olnud paljude matemaatikute uurimise objekt alates 80ndate aastate algusest. Välistes allikates on kaks optimeerimisülesannet sobiva matemaatilise mudeliga: Single-Source Capacitated Facility Location Problem ja Multi-Source Capacitated Facility Location Problem (räägime edaspidi ülesannete erinevustest). Tuleb öelda, et matemaatilises teaduskirjanduses sõnastatakse kahe optimeerimise ülesande probleeme ettevõtete asukoha kontekstis, kust ka nimi „Facility Location”. Suur osa sellest on traditsioon, kuna esmakordselt tulenes vajadus selliste kombinatoorsete probleemide lahendamiseks logistikavaldkonnast, suurel määral sõjaväe- ja tööstusharust 20. sajandi 50. aastatel. Ettevõtete asukoha terminite kohaselt sõnastatakse sellised probleemid järgmiselt:

• On lõplik hulk linnu, kus on potentsiaalselt võimalik rajada tootmisettevõtteid (edaspidi linnad-tootjad). Iga linn-tootja jaoks on määratud kulud ettevõtte avamiseks ning avatud ettevõtte tootmisvõimsuse piirang.
• On lõplik hulk linnu, kus tegelikult asuvad kliendid (edaspidi linnad-kliendid). Iga sellise linna-kliendi jaoks on määratud toote nõudluse maht. Lihtsuse huvides oletame, et toode, mida ettevõtted toodavad ja kliendid tarbivad, on sama.
• Iga paari linn-tootja ja linn-kliendi jaoks on määratud transpordikulude suurus nõutava toote hulga tarnimiseks tootjalt kliendile.

On vajalik leida, millistes linnades rajada ettevõtted ja kuidas klientide sidumine nende ettevõtetega toimub, et:

• Ettevõtete avamise ja transpordikulude kogusumma oleks minimaalne;
• Kliendilt, kes on seotud mõne avatud ettevõttega, nõutav nõudlus ei ületaks selle ettevõtte tootmisvõimsust.

Nüüd tuleks rääkida ainukesest erinevusest nende kahe klassikalise probleemi vahel:

• Single-Source Capacitated Facility Location Problem – klient saab varustust ainult ühest avatud ettevõttest;
• Multi-Source Capacitated Facility Location Problem – klient võib varustust saada mitmest avatud ettevõttest samaaegselt.

See erinevus kahe probleemi vahel paistab esmapilgul vähetähtis, kuid tegelikult toob see kaasa täiesti erineva probleemide kombinatoorse struktuuri ja seega ka täiesti erinevad lahenduse algoritmid. Probleemide erinevust näidatakse alloleval joonisel.

Joon.3. a) Multi-Source Capacitated Facility Location Problem

Joon.3. b) Single-Source Capacitated Facility Location Problem

Mõlemad ülesanded -raskus, see tähendab, et ei ole olemas täpset algoritmi, mis suudaks sellise ülesande polünoomse aja jooksul sisendi suuruse suhtes lahendada. Lihtsamalt öeldes, kõik täpsed algoritmid selle ülesande lahendamiseks töötavad eksponentsiaalses ajas, kuigi tõenäoliselt kiiremini kui täielik läbiproovimine. Kuna ülesanne -on keerukas, siis vaatleme ainult ligikaudseid heuristikaid, see tähendab algoritme, mis arvutavad pidevalt lahendusi, mis on väga lähedased optimaalsele ning töötavad piisavalt kiiresti. Kui selliste ülesannete vastu on huvi, siis siit leiate hea ülevaate Vene keeles.

Kui vaadata meie ülesande terminoloogiat, mis seisneb kaupade optimaalses pakkimises rakkudesse, siis:

• linnad-kliendid – need on doonor-rakud kaubajääkidega,
• linnad-tootjad – need on konteiner-rakud , kuhu plaanitakse paigutada jäänused teistest rakkudest,
• transportimiskulud – aja kulud ladustaja jaoks kauba mahu liigutamiseks doonor-rakust konteiner-rakku ;
• ettevõtte avamise kulud – konteineri valiku kulud , mis on võrdsed konteiner-raku mahuga , korrutatuna teatud vabade mahudega kokkuhoiu koefitsiendiga (koefitsiendi väärtus on alati > 1) (vt jaotis sisendandmete ettevalmistamine).

Pärast seda, kui analoogia tuntud klassikaliste tarnete ülesande kohta on tehtud, on oluline vastata küsimusele, mis mõjutab algoritmi lahenduse arhitektuuri valikut: kas jäänuste liigutamine doonor-rakust on võimalik ainult ühte konteinerisse (Single-Source) või on jäänuste paigutamine mitmesse konteiner-rakku (Multi-Source) võimalik?

Tasub märkida, et praktikas on mõlemat ülesande seadet vaja. Tõime välja iga sellise seadistuse plussid ja miinused allpool:

Tabel 1. Single-Source ja Multi-Source variantide plussid ja miinused.

Arvestades, et Single-Source variandi plusside arv on suurem ning kuna, mida vähem on jääke annetavates rakkudes, seda väiksem on erinevus tihenduse kompaktsete tasemete osas, mis on arvutatud mõlema ülesande variandi järgi, valisime Single-Source variandi.

Oluline on märkida, et Multi-Source variandi lahendamine on samuti võimalik. On palju tõhusaid algoritme selle lahendamiseks, millest enamik on suunatud ridade transportimise probleemide lahendamisele. Samuti on olemas mitte ainult tõhusad, vaid ka elegantsemad algoritmid, näiteks. siit.

Sisendandmete ettevalmistamine

Enne kui hakkame analüüsima ja arendama algoritmi ülesande lahendamiseks, tuleb otsustada, milliseid andmeid ja millises vormis me talle sisendina esitame. Kaupade jääkide maht annetavates rakkudes ja konteinerirakkude mahutavus ei põhjusta probleeme, kuna see on triviaalne – need väärtused mõõdetakse m3, kuid konteinerirakku kasutamise kulude ja liikumise kulude maatriksiga ei ole asi nii lihtne!

Alustame arvutamise ülevaatamist kaubakulu doonorist konteinerisse. Esiteks tuleb kindlaks teha, millistes mõõtühikutes me kaubakulu arvutame. Kaks kõige ilmsemat võimalust on meetrid ja sekundid. 'Puhtates' meetrites kaubakulu arvutamine ei ole mõttekas. Illustreerime seda näitega. Oletame, et räsi asub esimesel tasandil, räsi on eemaldatud 30 meetrit ja paikneb teisel tasandil:

• Liikumine ja on kulukam kui liikumine ja , kuna teiselt tasandilt (1,5-2 meetrit põrandast) on kergem alla lasta kui üles tõsta, kuigi distants on sama;
• 1 tk kaupa niisugusest räsi ja on kergem transportida kui 10 tk sama toodet, kuigi distants on sama.

Kaubakulusid on parem arvestada sekundites, kuna see arvestab nii tasemete erinevust kui ka transporditava kauba koguse variatsiooni. Kaubakulu arvestamiseks sekundites peame liikumisoperatsiooni jaotama elementaarseteks osadeks ja mõõtma igale elementaarsele osale kuluvat aega.

Oletame, et räsi liigub tk kaupa konteinerisse . Oletame, et on keskmine töötaja liikumiskiirus laos, mõõdetuna m/s. Oletame, et ja on keskmised korduvate operatsioonide täitmise kiirus, võtta ja panna, vastavalt kauba mahu kohta, mis on 4 dм3 (keskmine maht, mille töötaja laos korraga tehingute täitmisel võtab). Oletame, et ja on rackide kõrgus, millelt tehingud toimub. Näiteks, esimese tasandi (põrand) keskmine kõrgus on 1 m, teise tasandi on 2 m jne. Formula, mille alusel arvestame operatsiooni teostamise kogu aega on järgmine:

Tabelis 2 on esitatud iga elementaarse operatsiooni teostamise aega statistika, mille töötajad on laos kogunud, arvestades hoitava kauba spetsiifikat.

Operatsiooni nimetus	Märgistus	Keskmine väärtus
Keskmine töötaja liikumiskiirus laos		1,5 m/s
Keskmine kiirus ühe operatsiooni täitmisel, panna (kauba maht 4 dм3)		2,4 sek

Tabel 2. Keskmine aeg lao operatsioonide täitmise jaoks

Oleme määratlenud kaubakulu arvutamise meetodi. Nüüd on vajalik välja selgitada, kuidas arvutada kulusid konteineri valimiseksSiin on kõik oluliselt keerulisem kui kauba transportimise kuludega, kuna:

• Esiteks peavad kulud olema otseses sõltuvuses rakkude mahust – sama maht jääkidest, mis liigutatakse doonorrakkudest, on parem asetada väiksemasse konteinerisse kui suurde konteinerisse, tingimusel et see maht mahub täielikult mõlemasse konteinerisse. Nii, üldisi konteinerite valiku kulusid minimeerides püüdleme me „puuduvate“ vaba laopinda säästmise suunas valiku tsoonis, et teha järgmist kauba paigutamise operatsiooni rakkudesse. Joonisel 4 on näidatud jääkide liigutamise variante suurde ja väiksesse konteinerisse ning nende variantide tagajärjed järgnevate laoprotsesside teostamisel.
• Teiseks, kuna peame algse ülesande lahenduses minimeerima just üldkulusid, mis on nii transportimise kulude kui ka konteinerite valiku kulude summa, siis tuleb rakkude mahud kuupmeetrites mingil viisil siduda sekunditega, mis ei ole üldse triviaalne.

Joonis 4. Jääkide liigutamise variandid erineva mahuga konteineritesse.

Joonisel 4 on punase värviga kujutatud jääkide mahtu, mis ei mahu enam konteinerisse teises etapis järgnevate kaupade paigutamisest.

Kuna jääkide mahtude sidumine konteinerite valiku kuupmeetritega sekundite prisudega nõuab järgmisi nõudeid arvutatavatele ülesande lahendustele:

• On oluline, et doonorirakust jäägid paigutatakse konteinerirakku igal juhul, kui see vähendab konteinerite üldarvu, kus kaup on.
• Peame hoidma tasakaalu konteinerite mahude ja liikuvuse ajakulude vahel: näiteks, kui uue ülesande lahenduse variant võrreldes eelmise lahenduse variandiga on palju suurem mahult, ent ajakulud on palju väiksemad, siis tuleb valida uus variant.

Alustame viimase nõudega. Selleks, et täpsustada mitmekesist sõna „tasakaal“, viidi läbi laotöötajate küsitlus eesmärgiga selgitada välja järgnev. Olgu meil konteinerirakk mahuga , kuhu on määratud kaupadest jääkide liigutamine doonorrakkudest ja selle liigutamise koguaeg on . Olgu veel mitmeid alternatiivseid võimalusi sama koguse kauba paigutamiseks samadesse donorimahutitesse teistesse konteineritesse, kus igal paigutusel on oma hinnangud. , kus < ja , kus >.

Küsimus on: milline minimaalne kasum mahus on vastuvõetav, kui ajakulu on määratud. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Joon. 5. Diagramm minimaalsete lubatud mahutisäästude sõltuvusest operatsiooni täitmise ajavahe suurenemisest.

See tähendab, et kui täiendavad ajakulud on 40 sekundit, oleme valmis neid kulutama ainult siis, kui mahtude kasu on vähemalt 500 dm3. Vaatamata sellele, et sõltuvuses on väike mitte-lineaarsus, eeldame edasiste arvutuste lihtsuse huvides, et sõltuvus nende suuruste vahel on lineaarne ja seda kirjeldab ebaühtlus.

Alljärgneval joonisel vaatleme järgmisi kauba paigutamise viise konteineritesse.

Joon. 6. Variant (a): 2 konteinerit, kogumaht 400 dm3, koguaeg 150 sek.

Joon. 6. Variant (b): 2 konteinerit, kogumaht 600 dm3, koguaeg 190 sek.

Joon. 6. Variant (c): 1 konteiner, kogumaht 400 dm3, koguaeg 200 sek.

Variant (a) konteinerite valik on eelistatum kui algne variant, kuna täidetakse ebaühtlus: (800-400)/10>=150-120, millest järeldub 40 >= 30. Variant (b) on vähem eelistatud kui algne variant, kuna ebaühtlus ei kehti: (800-600)/10>=190-150, millest järeldub 20 >= 40. Kuid variant (c) ei järgita sarnast loogikat! Vaatame seda varianti lähemalt. Ühelt poolt kehtib ebaühtlus (800-400)/10>=200-120, seega ebaühtlus 40 >= 80 ei kehti, mis näitab, et mahukasum ei ole sellise suures ajakaotusest väärt.

Kuid teisalt, sellises variante (c) ei ole me mitte ainult vähendamas hõivatud mahtu, vaid ka vähendamas hõivatud riiulite arvu, mis on esimene kahest olulisest nõudest lahenduste arvutamiseks, nagu eespool loetletud. On ilmne, et selle nõude täitmiseks tuleb ebaühtluse vasakule poole lisada mõni positiivne konstant. , samas tuleb seda konstantti lisada ainult siis, kui konteinerite arv väheneb. Meenutame, et on muutuja, mis on võrdne 1, kui konteiner on valitud, ja 0, kui konteiner valitud ei ole. Määratleme, – palju konteinerite originaalses lahenduses ja – palju konteinerite uues lahenduses. Üldises vormis näeb uus ebavõrdsus välja järgmiselt:

Töötledes eelnevat ebavõrdsust, saame

Selgitades, jõuame valemini üldkulude arvutamiseks mõne lahenduse variandi jaoks:

Kuid nüüd tõstatub küsimus: kui suureks peaks see konstant olema ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Olgu – maksimaalne kaugus ladustamisvõime ühe tsooni ABC vahel, mis meie puhul on 100 m. Olgu – maksimaalne konteineri-mahus olev lao mahutavus, mis meie puhul on 1000 dm3.

Esimene meetod suuruse arvutamiseks . Vaatleme olukorda, kus esimesel tasemel on 2 konteinerit, milles on füüsiliselt kaup, see tähendab, et nad on ise donor-rakkudena, ning kauba liikumise kulud nende rakkudesse on loomulikult 0. Peame leidma sellise konstantse väärtuse , mille puhul oleks alati kasulik jääkide liigutamine konteinerist 1 konteinerisse 2. Asendades väärtused ja eelnevalt toodud ebavõrdsusse, saame:

mille põhjal järeldub

Asendades elementaarsete toimingute keskmised teostamisajad ülaltoodud valemisse, saame

Teine meetod suuruse arvutamiseks . Vaatleme olukorda, kus on donor-rakke, millest plaanitakse kauba liikumist konteinerisse 1. Määratleme – kaugus donor-rakust konteinerisse 1. Samuti on olemas konteiner 2, milles on juba kaupu, ja mille maht võimaldab mahutada jääke kõigist donor-rakkudest. Lihtsuse huvides eeldame, et rakkudest konteinerisse liigutatav kauba maht on sama ja võrdub . Peame leidma sellise konstantse väärtuse , mille puhul oleks kõikide jääkide paigutamine rakud konteinerisse 2 alati soodsam kui paigutamine erinevatesse konteineritesse:

Töötledes ebavõrdsust saame

Selleks, et suurendada suuruse väärtust , oletame, et = 0. Keskmine rakkude arv, mis tavaliselt osaleb jääkide tihendamise protseduuris, on 10. Asendades teadaolevad suuruste väärtused, saame järgmise konstantse väärtuse

Võtame suurima väärtuse, mis on arvutatud iga variandi põhjal, ja see ongi suuruse väärtus antud lao parameetrite jaoks. Nüüd lõpetuseks kirjutame valemi üldkulude arvutamiseks mõne lubatud lahenduse jaoks :

Nüüd, pärast kõiki titanilisi pingutusi sisendandmete transformeerimiseks, saame öelda, et kõik sisendandmed on muudetud vajalikku vormi ja on valmis kasutamiseks optimeerimisalgoritmis.

Kokkuvõte

Kuidas praktika näitab, et sisendandmete ettevalmistamise ja töötlemise etapi töömaht ja tähtsus algoritmi jaoks on tihti alahinnatud. Selles artiklis oleme sellele etapile eraldanud palju tähelepanu, et näidata, et ainult korralikult ja arvestavalt ettevalmistatud sisendandmed suudavad teha algoritmi arvutatud lahendused tõeliselt väärtuslikeks kliendi jaoks. Jah, oli palju valemi järeldusi, kuid me hoiatame teid juba enne kät 🙂

Järgmises artiklis jõuame lõpuks sellele, milleks kaks eelmist publikatsiooni mõeldud olid – diskreetse optimeerimise algoritmile.

Artikli koostas
Roman Shangin, projektide osakonna programmeerija,
ettevõte Esimene Bit, Čeljabinsk

Allikas: habr.com