Discrete wiskunde voor WMS: algoritme voor het comprimeren van goederen in cellen (deel 1)

In dit artikel bespreken we hoe we het probleem van een tekort aan vrije opslagruimtes in het magazijn hebben opgelost, en we vertellen over de ontwikkeling van een algoritme voor discrete optimalisatie om dit probleem aan te pakken. We zullen ook laten zien hoe we een wiskundig model voor de optimalisatie hebben 'gebouwd', en met welke onverwachte problemen we zijn geconfronteerd bij de verwerking van de invoergegevens voor het algoritme.

Als u geïnteresseerd bent in de toepassingen van wiskunde in het bedrijfsleven en niet bang bent voor zware identieke herschrijvingen van formules op het niveau van groep 5, dan bent u van harte welkom onder de cat!

Het artikel zal nuttig zijn voor degenen die WMS-systemen implementeren, in de sector van magazijn- of productie-logistiek werken, evenals voor programmeurs die geïnteresseerd zijn in de toepassingen van wiskunde in het bedrijfsleven en in procesoptimalisatie in een bedrijf.

Inleiding

Deze publicatie vervolgt een reeks artikelen waarin we onze succesvolle ervaring delen met de implementatie van optimalisatie-algoritmen in magazijnprocessen.

In vorig artikel de specificiteit van het magazijn wordt beschreven waarin wij de WMS-systeem hebben geïmplementeerd, en we vertellen ook waarom we het probleem van clustering van partijen resterende goederen bij de implementatie van WMS-systemen moesten oplossen, en hoe we dit hebben gedaan.

Toen we het artikel over optimalisatie-algoritmen schreven, werd het erg groot, dus besloten we het verzamelde materiaal op te splitsen in 2 delen:

• In het eerste deel (dit artikel) vertellen we hoe we het wiskundige model van het probleem hebben 'gebouwd', en met welke grote moeilijkheden we onverwacht werden geconfronteerd bij het verwerken en transformeren van de invoergegevens voor het algoritme.
• In het tweede deel zullen we de implementatie van het algoritme in de taal gedetailleerd bekijken, C++, we zullen 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 u het artikel moet lezen. Als u het vorige artikel hebt gelezen, kunt u meteen naar het hoofdstuk 'Overzicht van bestaande oplossingen' gaan; als dat niet het geval is, vindt u de beschrijving van het probleem dat wordt opgelost in de spoiler hieronder.

Beschrijving van het probleem dat zich voordoet in het magazijn van de klant

De bottleneck in de processen

In 2018 hebben we een project uitgevoerd voor de implementatie van een WMS-systeem in het magazijn 'Handelshuis 'LD' in Chelyabinsk. We hebben het product '1C-Logistiek: Magazijnbeheer 3' geïmplementeerd op 20 werkplekken: operators. WMS, magazijnmedewerkers, heftruckchauffeurs. Het magazijn heeft een gemiddelde oppervlakte van ongeveer 4.000 m2, met 5.000 vakken en 4.500 SKU’s. In het magazijn worden bolkranen van eigen productie opgeslagen in verschillende maten van 1 kg tot 400 kg. De voorraden in het magazijn worden opgeslagen per partij, aangezien er behoefte is aan het selecteren van goederen op FIFO.

Tijdens het ontwerpen van automatiseringsschema's voor magazijnprocessen stuitten we op een bestaande uitdaging van suboptimale opslag van voorraden. De specifieke opslag en stapeling van de kranen is zodanig dat in één vak voor eenhedenopslag slechts de nomenclatuur van één partij kan worden opgeslagen (zie fig. 1). De producten komen dagelijks in het magazijn aan, met elke levering als een aparte partij. In totaal ontstaan er na 1 maand operationele magazijnactiviteit 30 afzonderlijke partijen, waarbij elke partij in een afzonderlijk vak moet worden opgeslagen. De goederen worden vaak niet als complete pallets, maar als losse eenheden geselecteerd, waardoor in het gros van de vakken in de eenheden-opslag de volgende situatie zichtbaar is: in een vak van meer dan 1 m3 liggen enkele kranen die minder dan 5-10% van het vakvolume innemen.

Figuur 1. Foto van meerdere eenheden in een vak

