Matematica discretă pentru WMS: algoritmul de comprimare a produselor în celule (partea 1)

În acest articol, vom vorbi despre cum am rezolvat problema lipsei de celule libere în depozit și despre dezvoltarea unui algoritm de optimizare discretă pentru a aborda această problemă. Vă vom spune cum am „construit” modelul matematic al problemei de optimizare și despre dificultățile neașteptate pe care le-am întâmpinat în procesarea datelor de intrare pentru algoritm.

Dacă sunteți interesat de aplicațiile matematicii în afaceri și nu vă temeți de transformări identice complexe ale formulelor la nivelul clasei a V-a, atunci bun venit sub rând!

Articolul va fi util celor care implementează sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.Partea introductivă

Această publicație continuă seria de articole în care ne împărtășim experiența de succes în implementarea algoritmilor de optimizare în procesele de depozit.

Este descrisă specificitatea depozitului în care am implementat

În articolul anterior -sistemul, iar de asemenea, se discută de ce a fost necesar să abordăm problema clusterizării loturilor de stocuri în cadrul implementării sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.-sistemului și cum am realizat acest lucru. sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.Când am terminat de scris articolul despre algoritmii de optimizare, a rezultat unul foarte extins, astfel încât materialul acumulat a fost împărțit în 2 părți:

În prima parte (acest articol) vom explica cum am „construit” modelul matematic al problemei și despre dificultățile importante pe care le-am întâmpinat în procesarea și transformarea datelor de intrare pentru algoritm.

• În a doua parte, vom examina în detaliu implementarea algoritmului în limbajul
• , vom efectua un experiment computațional și vom rezuma experiența pe care am obținut-o în timpul implementării acestor „tehnologii inteligente” în procesele de afaceri ale clientului. C++Cum să citiți articolul. Dacă ați citit articolul anterior, puteți trece direct la capitolul „Prezentarea soluțiilor existente”, dacă nu, descrierea problemei abordate este în spoilerul de mai jos.

Descrierea problemei abordate în depozitul clientului

Punctul critic în procesele

În 2018, am realizat un proiect de implementare

În 2018 am realizat un proiect de implementare sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.-sistemele la depozitul «Casa de Comerț «LD» din orașul Chelyabinsk. Am implementat produsul «1C-Logistica: Managementul depozitului 3» pe 20 de puncte de lucru: operatori, depozitari, șoferi de stivuitoare. sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii., depozitar. Depozitul are o dimensiune medie de aproximativ 4.000 m2, cu 5.000 de celule și un număr de SKU de 4.500. În depozit sunt păstrate clape sferice de producție proprie, de diferite dimensiuni, între 1 kg și 400 kg. Stocurile sunt păstrate pe loturi, deoarece există necesitatea de a selecta produsele conform principiului FIFO.

În timpul proiectării schemelor de automatizare a proceselor de depozitare, ne-am confruntat cu problema existentă a stocării neoptime. Specificitatea stocării și aranjării clapelor este că într-o celulă de depozitare poate fi păstrat doar un singur tip de lot (vezi fig. 1). Produsele sosesc în depozit zilnic, iar fiecare sosire reprezintă un lot separat. Astfel, în urma unei luni de activitate a depozitului, se formează 30 de loturi separate, fiecare fiind necesar să fie stocată în celule separate. Produsele sunt adesea selectate nu pe palete întregi, ci bucată cu bucată, iar în zona de selecție frecventă se observă adesea o situație precum: într-o celulă cu un volum de peste 1m3 se află câteva unități de cliape, care ocupă mai puțin de 5-10% din volumul celulei.

Fig. 1. Fotografie cu câteva unități într-o celulă

Se observă o utilizare neoptimizată a capacităților de depozitare. Pentru a ilustra amploarea problemei, pot oferi cifre: în medie, există între 100 și 300 de celule cu un volum de peste 1m3, având «rezerve minuscule» în diferite perioade de funcționare a depozitului. Deoarece depozitul este relativ mic, în sezoanele aglomerate, acest factor devine un „gât de sticlă” care încetinește semnificativ procesele de primire și expediere.

