In dit artikel zullen we u vertellen hoe we het probleem van een gebrek aan vrije cellen in een magazijn hebben opgelost en de ontwikkeling van een discreet optimalisatie-algoritme om een dergelijk probleem op te lossen. Laten we het hebben over hoe we het wiskundige model van het optimalisatieprobleem hebben 'gebouwd', en over de moeilijkheden die we onverwachts tegenkwamen bij het verwerken van invoergegevens voor het algoritme.
Als je geïnteresseerd bent in toepassingen van wiskunde in het bedrijfsleven en niet bang bent voor rigide identiteitstransformaties van formules op het niveau van de 5e klas, dan ben je welkom bij de kat!
Het artikel zal nuttig zijn voor degenen die het implementeren WMS-systemen, werkt in de magazijn- of productielogistieksector, maar ook programmeurs die geïnteresseerd zijn in toepassingen van wiskunde in het bedrijfsleven en de optimalisatie van processen in een onderneming.
Inleidend deel
Deze publicatie vervolgt de reeks artikelen waarin we onze succesvolle ervaring delen met het implementeren van optimalisatie-algoritmen in magazijnprocessen.
В beschrijft de specifieke kenmerken van het magazijn waar we hebben geïmplementeerd WMS-systeem, en legt ook uit waarom we het probleem van het clusteren van partijen resterende goederen tijdens de implementatie moesten oplossen WMS-systemen, en hoe we dat deden.
Toen we klaar waren met het schrijven van het artikel over optimalisatie-algoritmen, bleek het erg groot te zijn, dus besloten we het verzamelde materiaal in twee delen te splitsen:
- In het eerste deel (dit artikel) zullen we praten over hoe we het wiskundige model van het probleem hebben ‘gebouwd’, en over de grote moeilijkheden die we onverwacht tegenkwamen bij het verwerken en transformeren van de invoergegevens voor het algoritme.
- In het tweede deel zullen we in detail de implementatie van het algoritme in de taal bekijken C + +, zullen we een computationeel experiment uitvoeren en de ervaring samenvatten die we hebben opgedaan tijdens de implementatie van dergelijke ‘intelligente technologieën’ in de bedrijfsprocessen van de klant.
Hoe een artikel te lezen. Als je het vorige artikel hebt gelezen, kun je meteen naar het hoofdstuk “Overzicht van bestaande oplossingen” gaan; zo niet, dan staat de beschrijving van het probleem dat wordt opgelost in de spoiler hieronder.
Beschrijving van het probleem dat wordt opgelost in het magazijn van de klant
Knelpunt in processen
In 2018 hebben we een project afgerond dat we moesten implementeren WMS-systemen in het magazijn “Trading House “LD” in Tsjeljabinsk. We hebben het product “1C-Logistics: Warehouse Management 3” geïmplementeerd voor 20 werkplekken: operators WMS, winkeliers, heftruckchauffeurs. Het gemiddelde magazijn is ongeveer 4 m2 groot, het aantal cellen is 5000 en het aantal SKU's is 4500. In het magazijn worden kogelkranen uit eigen productie opgeslagen in verschillende maten van 1 kg tot 400 kg. De voorraad in het magazijn wordt in batches opgeslagen, omdat het nodig is goederen te selecteren op basis van FIFO.
Tijdens het ontwerpen van automatiseringsschema's voor magazijnprocessen werden we geconfronteerd met het bestaande probleem van niet-optimale voorraadopslag. De specifieke kenmerken van opslag- en plaatsingskranen zijn zodanig dat één opslagcel slechts artikelen uit één batch kan bevatten (zie figuur 1). Dagelijks arriveren producten in het magazijn en elke aankomst is een aparte batch. In totaal worden als resultaat van 1 maand magazijngebruik 30 afzonderlijke batches gecreëerd, ondanks het feit dat ze allemaal in een aparte cel moeten worden opgeslagen. Producten worden vaak niet in hele pallets geselecteerd, maar in stukken, en als gevolg daarvan wordt in veel cellen in de stukselectiezone het volgende beeld waargenomen: in een cel met een volume van meer dan 1 m3 staan verschillende stukken kranen die nemen minder dan 5-10% van het celvolume in beslag.
Fig 1. Foto van verschillende stukken in een cel
Het is duidelijk dat de opslagcapaciteit niet optimaal wordt benut. Om me de omvang van de ramp voor te stellen, kan ik cijfers geven: gemiddeld zijn er 1 tot 3 cellen van dergelijke cellen met een volume van meer dan 100 m300 met ‘minuscule’ balansen tijdens verschillende perioden van de werking van het magazijn. Omdat het magazijn relatief klein is, wordt deze factor tijdens de drukke perioden in het magazijn een “knelpunt” en vertraagt dit de magazijnprocessen van acceptatie en verzending aanzienlijk.
Probleem oplossing idee
Er ontstond een idee: batches restjes met de dichtstbijzijnde data zouden moeten worden teruggebracht tot één enkele batch, en dergelijke restjes met een verenigde batch zouden compact samen in één cel moeten worden geplaatst, of in meerdere, als er niet genoeg ruimte in één is om de hele hoeveelheid restjes. Een voorbeeld van een dergelijke “compressie” wordt getoond in Figuur 2.
Fig. 2. Schema voor het comprimeren van residuen in cellen
Hierdoor kunt u de bezette magazijnruimte die wordt gebruikt voor het plaatsen van nieuwe goederen aanzienlijk verminderen. In een situatie waarin de magazijncapaciteit overbelast is, is een dergelijke maatregel uiterst noodzakelijk, omdat er anders eenvoudigweg niet genoeg vrije ruimte is om nieuwe goederen te huisvesten, wat zal leiden tot een stop in de magazijnprocessen van plaatsing en bevoorrading en, als gevolg daarvan, tot stopzetting van acceptatie en verzending. Voorheen, vóór de implementatie van het WMS-systeem, werd een dergelijke handeling handmatig uitgevoerd, wat niet effectief was, omdat het zoeken naar geschikte balansen in cellen vrij lang duurde. Nu we met de introductie van een WMS-systeem hebben besloten om het proces te automatiseren, te versnellen en intelligent te maken.
Het proces om een dergelijk probleem op te lossen is verdeeld in 2 fasen:
- in de eerste fase vinden we groepen batches die qua datum bijna klaar zijn voor compressie (speciaal voor deze taak). );
- in de tweede fase berekenen we voor elke groep batches de meest compacte plaatsing van de resterende goederen in de cellen.
In het huidige artikel zullen we ons concentreren op de tweede fase van het algoritme.
Beoordeling van bestaande oplossingen
Voordat we verder gaan met de beschrijving van de algoritmen die we hebben ontwikkeld, is het de moeite waard een kort overzicht te geven van de systemen die al op de markt bestaan WMS, die vergelijkbare optimale compressiefunctionaliteit implementeren.
Allereerst is het noodzakelijk om het product “1C: Enterprise 8. WMS Logistics. Warehouse management 4", eigendom van en gerepliceerd door 1C en behoort tot de vierde generatie WMS-systemen ontwikkeld door AXELOT. Dit systeem claimt compressiefunctionaliteit, die is ontworpen om ongelijksoortige productresten in één gemeenschappelijke cel te verenigen. Het is de moeite waard te vermelden dat de compressiefunctionaliteit in een dergelijk systeem ook andere mogelijkheden omvat, bijvoorbeeld het corrigeren van de plaatsing van goederen in cellen op basis van hun ABC-klassen, maar we zullen er niet verder op ingaan.
Als je de code van het 1C: Enterprise 8. WMS Logistics-systeem analyseert. Magazijnbeheer 4" (die open is in dit deel van de functionaliteit), kunnen we het volgende concluderen. Het residuele compressie-algoritme implementeert een nogal primitieve lineaire logica en er kan geen sprake zijn van enige “optimale” compressie. Het voorziet uiteraard niet in clustering van partijen. Verschillende klanten die een dergelijk systeem lieten implementeren, klaagden over de resultaten van de compressieplanning. In de praktijk deed zich bijvoorbeeld tijdens het comprimeren vaak de volgende situatie voor: 100 stuks. Het is de bedoeling om de resterende goederen van de ene cel naar de andere cel te verplaatsen, waar 1 stuk zich bevindt. goederen, hoewel het vanuit het oogpunt van tijdsbesteding optimaal is om het tegenovergestelde te doen.
Ook wordt de functionaliteit van het comprimeren van de resterende goederen in cellen in veel landen aangegeven. WMS-systemen, maar helaas hebben we geen echte feedback over de effectiviteit van de algoritmen (dit is een bedrijfsgeheim), laat staan een idee over de diepgang van hun logica (eigen closed-source software), dus we kunnen er niet over oordelen.
Zoek naar een wiskundig model van het probleem
Om algoritmen van hoge kwaliteit te ontwerpen voor het oplossen van een probleem, is het eerst nodig om dit probleem wiskundig helder te formuleren, en dat is wat we zullen doen.
Er zijn veel cellen , die de overblijfselen van enkele goederen bevatten. In wat volgt zullen we dergelijke cellen donorcellen noemen. Laten we aanduiden hoeveelheid goederen in de cel $.
Het is belangrijk om te zeggen dat slechts één product van één batch, of meerdere batches die eerder tot een cluster zijn gecombineerd (lees: ), wat te wijten is aan de specifieke kenmerken van opslag en opslag van goederen. Verschillende producten of verschillende batchclusters moeten hun eigen afzonderlijke compressieprocedure uitvoeren.
Er zijn veel cellen , waarin mogelijk resten van donorcellen kunnen worden geplaatst. Dergelijke cellen zullen we verder containercellen noemen. Dit kunnen vrije cellen uit het magazijn zijn, maar ook donorcellen uit een variëteit . Altijd genoeg is een subset .
Voor elke cel van velen Er zijn capaciteitsbeperkingen ingesteld , gemeten in dm3. Eén dm3 is een kubus met zijden van 10 cm.De producten die in het magazijn zijn opgeslagen, zijn behoorlijk groot, dus in dit geval is een dergelijke discretisatie voldoende.
Gegeven een matrix van de kortste afstanden in meters tussen elk paar cellen Waar и behoren tot sets и respectievelijk.
Laten we aanduiden “kosten” voor het verplaatsen van goederen uit de cel in een cel . Laten we aanduiden “kosten” van het kiezen van een container om resten van andere cellen erin te verplaatsen. Hoe precies en in welke meeteenheden de waarden worden berekend и we zullen er verder over nadenken (zie de sectie waarin invoergegevens worden voorbereid), voorlopig is het voldoende om te zeggen dat dergelijke waarden direct evenredig zullen zijn aan de waarden и respectievelijk.
Laten we aanduiden met een variabele die de waarde 1 aanneemt als de rest uit de cel komt verplaatst naar container , en anders 0. Laten we aanduiden met een variabele die de waarde 1 aanneemt als de container bevat de resterende goederen, en anders 0.
De taak luidt als volgt: je moet zoveel containers vinden en zo donorcellen aan containercellen “hechten” om de functie te minimaliseren
onder beperkingen
In totaal streven we er bij het berekenen van de oplossing voor het probleem naar:
- ten eerste om opslagcapaciteit te besparen;
- ten tweede om tijd te besparen voor winkeliers.
De laatste beperking betekent dat we geen goederen kunnen verplaatsen naar een container die we niet hebben gekozen, en daarom geen “kosten” hebben gemaakt voor de keuze ervan. Deze beperking betekent ook dat het volume aan goederen dat van de cellen naar de container wordt vervoerd, de capaciteit van de container niet mag overschrijden. Met het oplossen van een probleem bedoelen we een set containers en werkwijzen voor het bevestigen van donorcellen aan containers.
Deze formulering van het optimalisatieprobleem is niet nieuw en wordt sinds het begin van de jaren tachtig van de vorige eeuw door veel wiskundigen bestudeerd. In de buitenlandse literatuur zijn er 80 optimalisatieproblemen met een geschikt wiskundig model: и (we zullen het later hebben over de verschillen in taken). Het is de moeite waard om te zeggen dat in de wiskundige literatuur de formulering van dergelijke twee optimalisatieproblemen wordt geformuleerd in termen van de locatie van bedrijven ter plaatse, vandaar de naam ‘Facility Location’. Voor het grootste deel is dit een eerbetoon aan de traditie, aangezien de noodzaak om dergelijke combinatorische problemen op te lossen voor het eerst uit de logistiek kwam, vooral uit de militair-industriële sector in de jaren vijftig van de vorige eeuw. In termen van bedrijfslocatie zijn dergelijke taken als volgt geformuleerd:
- Er is een eindig aantal steden waar het potentieel mogelijk is om productiebedrijven te vestigen (hierna productiesteden genoemd). Voor elke productiestad worden de kosten voor het openen van een onderneming daarin gespecificeerd, evenals een beperking van de productiecapaciteit van de daarin geopende onderneming.
- Er is een eindige reeks steden waar klanten zich daadwerkelijk bevinden (hierna klantsteden genoemd). Voor elke klantstad wordt het volume van de vraag naar producten gespecificeerd. Voor de eenvoud gaan we ervan uit dat er slechts één product is dat door bedrijven wordt geproduceerd en door klanten wordt geconsumeerd.
- Voor elk paar stadsfabrikant en stadsklant wordt de waarde van de transportkosten voor het leveren van het vereiste volume aan producten van de fabrikant naar de klant gespecificeerd.
U moet uitzoeken in welke steden u bedrijven kunt openen en hoe u klanten aan dergelijke bedrijven kunt binden om:
- De totale kosten voor het openen van bedrijven en transportkosten waren minimaal;
- Het volume van de vraag van klanten die aan een open onderneming waren toegewezen, overschreed de productiecapaciteit van die onderneming niet.
Nu is het de moeite waard om het enige verschil in deze twee klassieke problemen te noemen:
- Single-Source Capacitated Facility Locatieprobleem – de klant wordt bevoorraad vanuit slechts één open faciliteit;
- Multi-source capaciteitsfaciliteit Locatieprobleem – de klant kan tegelijkertijd vanuit verschillende open faciliteiten worden bevoorraad.
Een dergelijk verschil tussen de twee problemen is op het eerste gezicht onbeduidend, maar leidt in feite tot een geheel andere combinatorische structuur van dergelijke problemen en, als gevolg daarvan, tot totaal verschillende algoritmen om ze op te lossen. De verschillen tussen de taken worden weergegeven in de onderstaande figuur.
Afb.3. a) Locatieprobleem van multi-source capaciteitsfaciliteit
Afb.3. b) Locatieprobleem van een gecapaciteerde faciliteit met één bron
Beide taken -moeilijk, dat wil zeggen dat er geen exact algoritme bestaat dat een dergelijk probleem zou oplossen in een tijdpolynoom in de omvang van de invoergegevens. In eenvoudiger woorden: alle exacte algoritmen voor het oplossen van een probleem zullen in exponentiële tijd werken, hoewel misschien sneller dan een volledige zoektocht naar opties. Sinds de taak -moeilijk is, zullen we alleen benaderende heuristieken overwegen, dat wil zeggen algoritmen die consequent oplossingen berekenen die zeer dicht bij het optimale liggen en die vrij snel zullen werken. Als u geïnteresseerd bent in een dergelijke taak, kunt u hier een goed overzicht in het Russisch vinden.
Als we overschakelen naar de terminologie van ons probleem van optimale compressie van goederen in cellen, dan:
- klantsteden zijn donorcellen met de overige goederen,
- productiesteden – containercellen , waarin de restanten van andere cellen moeten worden geplaatst,
- transportkosten - tijdkosten winkelier om het goederenvolume uit de donorcel te verplaatsen in een containercel ;
- kosten voor het openen van een bedrijf - kosten voor het kiezen van een container , gelijk aan het volume van de containercel , vermenigvuldigd met een bepaalde coëfficiënt voor het besparen van vrije volumes (de waarde van de coëfficiënt is altijd > 1) (zie de sectie waarin invoergegevens worden voorbereid).
Nadat de analogie met de bekende klassieke oplossingen van het probleem is getrokken, is het noodzakelijk een belangrijke vraag te beantwoorden waarvan de keuze van de architectuur van het oplossingsalgoritme afhangt: het verplaatsen van de restanten van de donorcel is slechts mogelijk naar één cel. en slechts één container (Single-Source), of is het mogelijk om de restanten naar meerdere containercellen te verplaatsen (Multi-Source)?
Het is vermeldenswaard dat in de praktijk beide probleemstellingen voorkomen. Hieronder presenteren we alle voor- en nadelen voor elke dergelijke instelling:
| Probleemvariant | Voordelen van de optie | Nadelen van de optie |
|---|---|---|
| Enkele bron | Goederenbewegingsbewerkingen berekend met behulp van deze variant van het probleem:
|
|
| Meerdere bronnen | Compressies berekend met deze versie van het probleem zijn doorgaans 10-15% compacter vergeleken met compressies berekend met de optie “Single-Source”. Maar we merken ook op dat hoe kleiner het aantal residuen in de donorcellen, hoe kleiner het verschil in compactheid | Goederenbewegingsbewerkingen berekend met behulp van deze variant van het probleem:
|
Tabel 1. Voor- en nadelen van opties met één bron en meerdere bronnen.
Omdat de Single-Source-optie meer voordelen heeft, en ook rekening houdend met het feit dat hoe kleiner het aantal residuen in donorcellen, hoe kleiner het verschil in de mate van compressiecompactheid berekend voor beide varianten van het probleem, viel onze keuze op de optie Eén bron.
Het is de moeite waard om te zeggen dat de oplossing voor de Multi-Source-optie ook plaatsvindt. Er is een groot aantal effectieve algoritmen om dit op te lossen, waarvan de meeste neerkomen op het oplossen van een aantal transportproblemen. Er zijn ook niet alleen efficiënte algoritmen, maar ook elegante, bijvoorbeeld
Invoergegevens voorbereiden
Voordat we beginnen met het analyseren en ontwikkelen van een algoritme om een probleem op te lossen, is het noodzakelijk om te beslissen welke gegevens en in welke vorm we deze als input zullen invoeren. Er zijn geen problemen met het volume van de resterende goederen in donorcellen en de capaciteit van containercellen, aangezien dit triviaal is - dergelijke hoeveelheden worden gemeten in m3, maar met de kosten van het gebruik van een containercel en de verhuiskostenmatrix, niet alles is zo eenvoudig!
Laten we eerst naar de berekening kijken kosten voor het verplaatsen van goederen van de donorcel naar de containercel. Allereerst is het noodzakelijk om te beslissen in welke meeteenheden we de bewegingskosten zullen berekenen. De twee meest voor de hand liggende opties zijn meters en seconden. Het heeft geen zin om reiskosten in ‘pure’ meters te berekenen. Laten we dit met een voorbeeld laten zien. Laat de cel gelegen op de eerste laag, cel verwijderd met 30 meter en gelegen op de tweede laag:
- Verhuizen van в duurder dan verhuizen в , aangezien het naar beneden gaan vanaf het tweede niveau (1,5-2 meter vanaf de vloer) gemakkelijker is dan naar het tweede niveau gaan, hoewel de afstand hetzelfde zal zijn;
- Verplaats 1 st. goederen uit de cel в Het zal gemakkelijker zijn dan 10 stukken verplaatsen. hetzelfde product, hoewel de afstand hetzelfde zal zijn.
Het is beter om de verhuiskosten binnen enkele seconden te overwegen, omdat u hierdoor zowel rekening kunt houden met het verschil in niveaus als met het verschil in de hoeveelheid verplaatste goederen. Om rekening te houden met de kosten van beweging in seconden, moeten we de bewegingsoperatie opsplitsen in elementaire componenten en tijdmetingen uitvoeren voor de uitvoering van elke elementaire component.
Laat vanuit de cel beweegt PC. goederen in containers . Laten – de gemiddelde bewegingssnelheid van een werknemer in het magazijn, gemeten in m/sec. Laten и – gemiddelde snelheden van respectievelijk het nemen en plaatsen van eenmalige handelingen voor een goederenvolume gelijk aan 4 dm3 (het gemiddelde volume dat een werknemer tegelijkertijd in een magazijn inneemt bij het uitvoeren van handelingen). Laten и de hoogte van de cellen van waaruit respectievelijk de take- en put-bewerkingen worden uitgevoerd. De gemiddelde hoogte van de eerste laag (vloer) is bijvoorbeeld 1 m, de tweede laag is 2 m, enz. De formule voor het berekenen van de totale tijd voor het voltooien van een verplaatsingsoperatie is dan: in aansluiting op:
Tabel 2 toont statistieken over de uitvoeringstijd van elke elementaire handeling, verzameld door magazijnmedewerkers, rekening houdend met de specifieke kenmerken van de opgeslagen goederen.
| de naam van de operatie | Aanwijzing | Gemeen |
|---|---|---|
| Gemiddelde snelheid van een werknemer die zich door het magazijn beweegt | |
1,5 m/s |
| Gemiddelde snelheid van één handeling (voor een productvolume van 4 dm3) | |
2,4 sec |
Tabel 2. Gemiddelde tijd voor het voltooien van magazijnwerkzaamheden
Wij hebben de methode voor het berekenen van de verhuiskosten bepaald. Nu moeten we uitzoeken hoe we moeten berekenen kosten voor het kiezen van een containercel. Alles is hier veel, veel ingewikkelder dan bij verhuiskosten, omdat:
- ten eerste moeten de kosten rechtstreeks afhankelijk zijn van het volume van de cel - hetzelfde volume aan residuen dat wordt overgebracht van donorcellen kan beter in een container met een kleiner volume worden geplaatst dan in een grote container, op voorwaarde dat een dergelijk volume volledig in beide containers past. Door de totale kosten voor het selecteren van containers te minimaliseren, streven we er dus naar om “schaarse” vrije opslagcapaciteit in het selectiegebied te besparen om daaropvolgende bewerkingen uit te voeren, zoals het plaatsen van goederen in cellen. Figuur 4 toont de mogelijkheden voor het overbrengen van reststoffen naar grote en kleine containers en de gevolgen van deze overslagmogelijkheden bij daaropvolgende magazijnoperaties.
- ten tweede, omdat we bij het oplossen van het oorspronkelijke probleem precies de totale kosten moeten minimaliseren, en dit is de som van zowel de verplaatsingskosten als de kosten van het kiezen van containers, moeten de celvolumes in kubieke meters op de een of andere manier worden gekoppeld aan seconden, wat verre van triviaal is.
Rijst. 4. Opties voor het verplaatsen van restjes naar containers met verschillende capaciteiten.
Figuur 4 toont in rood het volume aan restjes dat niet meer in de container past in de tweede fase van het plaatsen van volgende goederen.
Het zal helpen om de kubieke meters kosten voor het kiezen van een container te koppelen aan de seconden aan kosten voor het verplaatsen van de volgende vereisten voor berekende oplossingen voor het probleem:
- Het is in ieder geval noodzakelijk dat de saldi uit de donorbak naar de containerbak worden verplaatst als hierdoor het totaal aantal containerbakken met het product afneemt.
- Het is noodzakelijk om een evenwicht te bewaren tussen het volume van de containers en de tijd die wordt besteed aan het verplaatsen: bijvoorbeeld als bij een nieuwe oplossing voor een probleem in vergelijking met de vorige oplossing de volumewinst groot is, maar het tijdverlies klein is , dan is het noodzakelijk om een nieuwe optie te kiezen.
Laten we beginnen met de laatste vereiste. Om het dubbelzinnige woord ‘balans’ te verduidelijken, hebben we een enquête gehouden onder magazijnmedewerkers om het volgende te achterhalen. Laat er een containercel met volume zijn , waaraan de beweging van resterende goederen uit donorcellen is toegewezen en de totale tijd van een dergelijke beweging gelijk is aan . Laat er verschillende alternatieve opties zijn om dezelfde hoeveelheid goederen uit dezelfde donorcellen in andere containers te plaatsen, waarbij elke plaatsing zijn eigen schattingen heeft Waar < и Waar >.
De vraag wordt gesteld: wat is de minimale volumewinst aanvaardbaar, voor een gegeven tijdverlieswaarde ? Laten we het uitleggen met een voorbeeld. Aanvankelijk zouden de stoffelijke resten in een container met een inhoud van 1000 dm3 (1 m3) worden geplaatst en de overdrachtstijd bedroeg 70 seconden. Er bestaat een mogelijkheid om de reststoffen in een andere container met een inhoud van 500 dm3 en een tijd van 130 seconden te plaatsen. Vraag: zijn we bereid om 60 seconden extra tijd van de winkelier te besteden aan het verplaatsen van de goederen om zo 500 dm3 vrij volume te besparen? Op basis van de resultaten van een enquête onder magazijnmedewerkers is onderstaand schema samengesteld.
Rijst. 5. Diagram van de afhankelijkheid van de minimaal toegestane volumebesparing van de toename van het verschil in bedrijfstijd
Dat wil zeggen, als de extra tijdskosten 40 seconden bedragen, dan zijn we bereid deze alleen te besteden als de volumewinst minimaal 500 dm3 bedraagt. Ondanks het feit dat er een lichte niet-lineariteit in de afhankelijkheid zit, zullen we voor de eenvoud van verdere berekeningen aannemen dat de afhankelijkheid tussen de grootheden lineair is en wordt beschreven door de ongelijkheid
In de onderstaande figuur beschouwen we de volgende methoden voor het plaatsen van goederen in containers.
Rijst. 6. Optie (a): 2 containers, totaal volume 400 dm3, totale tijd 150 sec.
Rijst. 6. Optie (b): 2 containers, totaal volume 600 dm3, totale tijd 190 sec.
Rijst. 6. Optie (c): 1 container, totaal volume 400 dm3, totale tijd 200 sec.
Optie (a) voor het kiezen van containers heeft meer de voorkeur dan de oorspronkelijke optie, omdat de ongelijkheid geldt: (800-400)/10>=150-120, wat impliceert dat 40 >= 30 is. Optie (b) heeft minder de voorkeur dan het origineel optie , aangezien de ongelijkheid niet geldt: (800-600)/10>=190-150, wat 20 >= 40 impliceert. Maar optie (c) past niet in een dergelijke logica! Laten we deze optie in meer detail bekijken. Aan de ene kant de ongelijkheid (800-400)/10>=200-120, wat betekent dat de ongelijkheid 40 >= 80 niet opgaat, wat erop wijst dat de volumewinst zo'n groot verlies in tijd niet waard is.
Maar aan de andere kant verminderen we bij deze optie (c) niet alleen het totale bezette volume, maar verminderen we ook het aantal bezette cellen, wat de eerste van twee belangrijke vereisten is voor berekenbare oplossingen voor de hierboven genoemde problemen. Om aan deze eis te kunnen voldoen, is het uiteraard noodzakelijk om een positieve constante aan de linkerkant van de ongelijkheid toe te voegen. , en een dergelijke constante hoeft alleen te worden toegevoegd als het aantal containers afneemt. Laten we dat in herinnering brengen is een variabele gelijk aan 1 wanneer de container geselecteerd, en 0 bij container niet geselecteerd. Laten we aanduiden – veel containers in de initiële oplossing en – veel containers in de nieuwe oplossing. Over het algemeen zal de nieuwe ongelijkheid er als volgt uitzien:
Als we de bovenstaande ongelijkheid transformeren, krijgen we
Op basis hiervan hebben we een formule voor het berekenen van de totale kosten een oplossing voor het probleem:
Maar nu rijst de vraag: welke waarde moet zo'n constante hebben? ? Het is duidelijk dat de waarde ervan groot genoeg moet zijn, zodat altijd aan de eerste vereiste voor oplossingen voor het probleem wordt voldaan. Je kunt natuurlijk de waarde van de constante gelijk stellen aan 103 of 106, maar ik zou zulke “magische getallen” graag willen vermijden. Als we de details van het uitvoeren van magazijnoperaties in ogenschouw nemen, kunnen we verschillende goed onderbouwde numerieke schattingen van de waarde van een dergelijke constante berekenen.
Laten – de maximale afstand tussen magazijncellen van één zone ABC, in ons geval gelijk aan 100 m. Let – het maximale volume van een containercel in een magazijn, in ons geval gelijk aan 1000 dm3.
De eerste manier om de waarde te berekenen . Laten we een situatie bekijken waarin er 2 containers op de eerste laag staan, waarin de goederen zich al fysiek bevinden, dat wil zeggen dat ze zelf donorcellen zijn, en de kosten voor het verplaatsen van de goederen naar dezelfde cellen zijn uiteraard gelijk aan 0. is nodig om een dergelijke waarde voor de constante te vinden , waarbij het voordelig zou zijn om de restjes altijd van container 1 naar container 2 te verplaatsen. De waarden vervangen и In de hierboven gegeven ongelijkheid krijgen we:
waaruit volgt
Als we de waarden van de gemiddelde tijd voor het uitvoeren van elementaire bewerkingen vervangen door de bovenstaande formule, krijgen we
De tweede manier om de waarde te berekenen . Laten we een situatie bekijken waarin dat wel het geval is donorcellen van waaruit het de bedoeling is de goederen naar container 1 te verplaatsen. Laten we aangeven – afstand tot de donorcel naar container 1. Er is ook container 2, waar al goederen in zitten, en waarvan de inhoud het mogelijk maakt de rest van alle goederen te huisvesten. cellen. Voor de eenvoud gaan we ervan uit dat het volume aan goederen dat van donorcellen naar containers wordt verplaatst hetzelfde en gelijk is aan . Het is vereist om een dergelijke waarde van de constante te vinden , waarin de plaatsing van alle restanten uit cellen in container 2 zouden altijd winstgevender zijn dan ze in verschillende containers te plaatsen:
Het transformeren van de ongelijkheid die we krijgen
Om de waarde van de hoeveelheid te ‘versterken’ , laten we dat aannemen = 0. Het gemiddelde aantal cellen dat gewoonlijk betrokken is bij de procedure voor het comprimeren van magazijnsaldi is 10. Als we de bekende waarden van de hoeveelheden vervangen, hebben we de volgende waarde van de constante
We nemen de grootste berekende waarde voor elke optie, dit is de waarde van de hoeveelheid voor de opgegeven magazijnparameters. Laten we nu voor de volledigheid de formule opschrijven voor het berekenen van de totale kosten voor een haalbare oplossing :
Nu tenslotte titanische inspanningen Door de invoergegevens te transformeren kunnen we zeggen dat alle invoergegevens zijn omgezet naar de gewenste vorm en klaar zijn voor gebruik in het optimalisatiealgoritme.
Conclusie
Zoals de praktijk laat zien, wordt de complexiteit en het belang van de fase van het voorbereiden en transformeren van invoergegevens voor een algoritme vaak onderschat. In dit artikel hebben we specifiek veel aandacht besteed aan deze fase om aan te tonen dat alleen hoogwaardige en intelligent voorbereide invoergegevens de door het algoritme berekende beslissingen echt waardevol kunnen maken voor de klant. Ja, er waren veel afleidingen van formules, maar we waarschuwden je al vóór de kata :)
In het volgende artikel komen we eindelijk bij waar de twee voorgaande publicaties voor bedoeld waren: een discreet optimalisatie-algoritme.
Het artikel voorbereid
Roman Shangin, programmeur van de projectenafdeling,
First Bit-bedrijf, Tsjeljabinsk
Bron: www.habr.com