Er is een suboptimaal gebruik van magazijncapaciteit zichtbaar. Ter illustratie van de omvang van het probleem kan ik cijfers aanvoeren: gemiddeld zijn er tijdens verschillende periodes van magazijnoperaties tussen de 100 en 300 van dergelijke vakken met een volume van meer dan 1 m3 en ‘verwaarloosbare’ restanten. Aangezien het magazijn relatief klein is, wordt deze factor tijdens drukke seizoenen een 'knelpunt' dat de magazijnprocessen van ontvangst en verzending ernstig vertraagt.

Het idee voor een oplossing van het probleem

Het idee ontstond om partijen met de meest nabijgelegen datums samen te brengen tot één enkele partij en dergelijke restanten met een geharmoniseerde partij compact in één vak, of in meerdere vakken als er niet genoeg ruimte is in één vak, op te slaan. Een voorbeeld van zo'n 'compressie' is afgebeeld in figuur 2.

Figuur 2. Schema van compressie van restanten in vakken

Dit stelt ons in staat om de benodigde magazijnruimte aanzienlijk te verminderen, die gebruikt zal worden voor de nieuw te plaatsen goederen. In situaties met overbelasting van magazijncapaciteiten is zo'n maatregel uiterst noodzakelijk, anders kan de beschikbare ruimte voor het plaatsen van nieuwe goederen eenvoudigweg niet voldoende zijn, wat zal leiden tot een stilstand van de magazijnprocessen voor plaatsing en aanvulling en, als gevolg daarvan, tot een stilstand van de ontvangst en verzending. Vroeger, vóór de implementatie van het WMS-systeem, werd deze operatie handmatig uitgevoerd, wat niet efficiënt was, omdat het proces van het zoeken naar geschikte restanten in de compartimenten vrij lang was. Nu, met de implementatie van het WMS-systeem, hebben we besloten het proces te automatiseren, te versnellen en intelligenter te maken.

Het proces om deze taak op te lossen wordt verdeeld in 2 fasen:

• in de eerste fase zoeken we naar nabijgelegen partijen op datum voor compressie (deze taak is gewijd aan) het vorige artikel);
• in de tweede fase berekenen we voor elke partij de meest compacte plaatsing van de productrestanten in de compartimenten.

In dit artikel zullen we ons concentreren op de tweede fase van het algoritme.

Overzicht van bestaande oplossingen

Voordat we overgaan tot de beschrijving van de algoritmen die we hebben ontwikkeld, is het de moeite waard om een kort overzicht te geven van de al bestaande systemen op de markt WMS, waarin zulk een functionaliteit van optimale compressie is geïmplementeerd.

Allereerst moet het product "1C: Bedrijf 8. WMS Logistiek. Magazijnbeheer 4" worden vermeld, dat eigendom is van en wordt uitgegeven door het bedrijf 1C en behoort tot de vierde generatie WMS-systemen, ontwikkeld door het bedrijf AXELOT. In dit systeem wordt de functionaliteit van compressie aangekondigd, die is ontworpen om verspreide productrestanten in één gemeenschappelijk compartiment samen te voegen. Het moet worden opgemerkt dat de compressiefunctie in zo'n systeem ook andere mogelijkheden omvat, bijvoorbeeld het corrigeren van de plaatsing van goederen in compartimenten volgens hun ABC-klassen, maar daar zullen we niet op ingaan.

Bij de analyse van de code van het systeem '1C: Enterprise 8. WMS Logistiek. Voorraadbeheer 4' (dat op dit deel van de functionaliteit openbaar is), kan het volgende worden geconcludeerd. Het compressie-algoritme voor voorraden volgt een vrij primitieve lineaire logica en er kan niet gesproken worden van enige 'optimale' compressie. Uiteraard voorziet de algoritme niet in de clustering van partijen. Verschillende klanten die dit systeem hebben geïmplementeerd, hebben geklaagd over de resultaten van de compressieplanning. Bijvoorbeeld, in de praktijk gebeurde het vaak dat: 100 stuks van een product uit één vakje gepland werden om te verplaatsen naar een ander vakje, waar 1 stuk van het product ligt, terwijl het vanuit tijdsbesparing optimaal zou zijn om het omgekeerd te doen.

Ook de functionaliteit van de compressie van voorraden in vakken is in veel buitenlandse WMS-systemen aangekondigd, maar helaas hebben we geen daadwerkelijke beoordelingen over de effectiviteit van de algoritmen (dit is commercieel geheim), noch enige voorstelling van de diepte van hun logica (propriëtaire software met gesloten code), waardoor we er geen oordeel over kunnen vellen.

