Diskret matematik for WMS: algoritme til komprimering af varer i celler (del 1)

I artiklen vil vi fortælle, hvordan vi løste problemet med manglende ledige pladser på lageret og om udviklingen af en algoritme til diskret optimering til at tackle denne udfordring. Vi vil beskrive, hvordan vi 'byggede' den matematiske model for optimeringsopgaven, samt de udfordringer vi uventet stødte på under behandlingen af inddata til algoritmen.

Hvis du er interesseret i matematikens anvendelser i erhvervslivet og ikke er bange for hårde identitetsomformninger af formler på 5. klasse niveau, så er du hjerteligt velkommen til at læse videre!

Artiklen vil være nyttig for dem, der implementerer WMS-systemer, arbejder i sektoren for lager- eller produktionslogistik, samt programmører, der er interesseret i matematikens anvendelser i erhvervslivet og optimering af processer i virksomheden.

Introduktionen

Denne publikation fortsætter en serie artikler, hvor vi deler vores succesfulde erfaring med implementering af optimeringsalgoritmer i lagerprocesser.

I i den foregående artikel detaljerer specifikationen for det lager, hvor vi implementerede WMS-systemet, samt hvorfor vi havde behov for at løse opgaven med klustering af partier af varer ved implementeringen af WMS-systemet, og hvordan vi gjorde det.

Da vi var færdige med at skrive artiklen om optimeringsalgoritmer, blev den meget lang, så vi besluttede at dele det samlede materiale op i 2 dele:

• I den første del (denne artikel) vil vi fortælle om, hvordan vi 'byggede' den matematiske model for opgaven, samt de store udfordringer vi uventet stødte på under behandlingen og omdannelsen af inddata til algoritmen.
• I den anden del vil vi nøje gennemgå implementeringen af algoritmen i sproget C++, udføre et beregningsforsøg og opsummere den erfaring, vi har fået i løbet af implementeringen af sådanne 'intelligente teknologier' i kundens forretningsprocesser.

Hvordan man læser artiklen. Hvis du har læst den foregående artikel, kan du straks gå videre til kapitlet 'Oversigt over eksisterende løsninger', hvis ikke, så er beskrivelsen af det løste problem nedenfor i spoiler.

Beskrivelsen af det løste problem i kundens lager

Flaskehalsen i processerne

I 2018 gennemførte vi et projekt om implementering af WMS-systemet på lageret 'Handelsfirma LD' i Chelyabinsk. Vi implementerede produktet '1C-Logistik: Lagerstyring 3' på 20 arbejdspladser: operatører WMS, plukkere, gaffeltruckchauffører. Lageret er gennemsnitligt cirka 4.000 m2 stort, med 5.000 pladser og 4.500 SKU'er. Lageret opbevarer kuglehaner, som er produceret in-house, i forskellige størrelser fra 1 kg til 400 kg. Lagerbeholdningen lagres efter partier, da der er behov for at plukke varerne efter FIFO.

Under designet af automatiseringsordninger til lagerprocesser stødte vi på et eksisterende problem med suboptimale lagerforhold. Specifikationen for opbevaring og placering af haner er sådan, at der i hver enkelt opbevaringsplads kun kan befinde sig produkter fra én parti (se fig. 1). Produkterne ankommer til lageret dagligt, og hver ankomst er et separat parti. I alt, efter 1 måneds drift, skabes der 30 separate partier, hvor hvert parti skal opbevares i sin egen plads. Varerne plukkes ofte ikke i hele paletter, men stykvis, hvilket resulterer i, at der i plukkezonerne i mange enkeltpladser ses et billede, hvor der i en plads med mere end 1 m3 opbevares flere stykker haner, som kun udnytter 5-10% af pladsens volumen.

Fig. 1. Foto af flere stykker i en plads

Der er et tydeligt suboptimalt udnyttelse af lagerkapaciteten. For at illustrere omfanget af problemet kan jeg nævne nogle tal: I gennemsnit er der i forskellige perioder af lagerdriften mellem 100 og 300 pladser på mere end 1 m3 med "minimal" lagerbeholdning. Da lageret er relativt lille, bliver denne faktor i sæsoner med høj belastning til en "flaskehals", der i høj grad hæmmer lagerprocesserne ved modtagelse og afsendelse.

Ideen til at løse problemet

Der opstod en idé: at samle partier med de nærmeste datoer til én samlet parti og placere sådanne rester med en standardiseret parti kompakt sammen i en eller flere pladser, hvis der ikke er plads nok i én. Et eksempel på en sådan "komprimering" er vist i figur 2.

