Matematica discreta per WMS: algoritmo di compressione dei prodotti nelle celle (parte 1)

In questo articolo parleremo di come abbiamo affrontato il problema della mancanza di spazio libero nei magazzini e dello sviluppo di un algoritmo di ottimizzazione discreta per risolvere tale problema. Spiegheremo come abbiamo "costruito" il modello matematico del problema di ottimizzazione e delle difficoltà inaspettate che abbiamo incontrato durante l'elaborazione dei dati di input per l'algoritmo.

Se siete interessati alle applicazioni della matematica nel business e non temete trasformazioni algebriche di livello scolastico, siete i benvenuti sotto il cat!

L'articolo sarà utile a coloro che implementano WMS-sistemi, lavorano nel settore della logistica di magazzino o produttiva, e anche ai programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi aziendali.

Parte introduttiva

Questa pubblicazione continua una serie di articoli in cui condividiamo la nostra esperienza di successo nell'implementazione di algoritmi di ottimizzazione nei processi di magazzino.

In articolo precedente viene descritta la specificità del magazzino in cui è stato implementato il WMS-sistema, e si spiega perché abbiamo dovuto affrontare il problema della clustering delle partite di rimanenze al momento dell'implementazione. WMS-sistemi e di come li abbiamo realizzati.

Quando abbiamo finito di scrivere l'articolo sugli algoritmi di ottimizzazione, è risultato molto lungo, quindi abbiamo deciso di dividere il materiale accumulato in 2 parti:

• Nella prima parte (questo articolo) parleremo di come abbiamo 'costruito' il modello matematico del problema e delle grandi difficoltà inaspettate che abbiamo incontrato durante l'elaborazione e la trasformazione dei dati di input per l'algoritmo.
• Nella seconda parte analizzeremo in dettaglio l'implementazione dell'algoritmo nel linguaggio C++, condurremo un esperimento computazionale e riassumeremo l'esperienza acquisita durante l'implementazione di tali 'tecnologie intelligenti' nei processi aziendali del cliente.

Come leggere l'articolo. Se hai letto l'articolo precedente, puoi passare direttamente al capitolo 'Panoramica delle soluzioni esistenti', altrimenti, la descrizione del problema affrontato si trova nel spoiler qui sotto.

Descrizione del problema affrontato nel magazzino del cliente

Collo di bottiglia nei processi

Nel 2018 abbiamo realizzato un progetto per l'implementazione di WMS-sistema presso il magazzino 'Casa commerciale "LD"' a Chelyabinsk. Abbiamo implementato il prodotto "1C-Logistica: Gestione del magazzino 3" su 20 postazioni di lavoro: operatori WMS, magazzinieri, autisti di carrelli elevatori. Il magazzino ha una superficie di circa 4.000 m², con 5.000 posti e 4.500 SKU. Nel magazzino si conservano rubinetti a sfera di produzione propria di diverse dimensioni, da 1 kg a 400 kg. Le scorte nel magazzino sono gestite per lotto, poiché è necessario selezionare i prodotti secondo il FIFO.

Durante la progettazione dei sistemi di automazione dei processi di magazzino, ci siamo trovati di fronte al problema di una gestione non ottimale delle scorte. La specificità di stoccaggio e disposizione dei rubinetti richiede che in un'unica cella di stoccaggio possano trovarsi solo articoli di un singolo lotto (vedi figura 1). La merce arriva in magazzino quotidianamente, e ogni arrivo corrisponde a un lotto separato. In totale, in un mese di attività, si generano 30 lotti distinti, ciascuno dei quali deve essere immagazzinato in una cella separata. La merce viene spesso selezionata non in interi pallet, ma a pezzi, e di conseguenza, nell'area di prelievo a pezzi, si osserva spesso la seguente situazione: in una cella di oltre 1 m³ giacciono diversi rubinetti che occupano meno del 5-10% del volume della cella.

Figura 1. Foto di alcuni pezzi in una cella