Zoektocht naar een wiskundig model voor de taak

Om kwalitatieve algoritmen te ontwerpen voor het oplossen van de taak, is het noodzakelijk om deze taak eerst duidelijk wiskundig te formuleren, wat we zullen doen.

Er zijn veel vakken , waarin de restanten van een bepaald product zich bevinden. We zullen deze vakken voortaan donorvakken noemen. Laten we de hoeveelheid product die zich in het vak bevindt $.

Belangrijk is om te zeggen dat in het compressieproces alleen één product van één partij kan deelnemen, of van verschillende partijen die vooraf in een cluster zijn samengevoegd (lees het vorige artikel), wat het gevolg is van de specifieke opslag en indeling van producten. Voor verschillende producten of verschillende clusters van partijen moet er een aparte compressieprocedure worden gestart.

Er zijn veel vakken , waarin de restanten van de donorvakken potentieel kunnen worden geplaatst. We zullen deze vakken voortaan container-vakken noemen. Dit kunnen zowel vrije vakken in het magazijn zijn als donorvakken uit veelvoudige . Altijd is veelvoudige een deelverzameling van .

Voor elk vak uit veelvuldige zijn er beperkingen op de capaciteit ingesteld. , gemeten in dm3. Eén dm3 is een kubus met zijden van 10 cm. De producten die in het magazijn worden opgeslagen zijn groot genoeg, dus in dit geval is deze discretisering voldoende.

Er is een matrix van de kortste afstanden opgegeven in meters tussen elk paar vakken , waar en behoren tot verzamelingen en respectievelijk.

Laten we de 'kosten' voor het verplaatsen van goederen van de vak naar de vak . Laten we de 'kosten' voor het kiezen van een container voor het verplaatsen van resten uit andere vakken. Hoe precies en in welke eenheden de waarden worden berekend, en wordt later besproken (zie sectie voorbereiding van de invoergegevens), voor nu is het voldoende te zeggen dat deze waarden recht evenredig zullen zijn met de grootten en respectievelijk.

Laten we de variabele aanduiden die de waarde 1 aanneemt als de resten uit de vak worden verplaatst naar de container , en 0 in het andere geval. Laten we de variabele aanduiden die de waarde 1 aanneemt als de container resten van goederen bevat, en 0 in het andere geval.

De taak wordt als volgt gesteld: we moeten een zodanige verzameling containers vinden en zo de donorvakken aan de container-vakken 'hechten', zodat we de functie minimaliseren

onder beperkingen

Kortom, tijdens het berekenen van de oplossing van de taak streven we naar:

• ten eerste, het besparen van magazijncapaciteit;
• ten tweede, het besparen van tijd voor magazijnmedewerkers.

De laatste beperking betekent dat we goederen niet kunnen verplaatsen naar een container die we niet hebben gekozen, en dus die we ook geen 'kosten' voor hebben gemaakt om te kiezen. Evenzo betekent deze beperking dat het volume van de verplaatste goederen van de vakken naar de container niet groter mag zijn dan de capaciteit van de container. We verstaan onder de oplossing van de taak de verzameling containers en de manieren om de donor-vakken aan de containers te hechten.

Deze formulering van het optimaliseringsprobleem is niet nieuw en is door vele wiskundigen onderzocht sinds het begin van de jaren 80 van de vorige eeuw. In de buitenlandse literatuur zijn er 2 optimaliseringsproblemen met een geschikte wiskundige model: Single-Source Capacitated Facility Location Problem en Multi-Source Capacitated Facility Location Problem (over de verschillen in taken zullen we later praten). Het is vermeldenswaard dat in de wiskundige literatuur de formuleringen van deze twee optimalisatieproblemen worden gepresenteerd in termen van de locatie van bedrijven in een gebied, vandaar de naam 'Facility Location'. Dit is voor een groot deel een eerbetoon aan de traditie, aangezien de behoefte om dergelijke combinatorische problemen op te lossen voor het eerst voortkwam uit het logistieke domein, voornamelijk in de militaire en industriële sector in de jaren vijftig van de vorige eeuw. In termen van bedrijfsplaatsing worden dergelijke problemen als volgt geformuleerd:

• Er is een eindig aantal steden waar potentiële productiebedrijven kunnen worden gevestigd (hierna steden-producenten genoemd). Voor elke stad-producent zijn de kosten voor het openen van een bedrijf en de productiecapaciteit van het bedrijf dat daarin wordt geopend, gegeven.
• Er is een eindig aantal steden waar de klanten zich daadwerkelijk bevinden (hierna steden-klanten genoemd). Voor elke stad-klant is de vraag naar producten vastgesteld. Voor de eenvoud nemen we aan dat het product dat door de bedrijven wordt geproduceerd en door de klanten wordt geconsumeerd, hetzelfde is.
• Voor elk paar stad-producent en stad-klant zijn de transportkosten voor het leveren van het vereiste volume producten van de producent aan de klant vastgesteld.

Het is nodig te bepalen in welke steden bedrijven moeten worden geopend en hoe de klanten aan deze bedrijven moeten worden toegewezen, zodat:

• De totale kosten voor het openen van bedrijven en de transportkosten minimaal zijn;
• De vraag van de klanten die aan een geopend bedrijf zijn toegewezen, de productiecapaciteit van dat bedrijf niet overschrijdt.

Nu is het tijd om te spreken over het enige verschil tussen deze twee klassieke problemen:

• Single-Source Capacitated Facility Location Problem – de klant wordt slechts door één geopend bedrijf bevoorraad;
• Multi-Source Capacitated Facility Location Problem – de klant kan gelijktijdig door verschillende geopende bedrijven worden bevoorraad.

Dit verschil tussen de twee problemen lijkt op het eerste gezicht onbeduidend, maar leidt in werkelijkheid tot een totaal andere combinatorische structuur van deze problemen en, als gevolg daarvan, tot compleet verschillende algoritmen voor hun oplossing. Het verschil tussen de problemen wordt geïllustreerd in de onderstaande afbeelding.

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

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

Beide problemen - moeilijk, wat betekent dat er geen exacte algoritme bestaat dat het probleem in polynomiale tijd van de grootte van de invoer kan oplossen. Eenvoudiger gezegd, zullen alle exacte algoritmen voor het oplossen van het probleem exponentiële tijd nodig hebben, hoewel ze mogelijk sneller zijn dan brute force uitputting. Aangezien het probleem - moeilijk is, zullen we alleen benaderende heuristieken overwegen, dat wil zeggen algoritmen die stabiele oplossingen berekenen die zeer dicht bij de optimale liggen en voldoende snel werken. Als er interesse is in dergelijke problemen, kan hier een goede samenvatting in het Nederlands worden gevonden.

Als we de terminologie van onze taak van optimale opslag van goederen in cellen gebruiken, dan:

• de steden-klanten zijn de cellen-donoren met restvoorraden,
• de steden-producenten zijn de cellen-containers , waarin we de restvoorraden uit andere cellen willen plaatsen,
• transportkosten zijn de tijdskosten van de magazijnbeheerder voor het verplaatsen van de hoeveelheid goederen van cel-donor naar cel-container ;
• de kosten voor het openen van een onderneming zijn de kosten voor het selecteren van de container , gelijk aan het volume van de cel-container , vermenigvuldigd met een bepaalde besparingscoëfficiënt (de waarde van de coëfficiënt is altijd > 1) (zie de sectie voorbereiding van de invoergegevens).

Nadat de analogie met de bekende klassieke leveringsvraag is gemaakt, moet een belangrijke vraag worden beantwoord die de keuze van de architectuur van het oplossingsalgoritme bepaalt: is het mogelijk om restvoorraden alleen van cel-donor naar één en slechts één container (Single-Source) te verplaatsen, of is het mogelijk om restvoorraden naar meerdere cellen-containers (Multi-Source) te verplaatsen?

Het is vermeldenswaard dat in de praktijk beide problematiek mogelijk is. We zullen hieronder alle ‘voor’ en ‘tegen’ voor elke probleemstelling opsommen:

Tabel 1. Voor- en nadelen van de varianten Single-Source en Multi-Source.

Aangezien het aantal voordelen voor de variant Single-Source groter is, en rekening houdend met het feit dat hoe kleiner het aantal voorraden in de donorvakken, des te geringer het verschil in de mate van compactheid van de compressie, berekend volgens beide varianten van de taak, is, hebben we gekozen voor de variant Single-Source.