Fig. 2. Diagram over komprimering af rester i pladser

Dette muliggør en betydelig reduktion af det lagerplads, der vil blive brugt til det nye lagerførte produkt. I tilfælde af overbelastning af lagerkapacitet er denne foranstaltning yderst nødvendig, ellers kan der simpelthen ikke være nok plads til at placere det nye produkt, hvilket vil føre til en stilstand i lagerprocesserne for placering og forsyning, og som følge heraf til stilstand i modtagelse og afsendelse. Før implementeringen af WMS-systemet blev sådan en operation udført manuelt, hvilket var ineffektivt, da processen med at finde de passende lagre i reolerne var ret tidskrævende. Nu, med implementeringen af WMS-systemet, har vi besluttet at automatisere, fremskynde og gøre processen intelligent.

Processen til løsning af en sådan opgave opdeles i 2 faser:

• I den første fase finder vi nærliggende partigrupper for komprimering (denne opgave er dedikeret til den forrige artikel);
• I den anden fase beregner vi for hver partigruppe den mest kompakte placering af varernes rester i reolerne.

I denne artikel vil vi fokusere på den anden fase af algoritmen.

Oversigt over eksisterende løsninger

Før vi går videre til beskrivelsen af de algoritmer, vi har udviklet, er det værd at lave en kort oversigt over de allerede eksisterende systemer på markedet WMS, som implementerer en lignende funktionalitet til optimal komprimering.

Først og fremmest må vi nævne produktet "1C: Virksomhed 8. WMS Logistik. Lagerstyring 4", som tilhører og distribueres af firmaet 1C og hører til fjerde generation WMS-systemer, udviklet af virksomheden AXELOT. I dette system er der angivet kompressionsfunktionalitet, der har til formål at samle spredte varers rester i en fælles reol. Det er vigtigt at bemærke, at kompressionsfunktionaliteten i et sådant system også inkluderer andre muligheder, for eksempel korrektion af varernes placering i reolerne i henhold til deres ABC-klasser, men vi vil ikke dykke nærmere ned i dem.

Hvis man analyserer koden for systemet «1C: Enterprise 8. WMS Logistik. Lagerstyring 4» (som i denne del af funktionaliteten er åben), kan man konkludere følgende. Algoritmen til komprimering af restlagre implementerer en temmelig simpel linear logik, og der kan ikke tale om nogen «optimal» komprimering. Naturligvis indgår klyngedannelse af partier ikke. Flere kunder, som har fået implementeret et sådant system, har klaget over resultaterne af komprimeringsplanlægningen. For eksempel opstod der ofte i praksis følgende situation ved komprimering: 100 stk. restlagre fra en celle planlægges flyttet til en anden celle, hvor der ligger 1 stk. vare, selvom det ville være optimalt set fra tidsforbrug at gøre det modsatte.

Funktionaliteten til komprimering af restlagre i celler er også annonceret i mange udenlandske WMS-systemer, men desværre har vi hverken reelle anmeldelser af effektiviteten af algoritmerne (dette er en handelshemmelighed) eller noget større indblik i dybden af deres logik (proprietær software med lukket kode), så vi kan ikke dømme.

Søgning efter en matematisk model af opgaven

For at designe kvalitetsalgoritmer til at løse opgaven er det nødvendigt først klart at formulere denne opgave matematisk, hvilket vi vil gøre.

Der er mange celler , hvor restlagre af en bestemt vare befinder sig. Disse celler vil vi kalde donor-celler. Lad os betegne volumenet af varen, der befinder sig i cellen $.

Det er vigtigt at sige, at der kun kan deltage én vare fra en part, eller fra flere partier, der tidligere er samlet i en klynge (læs den forrige artikel), hvilket skyldes specifikationen ved opbevaring og placering af varer. For forskellige varer eller forskellige klynger af partier skal der startes en særskilt komprimeringsprocedure.

Der er mange celler , hvori restlagre fra donor-celler potentielt kan placeres. Disse celler vil vi fremover kalde container-celler. Det kan både være ledige celler på lageret samt donor-celler fra mange . Altid er mængden et underområde af .

For hver celle fra mængden er der angivet begrænsninger for kapacitet , målt i dm3. Én dm3 svarer til en terning med sider på 10 cm. Produkterne, der opbevares på lageret, er ret store, så i dette tilfælde er en sådan diskretisering helt tilstrækkelig.