C'è un uso non ottimale delle capacità di magazzino. Per illustrare l'entità del problema, posso fornire alcune cifre: in media ci sono da 100 a 300 celle con un volume superiore a 1 m³ con "residui minimi" in diversi periodi di attività del magazzino. Poiché il magazzino è relativamente piccolo, durante le stagioni di carico, questo fattore diventa un "collo di bottiglia" che rallenta fortemente i processi di accettazione e spedizione.

Idea per risolvere il problema

È emersa l'idea: raggruppare le partite residue con le date più vicine in un'unica partita e disporre tali residui con una partita unificata in modo compatto all'interno di una cella, o in più celle se lo spazio non è sufficiente per contenere tutta la quantità dei residui. Un esempio di tale "compressione" è illustrato nella figura 2.

Fig.2. Schema di compressione dei residui nelle celle

Questo consente di ridurre significativamente lo spazio di magazzino occupato, che sarà utilizzato per i nuovi prodotti in arrivo. In situazioni di sovraccarico delle capacità di stoccaggio, questa misura è estremamente necessaria; altrimenti, lo spazio disponibile per l'accoglienza di nuovi articoli potrebbe non essere sufficiente, portando a una paralisi dei processi di stoccaggio e rifornimento, e di conseguenza a una paralisi delle operazioni di accettazione e spedizione. Prima dell'implementazione del sistema WMS, questo processo veniva eseguito manualmente, risultando inefficace, poiché la ricerca di residui adeguati nelle celle richiedeva tempo. Ora, con l'introduzione del sistema WMS, abbiamo deciso di automatizzare, velocizzare e rendere più intelligente il processo.

Il processo di risoluzione di questa problematica si suddivide in 2 fasi:

• nella prima fase troviamo gruppi di lotti vicini per data da comprimere (questa fase è dedicata a questa attività) l'articolo precedente);
• nella seconda fase calcoliamo per ogni gruppo di lotti la disposizione più compatta possibile dei residui nelle celle.

In questo articolo ci concentreremo sulla seconda fase dell'algoritmo.

Panoramica delle soluzioni esistenti

Prima di passare alla descrizione degli algoritmi che abbiamo sviluppato, è utile fare una breve panoramica sui sistemi già esistenti sul mercato WMS, nei quali è implementata una funzionalità simile di compressione ottimale.

In primo luogo, è necessario menzionare il prodotto "1C: Enterprise 8. WMS Logistica. Gestione del Magazzino 4", che appartiene e viene distribuito dall'azienda 1C ed è parte della quarta generazione WMS-sistemi sviluppati dalla società AXELOT. In questo sistema è dichiarata la funzionalità di compressione, volta a unire i resti di merce sparsi in un'unica cella comune. È importante specificare che la funzionalità di compressione in un tale sistema include anche altre possibilità, come la correzione del posizionamento dei prodotti nelle celle secondo le loro classi ABC, ma non ci soffermeremo su questi aspetti.

Analizzando il codice del sistema "1C: Enterprise 8. WMS Logistica. Gestione del Magazzino 4" (che in questa parte della funzionalità è aperto), si può concludere quanto segue. L'algoritmo di compressione delle giacenze implementa una logica lineare piuttosto primitiva e non può essere definito come "ottimale". Naturalmente, non prevede la clusterizzazione dei lotti. Diversi clienti che hanno implementato tale sistema si sono lamentati dei risultati nella pianificazione della compressione. Ad esempio, in pratica, durante la compressione si verificava spesso la seguente situazione: 100 pezzi di merce da una cella vengono pianificati per essere spostati in un'altra cella, dove c'è 1 pezzo di merce, mentre sarebbe ottimale, dal punto di vista del tempo, fare il contrario.

Anche la funzionalità di compressione delle giacenze nelle celle è presente in molti sistemi esteri, WMS- ma, sfortunatamente, non abbiamo né recensioni reali sull'efficacia degli algoritmi (è un segreto commerciale), né tantomeno informazioni sulla profondità della loro logica (software proprietario con codice chiuso), quindi non possiamo esprimere un giudizio.