Het moet worden vermeld dat de oplossing van de Multi-Source-variant ook valide is. Er zijn veel effectieve algoritmes voor het oplossen ervan, waarvan de meeste neerkomen op het oplossen van een reeks transportproblemen. Er zijn niet alleen effectieve algoritmes, maar ook elegante, bijvoorbeeld: hier.

Voorbereiding van de invoergegevens

Voordat we beginnen met de analyse en het ontwikkelen van het algoritme voor het oplossen van de taak, moeten we bepalen welke gegevens en in welke vorm we deze als invoer aan het algoritme zullen geven. Er zijn geen problemen met de voorraden van producten in de donorvakken en de capaciteit van de container-vakken, aangezien dit triviaal is – dergelijke grootheden worden gemeten in m3, maar met de kosten voor het gebruik van het container-vak en de kostenmatrix voor verplaatsing is het niet zo eenvoudig!

Laten we eerst de berekening bekijken. kosten voor het verplaatsen van goederen van de donorcel naar de container. Ten eerste moeten we bepalen in welke eenheden we de kosten voor het verplaatsen zullen berekenen. De twee meest voor de hand liggende opties zijn meters en seconden. Het is zinloos om de kosten voor het verplaatsen in "schone" meters te berekenen. Laten we dit illustreren met een voorbeeld. Stel dat de cel ondanks de eerste laag, op 30 meter is verwijderd en zich op de tweede laag bevindt: Vervoer vanuit

• is duurder dan vervoer vanuit in , omdat het makkelijker is om naar beneden te dalen vanaf de tweede verdieping (1,5-2 meter van de grond) dan om naar de tweede verdieping te stijgen, hoewel de afstand hetzelfde zou zijn; in Een enkel item verplaatsen vanuit de cel
• zal gemakkelijker zijn dan 10 dezelfde items verplaatsen, hoewel de afstand gelijk zal zijn. in Het is beter om de verplaatsingskosten in seconden te berekenen, omdat dit zowel de verschillen in de lagen als het verschil in de hoeveelheid verplaatste goederen in rekening brengt. Om de verplaatsingskosten in seconden te berekenen, moeten we de verplaatsing operaties splitsen in elementaire componenten en de tijd meten die voor elke elementaire component nodig is.

Laten we zeggen dat er

wordt verplaatst stuks goederen naar container . Laten we zeggen dat de gemiddelde snelheid is waarmee een werknemer door het magazijn beweegt, gemeten in m/s. Laten we zeggen dat de gemiddelde snelheden voor het uitvoeren van de acties 'nemen' en 'leggen' respectievelijk zijn voor een volume goederen van 4 dm3 (het gemiddelde volume dat een werknemer op een keer in het magazijn vervoert). Laten we zeggen dat en de hoogte van de cellen is waaruit de acties 'nemen' en 'leggen' worden uitgevoerd. Bijvoorbeeld, de gemiddelde hoogte van de eerste laag (vloer) is 1 m, de tweede laag 2 m, enzovoort. De formule voor het berekenen van de totale tijd voor de uitvoering van de verplaatsingsoperatie en is als volgt: Tabel 2 bevat de statistieken van de tijd die nodig is voor elke elementaire operatie, verzameld door magazijnmedewerkers met inachtneming van de specifieke kenmerken van de opgeslagen goederen.

Naam van de operatie

Aanduiding	Gemiddelde waarde	Gemiddelde snelheid van de werknemer in het magazijn
1,5 m/s		Gemiddelde snelheid van de uitvoering van één actie 'leggen' (voor een volume goederen van 4 dm3)
2,4 sec		Tabel 2. Gemiddelde tijd voor het uitvoeren van magazijnoperaties

We hebben de methode voor het berekenen van de verplaatsingskosten vastgesteld. Nu moeten we uitvinden hoe we

de kosten voor het kiezen van de containercel kunnen berekenen. kosten voor de selectie van een containercelHet is hier veel, veel complexer dan de kosten voor verplaatsing, omdat:

• ten eerste, de kosten moeten direct afhankelijk zijn van het volume van de cellen – hetzelfde volume van de voorraden, verplaatst vanuit donor-cellen, kan beter in een kleinere container worden geplaatst dan in een grote container, mits dat volume volledig in beide containers past. Door de totale kosten voor het kiezen van containers te minimaliseren, proberen we ‘schaarse’ vrije opslagcapaciteit in het pickgebied te besparen, voor de uitvoering van daaropvolgende goederenplaatsingen in de cellen. In Figuur 4 worden de opties voor het verplaatsen van voorraden naar grote en kleine containers en de gevolgen van dergelijke verplaatsingsopties bij het uitvoeren van daaropvolgende magazijnoperaties geïllustreerd.
• ten tweede, omdat we in de oplossing van de oorspronkelijke taak de totale kosten moeten minimaliseren, wat de som is van zowel de verplaatsingskosten als de kosten van het kiezen van containers, moeten de volumes van de cellen in kubieke meters op de een of andere manier gekoppeld worden aan seconden, wat verre van triviaal is.

Figuur 4. Varianten voor het verplaatsen van voorraden naar containers met verschillende capaciteiten.

In Figuur 4 is in het rood aangegeven het volume van de voorraden dat al niet meer in de container past in de tweede fase van de plaatsing van daaropvolgende goederen.

De volgende eisen aan de berekende oplossingen van de taak zullen helpen om kubieke meters kosten voor het kiezen van een container te koppelen aan seconden van verplaatsingskosten:

• Het is noodzakelijk dat voorraden uit de donor-cel in de container-cel worden verplaatst, als dit het totale aantal container-cellen vermindert waarin het product zich bevindt.
• Het is noodzakelijk om een balans te behouden tussen de volumes van de containers en de tijdskosten van de verplaatsing: bijvoorbeeld, als in de nieuwe oplossing ten opzichte van de vorige oplossing de winst in volume groot is en het verlies in tijdskosten klein is, dan moet de nieuwe optie worden gekozen.

Laten we beginnen met de laatste vereiste. Om het meerduidige woord 'balans' te concretiseren, hebben we een enquête gehouden onder de magazijnmedewerkers om het volgende te achterhalen. Laat er een container-cel met een volume zijn , waarin de verplaatsing van voorraden uit donor-cellen is toegewezen en de totale tijd van deze verplaatsing is gelijk aan Laten we zeggen dat er nog een aantal alternatieve opties zijn voor het plaatsen van dezelfde hoeveelheid goederen uit dezelfde donorcellules in andere containers, waarbij elke plaatsing zijn eigen beoordelingen heeft. , waar < en , waar >.

De vraag is: wat is de minimale volumewinst die acceptabel is, gegeven de vastgestelde verlies in tijd? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Figuur 5. Diagram van de relatie tussen de minimale toegestane volumebesparing en de toename van het tijdsverschil bij het uitvoeren van de operatie.

Dat wil zeggen, als de extra tijdskosten 40 seconden bedragen, zijn we bereid deze op te offeren alleen wanneer de volumewinst minimaal 500 dm³ is. Ondanks dat er een kleine nonlineariteit in de relatie is, zullen we voor de eenvoud van verdere berekeningen aannemen dat de relatie lineair is en wordt beschreven door een ongelijkheid.

In de onderstaande afbeelding bekijken we de volgende manieren om goederen in containers te plaatsen.

Figuur 6. Optie (a): 2 containers, gezamenlijk volume 400 dm³, totale tijd 150 sec.

Figuur 6. Optie (b): 2 containers, gezamenlijk volume 600 dm³, totale tijd 190 sec.

Figuur 6. Optie (c): 1 container, gezamenlijk volume 400 dm³, totale tijd 200 sec.

Optie (a) voor het kiezen van containers is gunstiger dan de oorspronkelijke optie, aangezien de ongelijkheid wordt vervuld: (800-400)/10 >= 150-120 waaruit volgt dat 40 >= 30. Optie (b) is minder gunstig dan de oorspronkelijke optie, aangezien de ongelijkheid niet wordt vervuld: (800-600)/10 >= 190-150 waaruit volgt dat 20 >= 40. Maar optie (c) past niet binnen deze logica! Laten we deze optie nader bekijken. Enerzijds is er de ongelijkheid (800-400)/10 >= 200-120, dat wil zeggen dat de ongelijkheid 40 >= 80 niet wordt vervuld, wat aangeeft dat de volumewinst niet de grote tijdsverliezen rechtvaardigt.