Ideea soluționării problemei

A apărut ideea: loturile de rezerve cu date de expirare apropiate să fie consolidate într-un singur lot unificat, iar aceste rezerve cu lot uniformizat să fie plasate compact împreună într-o celulă sau în mai multe, dacă într-una nu este suficient loc pentru a plasa întreaga cantitate de rezerve. Un exemplu de astfel de „compactare” este ilustrat în figura 2.

Fig. 2. Schița compactării rezervei în celule

Aceasta permite reducerea semnificativă a spațiului de depozitare ocupat, care va fi utilizat pentru noul stoc de produse. În situația unei suprasarcini a capacităților de depozitare, această măsură devine extrem de necesară, altfel spațiul liber pentru stocarea de noi produse poate pur și simplu să nu fie suficient, ceea ce va duce la blocarea proceselor de stocare și alimentare și, prin urmare, la blocarea primirii și livrării. Înainte de implementarea sistemului WMS, această operațiune era efectuată manual, ceea ce era ineficient, deoarece procesul de căutare a stocurilor corespunzătoare în celule era destul de lung. Acum, cu implementarea sistemului WMS, am decis să automatizăm procesul, să-l accelerăm și să-l facem mai inteligent.

Procesul de rezolvare a acestei sarcini este împărțit în 2 etape:

• în prima etapă, găsim grupuri de loturi apropiate ca dată pentru comprimare (această sarcină este dedicată) articolul anterior);
• în a doua etapă, pentru fiecare grup de loturi, calculăm aranjamentul cel mai compact al stocurilor în celule.

În acest articol ne vom concentra asupra celei de-a doua etape a algoritmului.

Prezentarea soluțiilor existente

Înainte de a trece la descrierea algoritmilor pe care i-am dezvoltat, merită să facem o scurtă prezentare a sistemelor deja existente pe piață sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii., care implementează o astfel de funcționalitate de comprimare optimă.

În primul rând, trebuie menționat produsul „1C: Întreprindere 8. WMS Logistică. Managementul depozitului 4”, care aparține și este distribuit de firma 1C și face parte din a patra generație sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.-sisteme, dezvoltate de compania AXELOT. În acest sistem este declarat funcționalitatea de comprimare, care este destinată unirii stocurilor disparate de produse într-o celulă comună. Trebuie menționat că funcționalitatea de comprimare dintr-un astfel de sistem include și alte posibilități, de exemplu, corectarea plasării produselor în celule conform claselor lor ABC, dar nu ne vom opri asupra lor.

Dacă analizăm codul sistemului „1C: Întreprindere 8. WMS Logistică. Managementul depozitului 4” (care, în această parte a funcționalității, este deschis), putem concluziona următoarele. Algoritmul de compresie a stocurilor implementează o logică liniară destul de primitivă și nu poate fi vorba de o compresie „optimă”. Firește, acesta nu preconizează clusterizarea loturilor. Mai mulți clienți care au implementat un astfel de sistem s-au plâns de rezultatele planificării compresiei. De exemplu, în practică, adesea se întâmpla ca 100 de unități de stoc dintr-un loc să fie planificate pentru a fi mutate într-un alt loc unde se află o unitate de produs, deși ar fi fost optim, din punct de vedere al timpului, să se facă invers.

Funcționalitatea de compresie a stocurilor de produse în locuri este, de asemenea, anunțată în multe sisteme WMS, care lucrează în domeniul logisticii de depozit sau de producție, precum și programatorilor care sunt interesați de aplicațiile matematicii în afaceri și de optimizarea proceselor în cadrul întreprinderii.-sisteme străine, dar, din păcate, nu avem recenzii reale despre eficiența funcționării algoritmilor (aceasta fiind un secret comercial), nici informații despre complexitatea logicii acestora (software proprietar cu cod închis), așa că nu putem judeca.