Ricerca di un modello matematico del problema

Per progettare algoritmi di qualità per risolvere un problema, è necessario inizialmente formulare chiaramente questo problema in termini matematici, il che faremo.

Ci sono molte celle , in cui si trovano i residui di alcuni beni. Queste celle saranno chiamate celle donatrici. Indichiamo il volume dei beni presenti nella cella $.

È importante notare che nella procedura di compressione può partecipare solo un prodotto di un lotto, o di più lotti precedentemente riuniti in un cluster (leggi l'articolo precedente), a causa delle specificità di stoccaggio e sistemazione dei beni. Per diversi beni o diversi cluster di lotti deve essere avviata una propria procedura di compressione separata.

Ci sono molte celle , in cui possono essere potenzialmente collocati i residui delle celle donatrici. Queste celle saranno chiamate celle contenitore. Possono essere sia celle libere nel magazzino, sia celle donatrici di un certo insieme . L'insieme è sempre un sottoinsieme di .

Per ogni cella dell'insieme sono stati definiti limiti di capacità , misurati in dm3. Un dm3 rappresenta un cubo con lati di 10 cm. I prodotti stoccati sono abbastanza voluminosi, quindi in questo caso questa discrepanza è sufficientemente adeguata.

È stata data una matrice delle distanze minime in metri tra ogni coppia di celle , dove e appartenenti a insiemi e rispettivamente.

Indichiamo i «costanni» per il movimento della merce da una cella a un'altra cella . Indichiamo i «costi» per la scelta di un contenitore per trasferire in esso le rimanenze da altre celle. Come e in quali unità di misura saranno calcolati i valori e lo discuteremo più avanti (vedi sezione preparazione dei dati d'ingresso), al momento è sufficiente dire che tali grandezze saranno direttamente proporzionali alle grandezze e rispettivamente.

Indichiamo con una variabile che assume valore 1 se le rimanenze dalla cella vengono trasferite nel contenitore , e 0 in caso contrario. Indichiamo con una variabile che assume valore 1 se il contenitore contiene le rimanenze della merce, e 0 in caso contrario.

La questione è formulata così: è necessario trovare un insieme di contenitori e in questo modo «collegare» le celle donatrici alle celle contenitore, al fine di minimizzare la funzione

soggetta a vincoli

In totale, nel corso del calcolo della soluzione del problema, cerchiamo di:

• innanzitutto, risparmiare capacità di magazzino;
• in secondo luogo, risparmiare tempo per i magazzinieri.

L'ultima restrizione implica che non possiamo spostare merci in un container non selezionato e, di conseguenza, non «sostenere costi» per la sua scelta. Questa restrizione significa anche che il volume delle merci spostate dalle celle nel container non deve superare la capacità del container. Considereremo la soluzione del problema come un insieme di container e modi per collegare le celle donatrici ai container.

Questa formulazione del problema di ottimizzazione non è nuova ed è stata studiata da molti matematici fin dall'inizio degli anni '80 del secolo scorso. Nella letteratura estera, esistono 2 problemi di ottimizzazione con un modello matematico appropriato: Single-Source Capacitated Facility Location Problem e Multi-Source Capacitated Facility Location Problem (parleremo più avanti delle differenze tra i compiti). È importante notare che nella letteratura matematica questo tipo di problemi di ottimizzazione viene formulato in termini di posizionamento delle imprese sul territorio, da cui il nome 'Facility Location'. Questo è in gran parte una questione di tradizione, poiché la necessità di risolvere tali problemi combinatori è emersa principalmente nel campo della logistica, in particolare nell'industria militare negli anni '50 del secolo scorso. In termini di posizionamento delle imprese, i problemi sono formulati come segue:

• Esiste un insieme finito di città dove è potenzialmente possibile posizionare impianti di produzione (di seguito città-produttore). Per ogni città-produttore sono indicati i costi di apertura di un impianto e le limitazioni alla capacità produttiva dell'impianto stesso.
• Esiste un insieme finito di città dove si trovano effettivamente i clienti (di seguito città-clienti). Per ciascuna di queste città-clienti è indicato il volume della domanda per i prodotti. Per semplicità, consideriamo che il prodotto prodotto dagli impianti e consumato dai clienti sia lo stesso.
• Per ogni coppia città-produttore e città-cliente è stata definita l'entità dei costi di trasporto per la consegna del volume richiesto di prodotti dal produttore al cliente.

È necessario determinare in quali città aprire stabilimenti e come associare i clienti a tali stabilimenti affinché:

• I costi totali di apertura degli stabilimenti e i costi di trasporto siano minimali;
• Il volume della domanda dei clienti associati a un qualsiasi stabilimento aperto non superi le capacità produttive di tale stabilimento.

È ora opportuno parlare dell'unica differenza tra questi due problemi classici:

• Single-Source Capacitated Facility Location Problem – il cliente è rifornito solo da un singolo stabilimento aperto;
• Multi-Source Capacitated Facility Location Problem – il cliente può essere rifornito da più stabilimenti aperti contemporaneamente.

Questa differenza tra i due problemi può sembrare insignificante a prima vista, ma in realtà porta a strutture combinatorie completamente diverse per questi problemi e, di conseguenza, a algoritmi di risoluzione totalmente differenti. La differenza tra i problemi è illustrata nella figura sottostante.

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

Fig. 3. b) Problema della Localizzazione di Impianti Capacitati a Fonte Singola

Entrambi i problemi - sono complessi, cioè non esiste un algoritmo esatto che possa risolvere tale problema in tempo polinomiale in funzione della dimensione dell'input. In parole più semplici, tutti gli algoritmi esatti per risolvere il problema richiederanno un tempo esponenziale, sebbene possano essere più veloci di un semplice esaurimento delle opzioni. Poiché il problema - è difficile, considereremo solo euristiche approssimative, vale a dire algoritmi che calcolano soluzioni stabilmente molto vicine all'ottimale e che funzioneranno abbastanza rapidamente. Se c'è interesse per tali problemi, qui si può trovare una buona panoramica in russo.

Se traduciamo in termini del nostro problema di ottimizzazione del deposito di merci nelle celle, allora:

• le città-clienti sono celle-donatori con rimanenze di merci,
• le città-produttori sono celle-contenitori , in cui si prevede di inserire le rimanenze di altre celle,
• i costi di trasporto sono i costi di tempo del magazziniere per spostare il volume di merci dalla cella-donatore alla cella-contenitore ;
• i costi di apertura dell'impresa sono i costi di selezione del contenitore , pari al volume della cella-contenitore , moltiplicato per un certo coefficiente di risparmio dei volumi liberi (il valore del coefficiente è sempre > 1) (vedi sezione preparazione dei dati di input).

Dopo che l'analogia con le classiche forniture note è stata stabilita, è necessario rispondere a una domanda importante, dalla quale dipende la scelta dell'architettura dell'algoritmo di soluzione: il trasferimento dei residui dalla cella-donatrice è possibile solo in un solo contenitore (Single-Source) o è possibile il trasferimento dei residui in più celle-contenitori (Multi-Source)?

Vale la pena notare che, nella pratica, entrambe le formulazioni del problema sono presenti. Vediamo tutti i ‘pro’ e ‘contro’ per ciascuna di queste formulazioni qui di seguito:

Tabella 1. Vantaggi e svantaggi delle opzioni Single-Source e Multi-Source.

Poiché il numero di vantaggi per l'opzione Single-Source è maggiore, e considerando che minore è il numero di rimanenze nelle celle donatrici, minore è la differenza nel grado di compattezza della compressione calcolata per entrambe le varianti del problema, abbiamo optato per l'opzione Single-Source.