Aan de andere kant, in deze optie (c) verminderen we niet alleen het totale gebruikte volume, maar ook het aantal gebruikte cellen, wat het eerste van de twee belangrijke vereisten is voor de berekende oplossingen van de bovenstaande problemen. Het is duidelijk dat om aan deze vereiste te voldoen, er een positieve constante aan de linkerkant van de ongelijkheid moet worden toegevoegd. , waarbij deze constante alleen moet worden toegevoegd wanneer het aantal containers afneemt. Laten we niet vergeten dat — een variabele is die gelijk is aan 1 wanneer de container is geselecteerd, en 0 wanneer de container niet geselecteerd. Laten we het aanduiden, – een aantal containers in de oorspronkelijke oplossing en – een aantal containers in de nieuwe oplossing. In algemene termen zal de nieuwe ongelijkheid er als volgt uitzien:

Door de bovenstaande ongelijkheid te herformuleren, krijgen we

Op basis hiervan hebben we een formule voor het berekenen van de totale kosten van een bepaalde variant van de probleemoplossing:

Maar nu rijst de vraag: welke waarde zou zo'n constante moeten hebben ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Laat – de maximale afstand tussen de cellen van het magazijn in één zone ABC zijn, die in ons geval 100 m bedraagt. Laat – het maximale volume van een cel-container in het magazijn zijn, dat in ons geval 1000 dm3 bedraagt.

De eerste manier om de waarde te berekenen . Laten we een situatie bekijken waarin er 2 containers op de eerste laag zijn, waarin zich al fysiek goederen bevinden, dat wil zeggen dat ze zelf donor-cellen zijn, en de kosten voor het verplaatsen van goederen naar dezelfde cellen natuurlijk gelijk zijn aan 0. We moeten een waarde voor de constante vinden , waarbij het altijd voordelig zou zijn om de resten van container 1 naar container 2 te verplaatsen. Door de waarden in te vullen en in de eerder genoemde ongelijkheid krijgen we:

hieruit volgt

Door de waarden van de gemiddelde tijd voor het uitvoeren van elementaire bewerkingen in de bovenstaande formule in te vullen, krijgen we

De tweede manier om de waarde te berekenen . Laten we een situatie bekijken waarin er donor-cellen zijn van waaruit goederen naar container 1 zullen worden verplaatst. Laten we – de afstand van de donor-cel naar container 1 zijn. Er is ook container 2, waarin al goederen aanwezig zijn, en waarvan het volume toestaat dat de resten van alle cellen worden opgeslagen. Voor de eenvoud nemen we aan dat het volume van de goederen die van donor-cellen naar container 1 worden verplaatst gelijk is aan . We moeten een waarde voor de constante vinden , waarbij het altijd voordeliger zou zijn om alle resten van cellen in container 2 op te slaan dan deze in verschillende containers te plaatsen:

Door de ongelijkheid te transformeren krijgen we

Om de waarde van de grootheid te 'versterken', nemen we aan dat = 0. Het gemiddelde aantal cellen dat meestal betrokken is bij de procedure voor het samenpersen van resten in het magazijn is gelijk aan 10. Door de bekende waarden in te vullen, hebben we de volgende waarde voor de constante We nemen de grootste waarde, berekend voor elke variant, dit zal de waarde van de grootheid zijn

voor de gegeven magazijnparameters. Laten we nu ter afsluiting de formule voor het berekenen van de totale kosten noteren voor een bepaalde acceptabele oplossing . :

Nu, na al het titanelijke werk om de invoergegevens te transformeren, kunnen we zeggen dat alle invoergegevens omgevormd zijn naar de juiste vorm en klaar zijn voor gebruik in het optimalisatie-algoritme.

Conclusie

In de praktijk wordt de arbeidsintensiteit en het belang van de fase van voorbereiding en transformatie van invoergegevens voor het algoritme vaak onderschat. In dit artikel hebben we speciaal veel aandacht besteed aan deze fase om te laten zien dat alleen goed en slim voorbereide invoergegevens de door het algoritme berekende oplossingen echt waardevol kunnen maken voor de klant. Ja, er zijn veel formules afgeleid, maar we hebben je al gewaarschuwd voordat het kwam 🙂

In het volgende artikel zullen we eindelijk komen tot waar de vorige 2 publicaties voor bedoeld waren – het algoritme voor discrete optimalisatie.

Het artikel is voorbereid door
Roman Shangin, programmeur van de projectafdeling,
bedrijf Eerste Bit, Chelyabinsk

Bron: habr.com