Căutarea unui model matematic al problemei

Pentru a proiecta algoritmi de calitate pentru rezolvarea problemei, este necesar mai întâi să formulăm clar această problemă din punct de vedere matematic, ceea ce vom face.

Există numeroase locuri , în care se află stocurile unor produse. Mai departe, vom numi aceste locuri celule-donatoare. Să notăm volumul produsului aflat în celula $.

Este important de menționat că în procedura de compresie poate participa doar un singur produs dintr-un lot, sau mai multe loturi, unite anterior într-un cluster (citește articolul anterior), ceea ce se datorează specificului depozitării și aranjării produselor. Pentru produse diferite sau pentru diferite clustere de loturi, ar trebui să se lanseze proceduri separate de compresie.

Există numeroase locuri , în care pot fi potențial plasate stocuri din celule-donatoare. Aceste celule le vom numi mai departe celule-contoare. Acestea pot fi atât celule libere din depozit, cât și celule-donatoare din mulțime . Întotdeauna mulțimea este un subset .

Pentru fiecare celulă din mulțime sunt stabilite restricții privind capacitatea , măsurate în dm3. Un dm3 reprezintă un cub cu laturile de 10 cm. Produsele stocate în magazie sunt destul de mari, așa că, în acest caz, o astfel de discretizare este suficientă.

Este dată o matrice a distanțelor minime în metri între fiecare pereche de celule , unde și aparțin mulțimilor și corespunzător.

Să notăm „costurile” pentru mutarea produsului dintr-o celulă în celula . Să notăm „costurile” pentru alegerea containerului pentru a muta în el resturile din alte celule. Cum și în ce unități de măsură vor fi calculate valorile și vom analiza mai departe (vezi secțiunea pregătirea datelor de intrare), acum este suficient să spunem că aceste magnitudini vor fi direct proporționale cu valorile și corespunzător.

Să notăm prin o variabilă care ia valoarea 1 dacă resturile din celulă sunt mutate în container , și 0 în caz contrar. Să notăm prin o variabilă care ia valoarea 1 dacă containerul conține resturi de produs, și 0 în caz contrar.

Problema se formulează astfel: este necesar să găsim o mulțime de containere și astfel „să atașăm” celulele-donatoare la celulele-container, pentru a minimiza funcția

sub restricții

Astfel, în timpul calculării soluției problemei, ne străduim:

• în primul rând, să economisim capacitățile de depozitare;
• în al doilea rând, să economisim timpul lucrătorilor din magazie.

Ultima restricție înseamnă că nu putem muta produsele într-un container pe care nu l-am ales și, prin urmare, nu am „purta costuri” pentru alegerea acestuia. De asemenea, această restricție înseamnă că volumul produselor mutate din celule în container nu trebuie să depășească capacitatea containerului. O soluție a problemei va fi considerată o mulțime de containere și modalitățile de atașare a celulelor-donatoare la containere.

Această formulare a problemei de optimizare nu este nouă și a fost studiată de mulți matematicieni încă de la începutul anilor '80 ai secolului trecut. În literatura străină există 2 probleme de optimizare cu un model matematic adecvat: Problema Localizării Facilității Capacitate de Sursă Unică și Problema Localizării Facilității Capacitate de Sursă Multiple (despre diferențele dintre probleme vom discuta mai departe). Merită menționat că în literatura de specialitate matematică formulările acestor două probleme de optimizare sunt prezentate în termeni de amplasare a unităților de producție, de unde și denumirea „Locația Facilitaților”. În mare parte este o chestiune de tradiție, deoarece pentru prima dată necesitatea de a rezolva astfel de probleme combinatorice a apărut din domeniul logisticii, în cea mai mare parte în industria militaro-economică din anii '50 ai secolului trecut. În termeni de amplasare a unităților de producție, aceste probleme sunt formulate astfel:

• Există un număr finit de orașe unde este posibil să se amplaseze unități de producție (în continuare orașe-producători). Pentru fiecare oraș-producător sunt stabilite costurile de deschidere a unei unități și, de asemenea, restricțiile privind capacitatea de producție a unității deschise.
• Există un număr finit de orașe unde se află de fapt clienții (în continuare orașe-clienți). Pentru fiecare astfel de oraș-client este stabilit volumul cererii pentru produs. Pentru simplificare, vom considera că produsul fabricat de unități și consumat de clienți este unul singur.
• Pentru fiecare pereche oraș-producător și oraș-client este dată valoarea costurilor de transport pentru livrarea volumului necesar de produs de la producător la client.

Este necesar să se determine în ce orașe să se deschidă unități și cum să se aloce clienții acestor unități, astfel încât:

• Costurile totale de deschidere a unităților și costurile de transport să fie minime;
• Volumul cererii clienților alocați unei unități deschise să nu depășească capacitatea de producție a acestei unități.

Acum merită menționat despre singura diferență dintre aceste două probleme clasice:

• Problema Locației Facilitaților Capacitate Unică – clientul este aprovizionat doar dintr-o singură unitate deschisă;
• Problema Locației Facilitaților Capacitate Multi-Sursă – clientul poate fi aprovizionat din mai multe unități deschise simultan.

Această diferență între cele două probleme, la prima vedere, pare nesemnificativă, dar de fapt duce la o structură combinatorică complet diferită a acestor probleme și, drept consecință, la algoritmi complet diferiți pentru rezolvarea lor. Diferența între probleme este demonstrată în desenul de mai jos.

Fig.3. a) Problema Locației Facilitaților Capacitate Multi-Sursă

Fig.3. b) Problema Locației Facilitaților Capacitate Unică

Ambele probleme -dificile, adică nu există un algoritm exact care să rezolve o astfel de problemă în timp polinomial în funcție de dimensiunea datelor de intrare. Cu alte cuvinte, toate algoritmurile exacte pentru rezolvarea problemei vor funcționa într-un timp exponențial, deși poate mai repede decât o abordare exhaustivă. Deoarece problema -dificilă, așa că ne vom concentra doar asupra euristicilor aproximative, adică algoritmi care vor calcula soluții în mod constant, foarte apropiate de cele optime și care vor funcționa destul de repede. Dacă există interes pentru astfel de probleme, atunci aici se poate găsi o bună prezentare în limba română.

Dacă facem paralela cu terminologia problemei noastre de comprimare optimă a bunurilor în celule, atunci:

• orașele-client – sunt celulele-donatoare cu bunuri rămase,
• orașele-producătoare – sunt celulele-container , în care se presupune că se vor plasa bunurile rămase din alte celule,
• costurile de transport – costul timpului de depozitare pentru mutarea volumului de bunuri din celula-donator în celula-container ;
• costurile de deschidere a întreprinderii – costurile pentru alegerea containerului , egale cu volumul celulei-container , înmulțit cu un anumit coeficient de economisire a volumelor libere (valoarea coeficientului este întotdeauna > 1) (vezi secțiunea pregătirea datelor de intrare).

După ce s-a realizat analogia cu problemele clasice cunoscute, este necesar să răspundem la o întrebare importantă, de la care depinde alegerea arhitecturii algoritmului de soluționare: este posibilă mutarea bunurilor rămase din celula-donator doar într-un singur container (Single-Source) sau este posibilă mutarea bunurilor în mai multe celule-container (Multi-Source)?

Merită menționat că, în practică, ambele formulări ale problemei există. Vom enumera toate „avantajele” și „dezavantajele” fiecărei astfel de formulări mai jos:

Tabelul 1. Avantajele și dezavantajele variantelor Single-Source și Multi-Source.

Deoarece numărul avantajelor pentru varianta Single-Source este mai mare și având în vedere faptul că cu cât numărul de stocuri în celulele-donator este mai mic, cu atât diferența în gradul de compactitate a compresiei calculate conform ambelor variante de problemă este mai mică, alegerea noastră a căzut pe varianta Single-Source.