Vale la pena dire che anche l'opzione Multi-Source ha la sua validità. Esistono molteplici algoritmi efficaci per la sua risoluzione, la maggior parte dei quali si riduce alla soluzione di vari problemi di trasporto. Ci sono anche algoritmi non solo efficaci, ma anche eleganti, come ad esempio, qui.

Preparazione dei dati di input

Prima di iniziare ad analizzare e sviluppare un algoritmo per risolvere il problema, è necessario determinare quali dati e in quale formato forniremo in input. Non ci sono problemi con i volumi di giacenza delle merci nelle celle di origine e la capacità delle celle contenitore, in quanto questo è triviale: tali quantità saranno misurate in m³, ma per quanto riguarda i costi di utilizzo delle celle contenitore e la matrice dei costi di movimentazione non è tutto così semplice!

Iniziamo con il calcolo dei costi di movimentazione delle merci dalla cella di origine alla cella contenitore. Innanzitutto, è necessario stabilire quali unità di misura utilizzeremo per calcolare i costi di movimentazione. Due delle opzioni più ovvie sono i metri e i secondi. Non ha senso calcolare i costi di movimentazione in metri "puri". Dimostriamo questo con un esempio. Supponiamo che la cella sia situata al primo piano, mentre la cella si trova a 30 metri di distanza e si colloca al secondo piano:

• Muoversi da in è più costoso rispetto a muoversi da in , poiché scendere dal secondo piano (1,5-2 metri dal pavimento) è più facile che sollevare al secondo piano, anche se la distanza percorsa sarà la stessa;
• Spostare 1 pz. di merce dalla cella in Sarà più facile di spostare 10 unità dello stesso articolo, anche se la distanza percorsa sarà la stessa.

I costi di movimento sarebbero meglio considerati in secondi, poiché ciò consente di tenere conto delle differenze nei livelli e nella quantità di merce spostata. Per contabilizzare i costi di movimento in secondi, dobbiamo scomporre l'operazione di movimento in componenti elementari e misurare il tempo impiegato per ciascuna componente elementare.

Supponiamo che dalla cella vengano spostati unità di merce nel contenitore . Supponiamo che sia la velocità media di movimento dell'operatore nel magazzino, misurata in m/s. Supponiamo che e siano le velocità medie per le operazioni di prelievo e deposito rispettivamente per un volume di merce pari a 4 dm³ (volume medio che un dipendente in magazzino prende in un colpo durante le operazioni). Supponiamo che e sia l'altezza delle celle da cui vengono eseguite le operazioni di prelievo e deposito rispettivamente. Ad esempio, l'altezza media del primo livello (pavimento) è di 1 m, il secondo livello di 2 m, ecc. La formula per calcolare il tempo totale per eseguire l'operazione di movimento è la seguente: следующая:

Nella tabella 2 sono riportate le statistiche sui tempi di esecuzione di ciascuna operazione elementare, raccolte dal personale del magazzino tenendo conto delle specificità del prodotto stoccato.

Nome dell'operazione	Codice	Valore medio
Velocità media di movimento del lavoratore nel magazzino		1,5 m/sec
Velocità media di esecuzione di una operazione di deposito (per un volume di merce di 4 dm³)		2,4 sec

Tabella 2. Tempo medio di esecuzione delle operazioni di magazzino

Abbiamo definito il metodo di calcolo dei costi per il trasferimento. Ora è necessario scoprire come calcolare i costi per la scelta della cella-contenitore. Qui tutto è molto, molto più complesso rispetto ai costi di trasferimento, poiché:

• Innanzitutto, i costi devono essere direttamente proporzionali alla dimensione del contenitore: un volume identico di scorte trasferite da celle donatrici è preferibile collocarlo in un contenitore più piccolo piuttosto che in uno grande, a condizione che tale volume possa essere completamente contenuto in entrambi i contenitori. Così, riducendo i costi complessivi nella scelta dei contenitori, ci sforziamo di risparmiare capacità di magazzino "scarsa" nell'area di prelievo, per eseguire operazioni successive di allocazione della merce nelle celle. Nella figura 4 vengono mostrati i vari metodi di trasferimento delle scorte in contenitori grandi e piccoli e le conseguenze di tali scelte durante le operazioni di magazzino successive.
• In secondo luogo, poiché nel nostro approccio alla questione iniziale dobbiamo minimizzare i costi totali, che includono sia i costi di movimentazione che i costi di selezione dei contenitori, i volumi delle celle in metri cubici devono in qualche modo essere correlati ai secondi, il che non è affatto banale.