En matrix af korteste afstande er angivet i meter mellem hvert par af lagerrum , hvor og tilhører mængderne og henholdsvis.

Lad os betegne «omkostningerne» ved at flytte varer fra et lagerrum til et andet lagerrum . Lad os betegne «omkostningerne» ved at vælge en container til at flytte rester fra andre lagerrum. Hvordan og i hvilke måleenheder værdierne beregnes og vil blive beskrevet senere (se afsnit om forberedelse af inputdata), for nu er det tilstrækkeligt at sige, at sådanne størrelser vil være direkte proportional med værdierne og henholdsvis.

Lad os betegne med en variabel, der tager værdien 1, hvis rester fra lagerrummet flyttes til containeren , og 0 ellers. Lad os betegne med en variabel, der tager værdien 1, hvis containeren indenholder rester af varer, og 0 ellers.

Opgaven formuleres således: det er nødvendigt at finde en sådan mængde af containere og dermed »tilknytte« donor-lagerrum til container-lagerrum på en måde, der minimerer funktionen

under begrænsninger

I alt i løbet af beregningen af opgavens løsning stræber vi efter:

• for det første at spare lagerkapacitet;
• for det andet at spare tid for lagerarbejdere.

Den sidste begrænsning betyder, at vi ikke kan flytte varer til en container, som vi ikke har valgt, og derfor ikke «har båret omkostningerne» til dens valg. Denne begrænsning betyder også, at volumen af de flyttede varer fra lagerrum til container ikke må overstige containerens kapacitet. En løsning på opgaven vil blive forstået som en mængde containere og måder at tilknytte donor-lagerrum til containerne.

Denne formulering af optimeringsopgaven er ikke ny og er blevet undersøgt af mange matematikere siden begyndelsen af 80'erne i det forrige århundrede. I udenlandsk litteratur findes der 2 optimeringsopgaver med en passende matematisk model: Single-Source Capacitated Facility Location Problem og Multi-Source Capacitated Facility Location Problem (vi forskellige opgaver vil blive diskuteret senere). Det skal nævnes, at i matematisk litteratur bliver formuleringen af disse to optimeringsopgaver beskrevet i termer af placering af virksomheder i geografiske områder, deraf navnet 'Facility Location'. I høj grad er dette en tradition, da behovet for at løse sådanne kombinatoriske opgaver først kom fra logistikområdet, for det meste inden for den militær-industrielle sektor i 1950'erne. I termer af virksomhedens placering formuleres sådanne opgaver således:

• Der er et endeligt antal byer, hvor det potentiel er muligt at placere produktionsanlæg (herefter kaldet virksomhedsbyer). For hver virksomhedsby er der angivet omkostninger ved at åbne en virksomhed der, samt begrænsninger på produktionskapaciteten for den åbne virksomhed.
• Der er et endeligt antal byer, hvor kunderne faktiske befinder sig (herefter kaldet kundebyer). For hver sådan kundeby er der angivet efterspørgselsvolumen på produkter. For enkelhedens skyld antager vi, at det produkt, der produceres af virksomhederne og forbruges af kunderne, er det samme.
• For hvert par af virksomhedsby og kundeby er der angivet transportomkostningerne ved at levere det krævede volumen af produkter fra producenten til kunden.

Det er nødvendigt at finde ud af i hvilke byer man skal åbne virksomheder og hvordan man skal knytte kunderne til disse virksomheder, så:

• De samlede omkostninger ved at åbne virksomhederne og transportomkostningerne er minimale;
• Efterspørgselsvolumenet for kunderne, der er knyttet til et åbent anlæg, overstiger ikke produktionskapaciteten for dette anlæg.

Nu er det værd at nævne den eneste forskel mellem disse to klassiske opgaver:

• Single-Source Capacitated Facility Location Problem – kunden forsynes kun fra et åbent anlæg;
• Multi-Source Capacitated Facility Location Problem – kunden kan forsynes fra flere åbne anlæg samtidig.

Denne forskel mellem de to opgaver virker ved første øjekast ubetydelig, men fører faktisk til en helt anden kombinationsstruktur for sådanne opgaver og, som en konsekvens, til fuldstændig forskellige algoritmer til deres løsning. Forskellen mellem opgaverne er vist på billedet nedenfor.

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

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

