În acest articol vă vom spune cum am rezolvat problema lipsei de celule libere într-un depozit și dezvoltarea unui algoritm de optimizare discret pentru a rezolva o astfel de problemă. Să vorbim despre modul în care am „construit” modelul matematic al problemei de optimizare și despre dificultățile pe care le-am întâlnit în mod neașteptat la procesarea datelor de intrare pentru algoritm.
Dacă sunteți interesat de aplicațiile matematicii în afaceri și nu vă este frică de transformările identitare rigide ale formulelor la nivelul clasei a V-a, atunci bun venit la pisica!
Articolul va fi util celor care implementează WMS-sisteme, lucrări în industria de depozitare sau logistică de producție, precum și programatori care sunt interesați de aplicații ale matematicii în afaceri și optimizarea proceselor într-o întreprindere.
Parte introductivă
Această publicație continuă seria articolelor în care împărtășim experiența noastră de succes în implementarea algoritmilor de optimizare în procesele din depozit.
В descrie specificul depozitului în care am implementat WMS-sistem și explică, de asemenea, de ce a trebuit să rezolvăm problema grupării loturilor de mărfuri rămase în timpul implementării WMS-sisteme și cum am făcut-o.
Când am terminat de scris articolul despre algoritmii de optimizare, sa dovedit a fi foarte mare, așa că am decis să împărțim materialul acumulat în 2 părți:
- În prima parte (acest articol) vom vorbi despre modul în care am „construit” modelul matematic al problemei și despre marile dificultăți pe care le-am întâlnit în mod neașteptat la procesarea și transformarea datelor de intrare pentru algoritm.
- În a doua parte vom analiza în detaliu implementarea algoritmului în limbaj C ++, vom efectua un experiment de calcul și vom rezuma experiența pe care am dobândit-o în timpul implementării unor astfel de „tehnologii inteligente” în procesele de afaceri ale clientului.
Cum să citești un articol. Dacă citiți articolul anterior, puteți accesa imediat capitolul „Prezentare generală a soluțiilor existente”; dacă nu, atunci descrierea problemei care se rezolvă este în spoilerul de mai jos.
Descrierea problemei care se rezolva la depozitul clientului
Blocaj în procese
În 2018, am finalizat un proiect de implementat WMS-sisteme la depozitul „Casa de comerț „LD” din Chelyabinsk. Am implementat produsul „1C-Logistics: Warehouse Management 3” pentru 20 de locuri de muncă: operatori WMS, depozitari, conducători de stivuitoare. Depozitul mediu este de aproximativ 4 mii m2, numărul de celule este de 5000 și numărul de SKU este de 4500. Depozitul stochează robinete cu bilă de producție proprie de diferite dimensiuni de la 1 kg la 400 kg. Inventarul din depozit este stocat în loturi, deoarece este necesară selectarea mărfurilor conform FIFO.
În timpul proiectării schemelor de automatizare a proceselor de depozitare, ne-am confruntat cu problema existentă a stocării neoptimale a stocurilor. Specificul depozitării și așezării macaralelor este de așa natură încât o celulă de depozitare poate conține doar articole dintr-un singur lot (vezi Fig. 1). Produsele ajung zilnic la depozit și fiecare sosire este un lot separat. În total, ca urmare a 1 lună de funcționare a depozitului, sunt create 30 de loturi separate, în ciuda faptului că fiecare ar trebui să fie stocat într-o celulă separată. Produsele sunt adesea selectate nu în paleți întregi, ci în bucăți și, ca urmare, în zona de selecție a piesei din multe celule se observă următoarea imagine: într-o celulă cu un volum mai mare de 1 m3 există mai multe bucăți de macarale care ocupă mai puțin de 5-10% din volumul celular.
Fig 1. Fotografia mai multor piese dintr-o celulă
Este clar că capacitatea de stocare nu este utilizată în mod optim. Pentru a-mi imagina amploarea dezastrului, pot da cifre: în medie, există de la 1 la 3 de celule de astfel de celule cu un volum mai mare de 100 m300 cu solduri „minuscule” în diferite perioade de funcționare a depozitului. Deoarece depozitul este relativ mic, în timpul sezonului aglomerat al depozitului, acest factor devine un „gât de sticlă” și încetinește foarte mult procesele depozitului de acceptare și expediere.
Idee de rezolvare a problemei
A apărut o idee: loturile de resturi cu datele cele mai apropiate ar trebui reduse la un singur lot, iar astfel de resturi cu un lot unificat trebuie așezate compact împreună într-o singură celulă sau în mai multe, dacă nu există suficient spațiu într-una pentru a găzdui întreaga cantitate de resturi. Un exemplu de astfel de „compresie” este prezentat în Figura 2.
Fig.2. Schema de comprimare a reziduurilor din celule
Acest lucru vă permite să reduceți semnificativ spațiul de depozitare ocupat care va fi utilizat pentru plasarea de bunuri noi. Într-o situație în care capacitatea depozitului este supraîncărcată, o astfel de măsură este extrem de necesară, altfel este posibil să nu existe suficient spațiu liber pentru a găzdui mărfuri noi, ceea ce va duce la oprirea proceselor de plasare și reaprovizionare a depozitului și, în consecință, până la oprirea acceptării și expedierii. Anterior, înainte de implementarea sistemului WMS, o astfel de operație era efectuată manual, ceea ce era ineficient, deoarece procesul de căutare a echilibrelor adecvate în celule era destul de lung. Acum, odată cu introducerea unui sistem WMS, am decis să automatizăm procesul, să-l accelerăm și să-l facem inteligent.
Procesul de rezolvare a unei astfel de probleme este împărțit în 2 etape:
- la prima etapă găsim grupuri de loturi apropiate de data compresiei (dedicate acestei sarcini );
- în a doua etapă, pentru fiecare grup de loturi calculăm cea mai compactă plasare a mărfurilor rămase în celule.
În articolul de față ne vom concentra pe a doua etapă a algoritmului.
Revizuirea soluțiilor existente
Înainte de a trece la descrierea algoritmilor pe care i-am dezvoltat, merită să facem o scurtă prezentare generală a sistemelor deja existente pe piață. WMS, care implementează o funcționalitate optimă de compresie similară.
În primul rând, este necesar să rețineți produsul „1C: Enterprise 8. WMS Logistics. Managementul depozitului 4", care este deținut și replicat de 1C și aparține celei de-a patra generații WMS-sisteme dezvoltate de AXELOT. Acest sistem revendică funcționalitatea de compresie, care este concepută pentru a uni resturile de produse disparate într-o singură celulă comună. Este de menționat că funcționalitatea de compresie într-un astfel de sistem include și alte posibilități, de exemplu, corectarea plasării bunurilor în celule în funcție de clasele lor ABC, dar nu ne vom opri asupra lor.
Dacă analizați codul sistemului 1C: Enterprise 8. WMS Logistics. Managementul depozitului 4" (care este deschis în această parte a funcționalității), putem concluziona următoarele. Algoritmul de compresie reziduală implementează o logică liniară destul de primitivă și nu se poate vorbi despre nicio compresie „optimă”. Desigur, nu prevede gruparea partidelor. Mai mulți clienți care aveau implementat un astfel de sistem s-au plâns de rezultatele planificării compresiei. De exemplu, adesea în practică în timpul compresiei a apărut următoarea situație: 100 buc. Este planificată mutarea mărfurilor rămase dintr-o celulă în altă celulă, unde se află 1 bucată. bunuri, deși este optim din punct de vedere al consumului de timp să se facă invers.
De asemenea, funcționalitatea comprimării mărfurilor rămase în celule este declarată în multe țări străine. WMS-sisteme, dar, din păcate, nu avem un feedback real cu privire la eficacitatea algoritmilor (acesta este un secret comercial), cu atât mai puțin o idee despre profunzimea logicii lor (software-ul proprietar closed-source), așa că nu putem judeca.
Căutați un model matematic al problemei
Pentru a proiecta algoritmi de înaltă calitate pentru rezolvarea unei probleme, este mai întâi necesar să formulăm clar această problemă matematic, ceea ce vom face.
Sunt multe celule , care conţin resturile unor bunuri. În cele ce urmează, vom numi astfel de celule celule donatoare. Să notăm volumul bunurilor din celulă $.
Este important să spunem că un singur produs dintr-un lot sau mai multe loturi combinate anterior într-un grup (citiți: ), care se datorează specificului depozitării și depozitării mărfurilor. Produse diferite sau grupuri diferite de loturi ar trebui să execute propria lor procedură de compresie separată.
Sunt multe celule , în care pot fi plasate eventual reziduuri din celulele donatoare. Vom numi în continuare astfel de celule celule container. Acestea pot fi fie celule libere din depozit, fie celule donatoare dintr-o varietate . Întotdeauna din belșug este un subset .
Pentru fiecare celulă din multi Au fost stabilite restricții de capacitate , măsurată în dm3. Un dm3 este un cub cu laturile de 10 cm.Produsele depozitate in depozit sunt destul de mari, asa ca in acest caz o astfel de discretizare este destul de suficienta.
Având în vedere o matrice a celor mai scurte distanțe în metri între fiecare pereche de celule Unde и aparțin unor seturi и respectiv.
Să notăm „costurile” de mutare a mărfurilor din celulă într-o celulă . Să notăm „costurile” ale alegerii unui container pentru a muta în ea reziduurile din alte celule. Cum exact și în ce unități de măsură vor fi calculate valorile и vom lua în considerare în continuare (a se vedea secțiunea de pregătire a datelor de intrare), deocamdată este suficient să spunem că astfel de valori vor fi direct proporționale cu valorile и respectiv.
Să notăm prin o variabilă care ia valoarea 1 dacă restul provine din celulă mutat în container , iar 0 în caz contrar. Să notăm prin o variabilă care ia valoarea 1 dacă containerul conține bunurile rămase, iar 0 în caz contrar.
Sarcina este prezentată după cum urmează: trebuie să găsești atât de multe containere și astfel „atașează” celulele donatoare la celulele container pentru a minimiza funcția
sub restricții
În total, atunci când calculăm soluția problemei, ne străduim să:
- în primul rând, pentru a economisi capacitatea de stocare;
- în al doilea rând, pentru a economisi timpul depozitarilor.
Ultima restricție înseamnă că nu putem muta mărfurile într-un container pe care nu l-am ales și, prin urmare, nu am „achitat costuri” pentru alegerea acestuia. Această restricție înseamnă, de asemenea, că volumul de mărfuri mutate din celule în container nu trebuie să depășească capacitatea containerului. Prin rezolvarea unei probleme ne referim la un set de containere și metode pentru atașarea 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: и (vom vorbi despre diferențele dintre sarcini mai târziu). Merită spus că în literatura de specialitate, formularea acestor două probleme de optimizare este formulată în ceea ce privește amplasarea întreprinderilor pe teren, de unde și denumirea de „Locația instalației”. În cea mai mare parte, acesta este un tribut adus tradiției, deoarece pentru prima dată nevoia de a rezolva astfel de probleme combinatorii a venit din domeniul logisticii, mai ales din sectorul militar-industrial în anii 50 ai secolului trecut. În ceea ce privește locația întreprinderii, astfel de sarcini sunt formulate după cum urmează:
- Există un număr finit de orașe în care este posibil să se găsească întreprinderi de producție (denumite în continuare orașe de producție). Pentru fiecare oraș producator sunt specificate costurile de deschidere a unei întreprinderi în acesta, precum și o limitare a capacității de producție a întreprinderii deschise în acesta.
- Există un set finit de orașe în care se află de fapt clienții (denumite în continuare orașe clienți). Pentru fiecare astfel de oraș client este specificat volumul cererii de produse. Pentru simplitate, vom presupune că există un singur produs care este produs de întreprinderi și consumat de clienți.
- Pentru fiecare pereche oraș-producător și oraș-client se precizează valoarea costurilor de transport pentru livrarea volumului necesar de produse de la producător către client.
Trebuie să găsiți în ce orașe să deschideți afaceri și cum să atașați clienți la astfel de afaceri pentru a:
- Costurile totale de deschidere a întreprinderilor și costurile de transport au fost minime;
- Volumul cererii de la clienții alocați oricărei întreprinderi deschise nu a depășit capacitatea de producție a acelei întreprinderi.
Acum, merită menționată singura diferență între aceste două probleme clasice:
- Problemă de amplasare a instalației cu o singură sursă – clientul este alimentat dintr-o singură unitate deschisă;
- Problemă de locație a instalației cu capacități multi-surse – clientul poate fi alimentat din mai multe unități deschise în același timp.
O astfel de diferență între cele două probleme este nesemnificativă la prima vedere, dar, de fapt, duce la o structură combinatorie complet diferită a unor astfel de probleme și, în consecință, la algoritmi complet diferiți pentru rezolvarea lor. Diferențele dintre sarcini sunt demonstrate în figura de mai jos.
Fig.3. a) Problemă de amplasare a instalației cu capacități multi-surse
Fig.3. b) Problemă de amplasare a instalației cu o singură sursă
Ambele sarcini -dificil, adică nu există un algoritm exact care să rezolve o astfel de problemă într-un polinom de timp în dimensiunea datelor de intrare. Cu cuvinte mai simple, toți algoritmii exacti pentru rezolvarea unei probleme vor funcționa în timp exponențial, deși poate mai rapid decât o căutare completă de opțiuni. Din moment ce sarcina -dificil, atunci vom lua în considerare doar euristici aproximative, adică algoritmi care vor calcula constant soluții foarte apropiate de optim și vor funcționa destul de repede. Dacă sunteți interesat de o astfel de sarcină, puteți găsi o prezentare generală bună în rusă aici.
Dacă trecem la terminologia problemei noastre de compresie optimă a bunurilor în celule, atunci:
- orașele client sunt celule donatoare cu bunurile rămase,
- orașe producătoare – celule container , în care ar trebui să fie plasate resturile din alte celule,
- costuri de transport - costuri de timp depozitar să mute volumul de mărfuri din celula donatoare într-o celulă container ;
- costuri de deschidere a unei afaceri - costuri de alegere a unui container , egal cu volumul celulei container , înmulțit cu un anumit coeficient pentru salvarea volumelor libere (valoarea coeficientului este întotdeauna > 1) (vezi secțiunea de pregătire a datelor de intrare).
După ce s-a trasat analogia cu soluțiile clasice binecunoscute ale problemei, este necesar să se răspundă la o întrebare importantă de care depinde alegerea arhitecturii algoritmului de soluție: mutarea resturilor din celula donatoare este posibilă doar la una. și un singur container (Single-Source), sau este posibil să mutați resturile în mai multe celule container (Multi-Source)?
Este de remarcat faptul că în practică au loc ambele formulări ale problemei. Vă prezentăm mai jos toate argumentele pro și contra pentru fiecare astfel de setare:
| Varianta cu probleme | Avantajele opțiunii | Contra opțiunii |
|---|---|---|
| Singura sursa | Operațiuni de circulație a mărfurilor calculate folosind această variantă a problemei:
|
|
| Multi-Sursă | Compresiunile calculate folosind această versiune a problemei sunt de obicei cu 10-15% mai compacte în comparație cu compresiile calculate folosind opțiunea „Single-Source”. Dar observăm, de asemenea, că cu cât numărul de reziduuri din celulele donatoare este mai mic, cu atât diferența de compactitate este mai mică. | Operațiuni de circulație a mărfurilor calculate folosind această variantă a problemei:
|
Tabelul 1. Avantaje și dezavantaje ale opțiunilor cu sursă unică și surse multiple.
Întrucât opțiunea Single-Source are mai multe avantaje și, de asemenea, ținând cont de faptul că, cu cât este mai mic numărul de reziduuri din celulele donor, cu atât este mai mică diferența de gradul de compactare a compresiei calculată pentru ambele variante ale problemei, alegerea noastră a căzut pe opţiunea Single-Surse.Sursă.
Merită spus că are loc și soluția la opțiunea Multi-Source. Există un număr mare de algoritmi eficienți pentru rezolvarea acesteia, dintre care majoritatea se reduc la rezolvarea unui număr de probleme de transport. Există, de asemenea, nu doar algoritmi eficienți, ci și alții eleganti, de exemplu,
Pregătirea datelor de intrare
Înainte de a începe să analizăm și să dezvoltăm un algoritm pentru a rezolva o problemă, este necesar să decidem ce date și sub ce formă le vom alimenta ca intrare. Nu există probleme cu volumul mărfurilor rămase în celulele donatoare și capacitatea celulelor containerului, deoarece acest lucru este banal - astfel de cantități vor fi măsurate în m3, dar cu costurile utilizării unei celule container și matricea costurilor de mutare, nu totul este atât de simplu!
Să ne uităm mai întâi la calcul costurile de mutare a mărfurilor de la celula donatoare la celula container. În primul rând, este necesar să decidem în ce unități de măsură vom calcula costurile de mișcare. Cele mai evidente două opțiuni sunt metrii și secundele. Nu are sens să calculezi costurile de călătorie în contoare „pure”. Să arătăm asta cu un exemplu. Lasă celula situat pe primul nivel, celula îndepărtat la 30 de metri și situat pe al doilea nivel:
- Mutarea de la в mai scump decât mutarea din в , deoarece coborârea de pe al doilea nivel (1,5-2 metri de podea) este mai ușoară decât urcarea pe al doilea, deși distanța va fi aceeași;
- Mută 1 buc. bunuri din celulă в Va fi mai ușor decât mutarea a 10 bucăți. același produs, deși distanța va fi aceeași.
Este mai bine să luați în considerare costurile de mutare în câteva secunde, deoarece acest lucru vă permite să luați în considerare atât diferența de niveluri, cât și diferența dintre cantitatea de mărfuri mutate. Pentru a ține cont de costul mișcării în secunde, trebuie să descompunăm operația de mișcare în componente elementare și să luăm măsurători de timp pentru execuția fiecărei componente elementare.
Lăsați din celulă mișcări PC. mărfuri în container . lăsa – viteza medie de deplasare a unui lucrător în depozit, măsurată în m/sec. Lăsa и – vitezele medii ale operațiunilor unice luate și, respectiv, puse pentru un volum de mărfuri egal cu 4 dm3 (volumul mediu pe care un angajat îl ia la un moment dat într-un depozit atunci când efectuează operațiuni). Lăsa и înălțimea celulelor din care se efectuează, respectiv, operațiunile de preluare și de punere. De exemplu, înălțimea medie a primului nivel (etaj) este de 1 m, al doilea nivel este de 2 m etc. Apoi formula pentru calcularea timpului total pentru a finaliza o operație de mutare este Următorul:
În tabelul 2 sunt prezentate statistici privind timpul de execuție a fiecărei operațiuni elementare, colectate de angajații depozitului, ținând cont de specificul mărfurilor depozitate.
| numele operațiunii | Обозначение | Rău |
|---|---|---|
| Viteza medie a unui muncitor care se deplasează prin depozit | |
1,5 m/s |
| Viteza medie a unei operații de pus (pentru un volum de produs de 4 dm3) | |
2,4 sec |
Tabelul 2. Timp mediu pentru finalizarea operațiunilor din depozit
Am decis cu privire la metoda de calcul a costurilor de mutare. Acum trebuie să ne dăm seama cum să calculăm costurile pentru alegerea unei celule container. Totul aici este mult, mult mai complicat decât cu costurile de mutare, deoarece:
- în primul rând, costurile ar trebui să fie direct dependente de volumul celulei - același volum de reziduuri transferate de la celulele donatoare este mai bine plasat într-un recipient cu un volum mai mic decât într-un container mare, cu condiția ca un astfel de volum să se potrivească complet în ambele containere . Astfel, prin reducerea la minimum a costurilor totale de selectare a containerelor, ne străduim să economisim „scara” capacitate de depozitare gratuită în zona de selecție pentru a efectua operațiunile ulterioare de plasare a mărfurilor în celule. Figura 4 demonstrează opțiunile de transfer al reziduurilor în containere mari și mici și consecințele acestor opțiuni de transfer în operațiunile ulterioare ale depozitului.
- în al doilea rând, deoarece în rezolvarea problemei inițiale trebuie să minimizăm exact costurile totale, iar aceasta este suma atât a costurilor de mutare, cât și a costurilor de alegere a containerelor, atunci volumele celulelor în metri cubi trebuie să fie cumva legate de secunde, ceea ce este departe de a fi banal.
Orez. 4. Opțiuni pentru mutarea resturilor în containere de diferite capacități.
Figura 4 arată cu roșu volumul resturilor care nu mai încape în container la a doua etapă de plasare a mărfurilor ulterioare.
Va ajuta să legați metri cubi de costuri pentru alegerea unui container cu secundele de costuri pentru mutarea următoarelor cerințe pentru soluții calculate la problemă:
- Este necesar ca soldurile din containerul donator să fie mutate în containerul în orice caz dacă acest lucru reduce numărul total de containere care conțin produsul.
- Este necesar să se mențină un echilibru între volumul containerelor și timpul petrecut în deplasare: de exemplu, dacă într-o nouă soluție a unei probleme în comparație cu soluția anterioară, câștigul în volum este mare, dar pierderea în timp este mică. , atunci este necesar să alegeți o nouă opțiune.
Să începem cu ultima cerință. Pentru a clarifica cuvântul ambiguu „echilibru”, am efectuat un sondaj asupra angajaților din depozit pentru a afla următoarele. Să existe o celulă container de volum , căruia i se atribuie mișcarea mărfurilor rămase din celulele donatoare și timpul total al acestei mișcări este egal cu . Să existe mai multe opțiuni alternative pentru a plasa aceeași cantitate de bunuri din aceleași celule donatoare în alte containere, unde fiecare plasare are propriile estimări Unde < и Unde >.
Se pune întrebarea: care este câștigul minim în volum acceptabil, pentru o valoare dată de pierdere de timp ? Să explicăm cu un exemplu. Inițial, rămășițele trebuiau să fie plasate într-un container cu un volum de 1000 dm3 (1 m3) și timpul de transfer a fost de 70 de secunde. Există o opțiune de a plasa reziduurile într-un alt recipient cu un volum de 500 dm3 și un timp de 130 de secunde. Întrebare: suntem pregătiți să petrecem încă 60 de secunde din timpul depozitarului pentru mutarea mărfurilor pentru a economisi 500 dm3 de volum liber? Pe baza rezultatelor unui sondaj asupra angajaților din depozit, a fost întocmită următoarea diagramă.
Orez. 5. Diagrama dependenței economiilor minime admisibile de volum de creșterea diferenței de timp de funcționare
Adică, dacă costurile suplimentare de timp sunt de 40 de secunde, atunci suntem gata să le cheltuim doar atunci când câștigul în volum este de cel puțin 500 dm3. În ciuda faptului că există o ușoară neliniaritate în dependență, pentru simplitatea calculelor ulterioare vom presupune că dependența dintre mărimi este liniară și este descrisă de inegalitatea
În figura de mai jos, luăm în considerare următoarele metode de plasare a mărfurilor în containere.
Orez. 6. Opțiunea (a): 2 recipiente, volum total 400 dm3, timp total 150 sec.
Orez. 6. Opțiunea (b): 2 recipiente, volum total 600 dm3, timp total 190 sec.
Orez. 6. Opțiunea (c): 1 recipient, volum total 400 dm3, timp total 200 sec.
Opțiunea (a) pentru alegerea recipientelor este mai de preferat decât varianta inițială, deoarece inegalitatea este valabilă: (800-400)/10>=150-120, ceea ce implică 40 >= 30. Opțiunea (b) este mai puțin preferată decât originalul opțiunea , întrucât inegalitatea nu se ține: (800-600)/10>=190-150 ceea ce implică 20 >= 40. Dar opțiunea (c) nu se încadrează într-o astfel de logică! Să luăm în considerare această opțiune mai detaliat. Pe de o parte, inegalitatea (800-400)/10>=200-120, ceea ce înseamnă că inegalitatea 40 >= 80 nu este satisfăcută, ceea ce sugerează 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 numai că reducem volumul total ocupat, ci și numărul de celule ocupate, care este prima dintre cele două cerințe importante pentru soluții calculabile la problemele enumerate mai sus. Evident, pentru ca această cerință să înceapă să fie îndeplinită, este necesar să adăugați o constantă pozitivă în partea stângă a inegalității. , iar o astfel de constantă trebuie adăugată numai atunci când numărul de containere scade. Să vă reamintim că este o variabilă egală cu 1 când containerul selectat și 0 când container nu a fost ales. Să notăm – multe recipiente în soluția inițială și – multe containere în noua soluție. În general, noua inegalitate va arăta astfel:
Transformând inegalitatea de mai sus, obținem
Pe baza acestui lucru, avem o formulă pentru calcularea costului total ceva solutie la problema:
Dar acum se pune întrebarea: ce valoare ar trebui sa aiba o astfel de constanta? ? Evident, valoarea sa trebuie să fie suficient de mare pentru ca prima cerință pentru soluții la problemă să fie întotdeauna îndeplinită. Puteți, desigur, să luați valoarea constantei egală cu 103 sau 106, dar aș dori să evit astfel de „numere magice”. Dacă luăm în considerare specificul efectuării operațiunilor de depozit, putem calcula mai multe estimări numerice bine întemeiate ale valorii unei astfel de constante.
lăsa – distanța maximă dintre celulele depozitului unei zone ABC, egală în cazul nostru cu 100 m. Fie – volumul maxim al unei celule container dintr-un depozit, egal în cazul nostru cu 1000 dm3.
Prima modalitate de a calcula valoarea . Să luăm în considerare o situație în care există 2 containere pe primul nivel, în care bunurile sunt deja situate fizic, adică ele însele sunt celule donatoare, iar costul mutarii mărfurilor în aceleași celule este în mod natural egal cu 0. este necesar să se găsească o astfel de valoare pentru constantă , în care ar fi avantajos să se mute întotdeauna resturile din recipientul 1 în recipientul 2. Înlocuirea valorilor и În inegalitatea dată mai sus obținem:
din care decurge
Înlocuind valorile timpului mediu pentru efectuarea operațiilor elementare în formula de mai sus obținem
A doua modalitate de a calcula valoarea . Să luăm în considerare o situație în care există celule donatoare din care se preconizează mutarea mărfurilor în container 1. Să notăm – distanta fata de celula donatoare la containerul 1. Există, de asemenea, containerul 2, care conține deja mărfuri și al cărui volum vă permite să găzduiți restul tuturor celule. Pentru simplitate, vom presupune că volumul de mărfuri mutate de la celulele donatoare la containere este același și egal cu . Este necesar să se găsească o astfel de valoare a constantei , în care plasarea tuturor resturilor din celulele în containerul 2 ar fi întotdeauna mai profitabil decât plasarea lor în containere diferite:
Transformând inegalitatea pe care o obținem
Pentru a „întări” valoarea cantității , să presupunem că = 0. Numărul mediu de celule implicate de obicei în procedura de comprimare a soldurilor de depozit este 10. Înlocuind valorile cunoscute ale cantităților, avem următoarea valoare a constantei
Luăm cea mai mare valoare calculată pentru fiecare opțiune, aceasta va fi valoarea cantității pentru parametrii de depozit dați. Acum, pentru a fi complet, să scriem formula pentru calcularea costurilor totale pentru o soluție fezabilă :
Acum, la urma urmei eforturi herculeene Prin transformarea datelor de intrare, putem spune că toate datele de intrare au fost convertite în forma dorită și sunt gata de utilizare în algoritmul de optimizare.
Concluzie
După cum arată practica, complexitatea și importanța etapei de pregătire și transformare a datelor de intrare pentru un algoritm sunt adesea subestimate. În acest articol, am acordat în mod special multă atenție acestei etape pentru a arăta că numai datele de intrare de înaltă calitate și pregătite inteligent pot face deciziile calculate de algoritm cu adevărat valoroase pentru client. Da, au fost multe derivări de formule, dar te-am avertizat chiar înainte de kata :)
În următorul articol vom ajunge în sfârșit la ceea ce au fost destinate cele 2 publicații anterioare - un algoritm de optimizare discret.
Am pregătit articolul
Roman Shangin, programator al departamentului de proiecte,
Compania First Bit, Chelyabinsk
Sursa: www.habr.com