Fig. 4. Metodi di trasferimento delle scorte in contenitori di capacità diversa.

Nell'immagine 4, il volume delle giacenze che non può più essere contenuto nel container è mostrato in rosso nel secondo stadio di collocazione dei successivi prodotti.

Aiuterà a collegare i metri cubi di costi per la selezione del container con i secondi di costi per il trasferimento i seguenti requisiti per le soluzioni calcolate del problema:

• È necessario che le giacenze dalla cella donatrice siano spostate nella cella-container in ogni caso, se ciò riduce il numero totale di celle-container in cui si trova il prodotto.
• È fondamentale mantenere un equilibrio tra i volumi dei container e i costi di tempo per il trasferimento: ad esempio, se nella nuova soluzione rispetto alla precedente c'è un guadagno significativo nel volume e una perdita minima nei costi di tempo, è necessario scegliere la nuova soluzione.

Iniziamo con l'ultima richiesta. Per specificare il termine polisemico 'equilibrio', abbiamo condotto un sondaggio tra i dipendenti del magazzino per chiarire quanto segue. Supponiamo di avere una cella-container di volume , a cui è assegnato il trasferimento delle giacenze dei prodotti dalle celle donatrici e il tempo totale per tale trasferimento è pari a . Ci siano anche alcune opzioni alternative per posizionare la stessa quantità di merce da quelle celle donatrici in altri contenitori, dove ogni posizionamento ha la propria valutazione. , dove < e , dove >.

Sorge la domanda: quale è il guadagno minimo in volume accettabile, dato un valore di perdita di tempo. ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagramma della dipendenza del risparmio minimo accettabile in volume dall'aumento della differenza temporale nell'esecuzione dell'operazione.

Cioè, se i costi addizionali in tempo sono di 40 secondi, siamo disposti a sostenerli solo quando il guadagno in volume sarà di almeno 500 dm3. Nonostante si osservi una leggera non linearità nella dipendenza, per semplicità nei calcoli successivi considereremo che la relazione tra le quantità sia lineare e descritta dall'ineguaglianza.

Nell'immagine sottostante consideriamo i seguenti modi di posizionare la merce nei contenitori.

Fig. 6. Opzione (a): 2 contenitori, volume totale 400 dm3, tempo totale 150 sec.

Fig. 6. Opzione (b): 2 contenitori, volume totale 600 dm3, tempo totale 190 sec.

Fig. 6. Opzione (c): 1 contenitore, volume totale 400 dm3, tempo totale 200 sec.

L'opzione (a) per la scelta dei container è più preferibile rispetto all'opzione iniziale, poiché l'ineguaglianza è soddisfatta: (800-400)/10 >= 150-120, da cui segue 40 >= 30. L'opzione (b) è meno preferibile rispetto all'opzione iniziale, poiché l'ineguaglianza non è soddisfatta: (800-600)/10 >= 190-150, da cui segue 20 >= 40. Tuttavia, l'opzione (c) non si inserisce in questa logica! Esaminiamo questa opzione più da vicino. Da un lato, l'ineguaglianza (800-400)/10 >= 200-120 implica che l'ineguaglianza 40 >= 80 non è soddisfatta, il che indica che il guadagno in volume non giustifica una perdita così significativa in termini di tempo.