Merită menționat că soluția pentru varianta Multi-Source își găsește locul. Există o mulțime de algoritmi eficienți pentru rezolvarea sa, majoritatea dintre ei reducându-se la soluționarea unor probleme de transport. Există nu doar algoritmi eficienți, ci și eleganți, de exemplu, aici.

Pregătirea datelor de intrare

Înainte de a începe analiza și dezvoltarea algoritmului pentru rezolvarea problemei, trebuie să stabilim ce date și în ce formă le vom oferi ca intrare. Cu volumele de stocuri ale produselor în celulele-donator și capacitatea celulelor-container nu sunt probleme, deoarece acestea sunt triviale – aceste valori vor fi măsurate în m3, dar în ceea ce privește costurile pentru utilizarea celulei-container și matricea costurilor pentru mutare, lucrurile nu sunt atât de simple!

La început, să examinăm calculul costurile de mutare a bunurilor din celula-donator în celula-container. În primul rând, trebuie să stabilim în ce unități de măsură vom calcula costurile de mutare. Două dintre cele mai evidente variante sunt metri și secunde. În metri "curați", calcularea costurilor de mutare nu are sens. Să arătăm acest lucru prin exemplu. Să presupunem că celula este situată la primul nivel, celula este la 30 metri distanță și se află la al doilea nivel:

• Mutarea din în este mai costisitoare decât mutarea din în , deoarece este mai ușor să coboare de la al doilea nivel (1,5-2 metri de la podea) decât să se ridice la al doilea, deși distanța parcursă va fi aceeași;
• A muta 1 buc. de marfă din celula în va fi mai ușor decât a muta 10 buc. din aceeași marfă, deși distanța parcursă va fi aceeași.

Costurile de mutare ar trebui să fie considerate mai bine în secunde, deoarece aceasta permite luarea în considerare a diferențelor de nivel și a diferențelor cantitative de marfă mutată. Pentru a contabiliza costurile de mutare în secunde, trebuie să descompunem operațiunea de mutare în componente elementare și să măsurăm timpul necesar pentru fiecare componentă elementară.

Să presupunem că din celula se mută buc. de marfă în container . Să presupunem că este viteza medie de deplasare a lucrătorului în magazie, măsurată în m/s. Să presupunem că și sunt vitezele medii de execuție pentru operațiunile de luat și pus, respectiv, pentru un volum de marfă egal cu 4 dm³ (volumul mediu pe care un angajat îl ia în 1 singură dată în magazie în timpul desfășurării operațiunilor). Să presupunem că și sunt înălțimile celulelor din care se realizează operațiunile de luat și pus, respectiv. De exemplu, înălțimea medie a primului nivel (podea) este de 1 m, al doilea nivel 2 m etc. Atunci formula pentru calcularea timpului total necesar pentru desfășurarea operațiunii de mutare este următoarea:

În tabelul 2 sunt prezentate statisticile timpului de desfășurare a fiecărei operațiuni elementare, colectate de angajații magazinului, luând în considerare specificul bunurilor păstrate.

Denominația operațiunii	Simbol	Valoare medie
Viteza medie de deplasare a lucrătorului în magazie		1,5 m/s
Viteza medie de desfășurare a unei operațiuni de pus (pentru un volum de marfă de 4 dm³)		2,4 sec

Tabelul 2. Timpul mediu pentru desfășurarea operațiunilor din magazie

Am stabilit modul de calcul al costurilor de mutare. Acum este necesar să aflăm cum să calculăm costurile pentru selectarea celulei-containerAici totul este mult, mult mai complicat decât costurile de mutare, deoarece:

• în primul rând, costurile trebuie să fie în legătură directă cu volumul celulei – același volum de stocuri mutat din celulele-donator este mai bine să fie pus într-un container mai mic decât într-un container mare, atâta vreme cât acest volum încap în ambele containere. Astfel, minimizând costurile totale de alegere a containerelor, ne străduim să economisim capacitățile de depozitare „deficitare” în zona de selecție, pentru a desfășura ulterior operațiunile de plasare a mărfurilor în celule. În figura 4 sunt prezentate opțiunile de mutare a stocurilor în containere mari și mici și consecințele acestor opțiuni de mutare în executarea operațiunilor de depozitare ulterioare.
• în al doilea rând, deoarece în soluția problemei de bază trebuie să minimizăm tocmai costurile totale, adică suma atât a costurilor de mutare, cât și a costurilor de alegere a containerelor, volumul celulelor în metri cubi trebuie cumva corelat cu secunde, ceea ce nu este deloc trivial.

Fig. 4. Opțiunile de mutare a stocurilor în containere cu capacități diferite.

În figura 4, în roșu este reprezentat volumul stocurilor care nu mai încap în container în etapa a doua de plasare a mărfurilor ulterioare.

Pentru a corela metri cubi de costuri pentru alegerea containerului cu secunde de costuri de mutare, următoarele cerințe pentru soluțiile calculate ale problemei vor fi utile:

• Este necesar ca stocurile din celula-donator să fie mutate în celula-container în orice caz, dacă acest lucru reduce numărul total de celule-container în care se află produsul.
• Trebuie respectat un echilibru între volumele containerelor și costurile de timp pentru mutare: de exemplu, dacă în noua variantă a soluției problemei, comparativ cu varianta anterioară, câștigul în volum este mare, iar pierderea în costurile de timp este mică, atunci trebuie aleasă noua variantă.

Să începem cu ultima cerință. Pentru a concretiza cuvântul ambiguu „echilibru”, am realizat un sondaj printre angajații depozitului pentru a determina următoarele. Să presupunem că există o celulă-container cu un volum , în care este planificată mutarea stocurilor din celule-donator și timpul total al acestei mutări este egal cu . Să presupunem că există câteva opțiuni alternative de plasare a aceleași cantități de bunuri din aceleași celule donor în alte containere, unde fiecare plasare are propriile evaluări. , unde < și , unde >.

Se pune întrebarea: care este câștigul minim în volum acceptabil, având în vedere o pierdere dată de timp? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagrama relației dintre economia minimă acceptabilă a volumului și creșterea diferenței de timp de execuție a operațiunii.

Cu alte cuvinte, dacă costurile suplimentare de timp se ridică la 40 de secunde, suntem dispuși să le cheltuim doar atunci când câștigul în volum este de cel puțin 500 dm3. Deși există o mică non-liniaritate în relație, pentru simplificarea calculilor viitoare, vom considera că relația dintre variabile este liniară și este descrisă de inegalitate.

În figura de mai jos, vom analiza următoarele modalități de plasare a bunurilor în containere.

Fig. 6. Opțiunea (a): 2 containere, volum total 400 dm3, timp total 150 sec.

Fig. 6. Opțiunea (b): 2 containere, volum total 600 dm3, timp total 190 sec.

Fig. 6. Opțiunea (c): 1 container, volum total 400 dm3, timp total 200 sec.

Opțiunea (a) de alegere a containerelor este mai preferabilă decât opțiunea inițială, deoarece se îndeplinește inegalitatea: (800-400)/10>=150-120 ceea ce implică 40 >= 30. Opțiunea (b) este mai puțin preferabilă decât opțiunea inițială, deoarece inegalitatea nu se îndeplinește: (800-600)/10>=190-150 ceea ce implică 20 >= 40. Însă opțiunea (c) nu se încadrează în această logică! Să analizăm această opțiune în detaliu. Pe de o parte, inegalitatea (800-400)/10>=200-120, ceea ce înseamnă că inegalitatea 40 >= 80 nu se îndeplinește, ceea ce indică faptul că câștigul în volum nu merită o pierdere atât de mare în timp.