Begge opgaver -svære, hvilket vil sige, at der ikke findes en præcis algoritme, der kan løse en sådan opgave på polynomiel tid i forhold til størrelsen af inputdataene. Mere enkelt sagt, vil alle præcise algoritmer til at løse opgaven arbejde med eksponentiel tid, skønt de måske kan være hurtigere end en fuld prøve på alle muligheder. Da opgaven -er svær, vil vi kun overveje tilnærmede heuristikker, det vil sige algoritmer, der vil beregne stabilt løsninger meget tæt på de optimale og vil arbejde hurtigt. Hvis der er interesse for sådanne opgaver, kan man finde en god oversigt på russisk her.

Hvis vi overfører til terminologien fra vores opgave med optimal komprimering af varer i celler, så:

• byer-kunder – er donor-celler med rester af varer,
• byer-producenter – er container-celler , hvor rester fra andre celler forventes placeret,
• transportomkostninger – tidsomkostningerne for lagerarbejderen til at flytte mængden af varer fra donor-cellen til container-cellen ;
• omkostningerne ved at åbne virksomhed – omkostninger ved valg af container , svarende til volumenet af container-cellen , ganget med en eller anden besparelsesfaktor (værdien af faktoren er altid > 1) (se afsnittet forberede inputdata).

Efter at analogien med de kendte klassiske leveringsproblemer er draget, er det nødvendigt at besvare et vigtigt spørgsmål, som afhænger af valget af algoritmearkitektur: er overflytning af rester fra donor-cellen kun muligt til én og kun én container (Single-Source), eller er det muligt at flytte rester til flere container-celler (Multi-Source)?

Det er værd at bemærke, at begge problemstillinger praktisk talt er til stede. Vi vil opremse alle 'for' og 'imod' for hver sådan opstilling nedenfor:

Tabel 1. Fordele og ulemper ved Single-Source og Multi-Source.

Da antallet af fordele ved Single-Source er større, og i betragtning af at jo færre rester der er i donorcellerne, jo mindre er forskellen i komprimeringsgrad mellem de to opgaveløsninger, så faldt vores valg på Single-Source.

Det skal siges, at løsningen af Multi-Source også er relevant. Der findes mange effektive algoritmer til at løse den, hvoraf de fleste reduceres til at løse et antal transportopgaver. Der er også ikke bare effektive algoritmer, men også elegante, for eksempel, her.

Forberedelse af inddata

Før vi begynder at analysere og udvikle algoritmen til at løse opgaven, er det nødvendigt at afgøre, hvilke data og i hvilken form vi vil præsentere dem for den. Med mængderne af varer i donorcellene og kapaciteten af containercellerne er der ingen problemer, da det er trivielt – sådanne størrelser vil blive målt i m3, men med omkostningerne ved at bruge en containercelle og omkostningsmatrixen for flytning er det ikke så enkelt!

Først ser vi på beregningen omkostninger ved flytning af varer fra donorcelle til containercelle. Først og fremmest skal vi beslutte, hvilke måleenheder vi vil bruge til at beregne omkostningerne ved flytningen. De to mest oplagte muligheder er meter og sekunder. Det giver ikke mening at beregne omkostningerne ved flytning i 'rene' meter. Lad os illustrere dette med et eksempel. Antag, at cellen er placeret på første niveau, cellen er 30 meter væk og er placeret på andet niveau:

• Flytning fra i er dyrere end flytning fra i , da det er lettere at nedføre ting fra andet niveau (1,5-2 meter over gulvet) end at løfte dem til andet niveau, selvom afstanden er den samme;
• At flytte 1 stk. vare fra cellen i vil være lettere end at flytte 10 stk. af den samme vare, selvom afstanden er den samme.

Omkostningerne ved flytning bør bedst tælles i sekunder, da det muliggør at tage hensyn til både forskelle i niveauer og forskelle i mængden af flyttede varer. For at kunne tage omkostningerne ved flytning i sekunder, skal vi nedbryde flytteoperationen i dens elementære bestanddele og måle tiden for hver elementær bestanddel.

Lad os sige, at fra cellen bliver flyttet stk. varer til containeren . Lad os antage, at er den gennemsnitlige hastighed, som arbejdere bevæger sig med i lageret, målt i m/s. Lad os antage, at og er de gennemsnitlige hastigheder for engangsoperationerne at tage og lægge henholdsvis for en varevolumen på 4 dm3 (den gennemsnitlige volumen, som en medarbejder tager ad gangen i lageret, når der udføres operationer). Lad os antage, at og er højden på de celler, hvor operationerne at tage og lægge udføres. For eksempel, den gennemsnitlige højde af første niveau (gulv) er 1 m, andet niveau 2 m osv. Således er formlen til beregning af den samlede tid til udførelse af flytteoperationen følgende:

Tabel 2 præsenterer statistikken over tiden for udførelse af hver elementær operation, indsamlet af lagerpersonalet med hensyn til den specifikke opbevaring af varer.

Operationens navn	Betegnelse	Gennemsnitlig værdi
Gennemsnitlig hastighed, som medarbejderen bevæger sig med i lageret		1,5 m/s
Gennemsnitlig hastighed for udførelsen af en operation at lægge (for en varevolumen på 4 dm3)		2,4 sek

Tabel 2. Gennemsnitstiden for udførelse af lageroperationer

Vi har nu fastlagt metoden til beregning af omkostninger ved flytning. Nu skal vi finde ud af, hvordan vi beregner omkostningerne ved valget af containercelleHer er alt meget, meget mere kompliceret end med omkostningerne til flytning, fordi:

• for det første bør omkostningerne være direkte afhængige af volumen af cellen – det samme volumen af rester, der flyttes fra donor-celler, er bedre at placere i en mindre beholder end i en stor beholder, forudsat at dette volumen helt kan rumme i begge beholdere. På denne måde, ved at minimere de samlede omkostninger ved valg af beholdere, søger vi at spare "knappe" ledige lagerkapaciteter i udtagningsområdet for at udføre efterfølgende placeringsoperationer af varer i celler. Figur 4 viser mulighederne for flytning af rester til store og små beholdere og konsekvenserne af sådanne flytninger ved udførelsen af efterfølgende lageroperationer.
• for det andet, da vi i løsningen af den oprindelige opgave skal minimere de samlede omkostninger, hvilket er summen af både omkostninger til flytning og omkostninger til valg af beholdere, så skal volumenerne af celler i kubikmeter på en eller anden måde kobles med sekunder, hvilket ikke er trivielt.

Fig. 4. Muligheder for flytning af rester til beholdere med forskellige kapaciteter.

I Figur 4 er volumen af rester, der allerede ikke kan rumme i beholderen i den anden fase af placeringen af efterfølgende varer, vist i rødt.

Følgende krav til de beregnede løsninger på opgaven hjælper med at koble kubikmeterne af omkostningerne til valg af beholder med sekunderne af omkostningerne til flytning:

• Det er nødvendigt, at resterne fra donor-cellen bliver flyttet til container-cellen under alle omstændigheder, hvis dette reducerer det samlede antal container-celler, hvor varerne befinder sig.
• Der skal være balance mellem beholdere og tidsomkostninger ved flytning: for eksempel, hvis gevinsten i volumen i den nye løsning i forhold til den forrige løsning er stor, og tabet i tidsomkostninger er lille, så er det nødvendigt at vælge den nye løsning.

Lad os begynde med det sidste krav. For at præcisere det flertydige ord "balance" gennemførte vi en undersøgelse blandt lagerpersonalet for at finde ud af følgende. Lad os antage, at der er en container-celle med volumen , hvortil det er planlagt at flytte resterne af varer fra donor-cellerne, og den samlede tid for denne flytning er lig . Lad os antage, at der er flere alternative muligheder for at placere den samme mængde varer fra de samme donor-celler i andre containere, hvor hver placering har sine egne vurderinger. , hvor < og , hvor >.

Spørgsmålet opstår: hvad er den minimale gevinst i volumen, der er acceptabel, givet et bestemt tidsmæssigt tab. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagram over afhængigheden af minimums tilladt besparelse i volumen fra den øgede tidsforskel ved udførelse af operationen.

Det vil sige, hvis de ekstra tidsomkostninger er 40 sekunder, så er vi kun villige til at bruge dem, når gevinsten i volumen er mindst 500 dm3. Selvom der er en lille ikke-linearitet i afhængigheden, antager vi af simplificeringsårsager, at forholdet mellem størrelserne er lineært og beskrives ved uligheden.

I figuren nedenfor vil vi overveje følgende metoder til at placere varer i containere.

Fig. 6. Mulighed (a): 2 containere, samlet volumen 400 dm3, samlet tid 150 sek.

Fig. 6. Mulighed (b): 2 containere, samlet volumen 600 dm3, samlet tid 190 sek.

Fig. 6. Mulighed (c): 1 container, samlet volumen 400 dm3, samlet tid 200 sek.