Ma dall'altro lato, in questa opzione (c), non solo riduciamo il volume complessivo occupato, ma riduciamo anche il numero di celle occupate, il che è il primo dei due requisiti importanti per le soluzioni computazionali dei problemi elencati sopra. È evidente che, affinché questo requisito venga soddisfatto, è necessario aggiungere al lato sinistro dell'ineguaglianza una certa costante positiva. , e questa costante deve essere aggiunta solo quando il numero di container diminuisce. Ricordiamo che — è una variabile che assume il valore 1 quando il contenitore è selezionato, e 0 quando il contenitore non è selezionato. Indichiamo – l'insieme dei contenitori nella soluzione originale e – l'insieme dei contenitori nella nuova soluzione. In generale, la nuova disuguaglianza sarà così:

Trasformando la disuguaglianza sopra, otteniamo

Da questo, abbiamo una formula per calcolare il costo totale di una certa variante della soluzione del problema:

Ma ora sorge la domanda: quale valore dovrebbe avere tale costante ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Sia – la distanza massima tra le celle del magazzino in una zona ABC, pari nel nostro caso a 100 m. Sia – il volume massimo della cella-contenitore nel magazzino, pari nel nostro caso a 1000 dm3.

Il primo modo per calcolare il valore . Consideriamo la situazione in cui ci sono 2 contenitori sul primo livello, nei quali è già fisicamente presente della merce, ossia essi stessi sono celle-donatrici, e i costi per spostare la merce in queste celle sono naturalmente pari a 0. È necessario trovare un tale valore della costante , nel quale sarebbe vantaggioso spostare sempre le rimanenze dal contenitore 1 al contenitore 2. Sostituendo i valori e nella disuguaglianza sopra citata, otteniamo:

da cui segue

Sostituendo i valori del tempo medio di esecuzione delle operazioni elementari nella formula sopra otteniamo

Un secondo metodo per calcolare la grandezza . Consideriamo la situazione in cui ci sono celle-donatrici da cui si prevede di spostare la merce nel contenitore 1. Indichiamo – la distanza dalla cella-donatrice al contenitore 1. C'è anche il contenitore 2, in cui ci sono già dei prodotti, e il cui volume consente di contenere i residui di tutte le celle. Per semplificare, supponiamo che il volume della merce spostata dalle celle-donatrici nei contenitori sia uguale e pari a . È necessario trovare un valore della costante , per il quale il collocamento di tutti i residui delle celle nel contenitore 2 risulti sempre più vantaggioso rispetto al collocamento in contenitori diversi:

Trasformando l'ineguaglianza otteniamo

Per 'rinforzare' il valore della grandezza , assumiamo che = 0. Il numero medio di celle normalmente coinvolte nella procedura di compressione dei residui in magazzino è pari a 10. Sostituendo i valori noti delle grandezze, abbiamo il seguente valore della costante

Prendiamo il valore massimo calcolato per ciascuna opzione, questo sarà il valore della grandezza per i parametri forniti per il magazzino. Ora, per completezza, registriamo la formula per calcolare i costi totali. per una certa soluzione ammissibile. :

Ecco, ora, dopo tutti questi sforzi titanici, dopo la trasformazione dei dati in ingresso, possiamo dire che tutti i dati sono stati trasformati nella forma necessaria e sono pronti per essere utilizzati nell'algoritmo di ottimizzazione.

Conclusione

Come dimostra la pratica, il carico di lavoro e l'importanza della fase di preparazione e trasformazione dei dati di input per l'algoritmo sono spesso sottovalutati. In questo articolo abbiamo dedicato particolare attenzione a questa fase per mostrare che solo i dati di input preparati con qualità e intelligenza possono rendere le soluzioni calcolate dall'algoritmo realmente preziose per il cliente. Sì, ci sono state molte deduzioni di formule, ma vi avevamo avvertiti prima della catena 🙂

Nel prossimo articolo finalmente arriveremo a ciò per cui sono stati pensati i 2 precedenti articoli: all'algoritmo di ottimizzazione discreta.

L'articolo è stato preparato da
Roman Shangin, programmatore del dipartimento progetti,
azienda Primo Bit, Città di Chelyabinsk

Fonte: habr.com