Dar, pe de altă parte, în această opțiune (c) nu doar reducem volumul total ocupat, ci și diminuăm numărul de celule ocupate, ceea ce este primul din cele două cerințe importante pentru soluțiile calculate la problemele enumerate mai sus. Este evident că, pentru ca această cerință să înceapă să fie îndeplinită, trebuie să adăugăm o anumită constantă pozitivă în partea stângă a inegalității. , unde această constantă trebuie adăugată doar atunci când numărul de containere se diminuează. Să ne amintim că — este o variabilă care este egală cu 1 atunci când containerul este ales și 0 când acesta nu este. nu este selectat. Să definim, – un număr mare de containere în soluția inițială și – un număr mare de containere în noua soluție. În forma sa generală, noua inegalitate va arăta astfel:

Transformând inegalitatea de mai sus, obținem

Având în vedere acest lucru, avem formula pentru calcularea costului total unei soluții alternative la problemă:

Dar acum apare întrebarea: ce valoare ar trebui să aibă o astfel de constantă ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Să presupunem că – distanța maximă între celulele depozitului dintr-o zonă ABC, care este în cazul nostru de 100 m. Să presupunem că – volumul maxim al celulei-container din depozit, care este în cazul nostru de 1000 dm3.

Prima metodă de calculare a valorii . Să analizăm o situație în care există 2 containere pe primul nivel, în care se află deja fizic bunuri, adică sunt ele însele celule-donatoare, iar costurile pentru mutarea bunurilor în aceleași celule sunt, evident, egale cu 0. Este necesar să găsim o valoare pentru constantă , pentru care ar fi avantajos să se mute întotdeauna resturile din container 1 în container 2. Înlocuind valorile și în inegalitatea menționată mai sus, obținem:

din care reiese

Înlocuind valorile timpului mediu de execuție a operațiunilor elementare în formula de mai sus, obținem

A doua metodă de calculare a valorii . Să analizăm o situație în care există celule-donatoare din care se plănuiește mutarea bunurilor în container 1. Să denumim – distanța de la celula-donator până la container 1. Există de asemenea un container 2, în care se află deja bunuri și volumul căruia permite să încapă resturile din toate celulele. Pentru simplificare, să presupunem că volumul bunurilor mutate din celulele-donatoare în containere este același și egal cu . Este necesar să găsim o valoare pentru constantă , pentru care plasarea tuturor resturilor din celule în container 2 ar fi întotdeauna mai avantajoasă decât plasarea acestora în diverse containere:

Transformând inegalitatea, obținem

Pentru a "consolida" valoarea lui , vom presupune că = 0. Numărul mediu de celule care participă în mod obișnuit în procedura de comprimare a resturilor în depozit este de 10. Împăcând valorile cunoscute ale mărimilor, obținem următoarea valoare a constantei

Luăm cea mai mare valoare, calculată pentru fiecare variantă, aceasta va fi valoarea mărimii pentru parametrii specificați ai depozitului. Acum, pentru a finaliza, vom scrie formula pentru calcularea costurilor totale pentru o anumită soluție acceptabilă :

Iată acum, după toate eforturile titanice de transformare a datelor de intrare, putem spune că toate datele de intrare au fost transformate în forma necesară și sunt gata pentru utilizare în algoritmul de optimizare.

Concluzie

Așa cum arată practica, munca și importanța etapei de pregătire și transformare a datelor de intrare pentru algoritm sunt adesea subestimate. În acest articol, am dedicat o atenție deosebită acestei etape pentru a arăta că doar datele de intrare pregătite calitativ și cu discernământ pot face ca soluțiile calculate de algoritm să fie cu adevărat valoroase pentru client. Da, au fost multe concluzii de formule, dar v-am avertizat și înainte de asta 🙂

În articolul următor, în sfârșit vom ajunge la ceea ce a fost gândit în ultimele 2 publicații - algoritmul de optimizare discretă.

Articolul a fost pregătit de
Roman Shangin, programator în departamentul de proiecte,
compania Primul Bit, orașul Chelyabinsk

Sursa: habr.com