Valg (a) af containere er mere foretrukket end den oprindelige mulighed, da uligheden opfyldes: (800-400)/10>=150-120 hvilket betyder 40 >= 30. Valg (b) er mindre foretrukket end den oprindelige mulighed, da uligheden ikke opfyldes: (800-600)/10>=190-150 hvilket betyder 20 >= 40. Men mulighed (c) passer ikke ind i denne logik! Lad os overveje denne mulighed mere detaljeret. På den ene side er uligheden (800-400)/10>=200-120, så uligheden 40 >= 80 opfyldes ikke, hvilket indikerer, at gevinsten i volumen ikke retfærdiggør den store tidsmæssige nedgang.

Men på den anden side, i en sådan mulighed (c) reducerer vi ikke blot det samlede optagne volumen, men også antallet af optagne celler, hvilket er det første af de to vigtige krav til de beregnede løsninger til de ovenfor nævnte opgaver. Det er tydeligt, at for at dette krav skal begynde at blive opfyldt, er det nødvendigt at tilføje en positiv konstant til venstre side af uligheden. , desuden skal denne konstant kun tilføjes, når antallet af containere reduceres. Husk, at — er en variabel, der er lig med 1, når containeren er valgt, og 0 når containeren ikke valgt. Lad os definere, – mange containere i den oprindelige løsning og – mange containere i den nye løsning. Generelt vil den nye ulighed se således ud:

Ved at omdanne den ovenstående ulighed får vi

Baseret på dette har vi en formel til beregning af de samlede omkostninger for en given løsning af problemet:

Men nu opstår spørgsmålet: hvilken værdi skal en sådan konstant have ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Lad – den maksimale afstand mellem lagercellerne i én zone ABC, svarende til i vores tilfælde 100 m. Lad – det maksimale volumen af en celle-container på lageret, svarende til i vores tilfælde 1000 dm3.

Den første måde at beregne størrelsen . Lad os overveje situationen, hvor der er 2 containere på den første række, hvor der allerede fysisk er varer, det vil sige, at de selv er donor-celler, og omkostningerne ved at flytte varer til de samme celler er naturligvis lig med 0. Det er nødvendigt at finde en sådan værdi for konstanten , hvor det altid ville være rentabelt at flytte resterne fra container 1 til container 2. Ved at indsætte værdierne og i den ovenstående ulighed får vi:

hvoraf det følger

Ved at indsætte værdierne for den gennemsnitlige tid til udførelse af elementære operationer i formlen ovenfor får vi

Den anden måde at beregne størrelsen . Lad os overveje situationen, hvor der er donor-celler, fra hvilke der planlægges at flytte varer til container 1. Lad os betegne – afstanden fra donor-cellen til container 1. Der er også container 2, hvor der allerede er varer, og som har et volumen, der kan rumme resterne fra alle celler. For enkelhed vil vi antage, at volumen af varerne, der flyttes fra donor-cellerne til containere, er ens og lig med . Det er nødvendigt at finde en sådan værdi for konstanten , hvor det altid ville være mere fordelagtigt at placere alle rester fra celler i container 2 end at placere dem i forskellige containere:

Ved at omdanne uligheden får vi

For at "stærke" værdien af størrelsen , antager vi, at = 0. Det gennemsnitlige antal celler, der normalt deltager i proceduren for komprimering af rester på lageret, er lig med 10. Ved at indsætte de kendte værdier for størrelserne har vi følgende værdi for konstanten

Vi tager den højeste værdi beregnet for hver mulighed, og dette vil være værdien af størrelsen for de givne lagerparametre. Nu for at afslutte, lad os skrive formlen for beregning af de samlede omkostninger for en given tilladelig løsning :

Nu kan vi efter enorme indsatser med at transformere inputdataene sige, at alle inputdata er blevet omformet til den ønskede form og er klar til brug i optimeringsalgoritmen.

Konklusion

Praksis viser, at arbejdsbyrden og betydningen af forberedelse og transformation af inputdata til algoritmen ofte undervurderes. I denne artikel har vi bevidst lagt stor vægt på dette trin for at vise, at kun kvalitets- og klogt forberedte inputdata kan gøre de beslutninger, algoritmen træffer, virkelig værdifulde for kunden. Ja, der har været mange formler, men vi advarede dig om det før katastrofen 🙂

I den næste artikel vil vi endelig komme til det, som de to tidligere publikationer havde til formål – algoritmen for diskret optimering.

Artiklen er forberedt af
Roman Shangin, programmør i projektafdelingen,
firmaet Første Bit, Chelyabinsk

Kilde: habr.com