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 celle libere in magazzino e dello sviluppo di un algoritmo di ottimizzazione discreta per risolvere tale problema. Racconteremo come abbiamo "costruito" il modello matematico del problema di ottimizzazione e delle difficoltà inesperate che abbiamo incontrato nell'elaborazione dei dati di input per l'algoritmo.

Se siete interessati alle applicazioni della matematica nel business e non temete trasformazioni rigorose delle formule a livello di quinta elementare, benvenuti sotto il tag!

L'articolo sarà utile a coloro che implementano sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.Parte introduttiva

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

viene descritta la specificità del magazzino in cui abbiamo implementato

In articolo precedente il sistema, e viene anche spiegato perché abbiamo dovuto affrontare il problema della clustering delle partite di rimanenti prodotti durante l'implementazione del sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.sistema, e come lo abbiamo fatto. sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.Quando abbiamo finito di scrivere l'articolo sugli algoritmi di ottimizzazione, era molto lungo, quindi abbiamo deciso di suddividere 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 nell'elaborazione e trasformazione dei dati di input per l'algoritmo.

• Nella seconda parte esamineremo in dettaglio l'implementazione dell'algoritmo nel linguaggio
• , faremo un esperimento computazionale e riassumeremo l'esperienza che abbiamo acquisito durante l'implementazione di tali "tecnologie intelligenti" nei processi aziendali del cliente. C++Come leggere l'articolo. Se hai letto l'articolo precedente, puoi passare direttamente al capitolo "Panoramica delle soluzioni esistenti", altrimenti, la descrizione del problema risolto si trova nel riquadro qui sotto.

Descrizione del problema risolto nel magazzino del cliente

Collo di bottiglia nei processi

Nel 2018 abbiamo realizzato un progetto per l'implementazione

Nel 2018 abbiamo realizzato un progetto di implementazione sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.-sistemi nel magazzino "Casa commerciale 'LD' a Chelyabinsk. Implementato il prodotto '1C-Logistica: Gestione del Magazzino 3' su 20 postazioni di lavoro: operatori, magazzinieri, autisti di carrelli elevatori. sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.Il magazzino è di dimensioni medie, circa 4.000 m², con 5.000 scaffali e 4.500 SKU. Nel magazzino sono stoccati rubinetti sferici prodotti internamente di varie dimensioni, da 1 kg a 400 kg. Le scorte sono conservate per lotti, poiché esiste la necessità di selezionare i prodotti secondo il metodo FIFO.

Durante la progettazione degli schemi di automazione dei processi di magazzino, ci siamo imbattuti in un problema esistente di stoccaggio non ottimale delle scorte. La specificità di stoccaggio e disposizione dei rubinetti è tale che in un'unità di stoccaggio può trovarsi solo una nomenclatura di un lotto (vedi fig. 1). I prodotti arrivano in magazzino quotidianamente e ogni arrivo rappresenta un lotto separato. Di conseguenza, in un mese di attività del magazzino si creano 30 lotti distinti, ognuno dei quali deve essere conservato in un'unità separata. I prodotti vengono spesso estratti non in pallet interi, ma singolarmente, e di conseguenza nella zona di prelievo molte unità presentano la seguente situazione: in un'unità con volume superiore a 1 m³ si trovano diversi rubinetti, che occupano meno del 5-10% del volume dell'unità.

Fig. 1. Foto di più pezzi in un'unità

Si evidenzia un utilizzo non ottimale delle capacità di magazzino. Per rappresentare la portata del problema, posso fornire delle cifre: in media, queste unità di volume superiore a 1 m³ con "scorte minime" conteggiate in vari periodi di lavoro del magazzino oscillano tra 100 e 300 unità. Dato che il magazzino è relativamente piccolo, durante i periodi di alta attività questo fattore diventa un "collo di bottiglia" che rallenta notevolmente i processi di ricezione e spedizione.

Idea per risolvere il problema

È emersa l'idea di riunire i lotti di scorte con date di scadenza più vicine in un unico lotto e di collocare queste scorte con lotto uniformato in modo compatto insieme in un'unità, o in diverse unità se lo spazio in una non fosse sufficiente a contenere tutte le scorte. Un esempio di tale "compressione" è illustrato nella figura 2.

Fig. 2. Schema di compressione delle scorte nelle unità

Questo permette di ridurre significativamente gli spazi di magazzino occupati, che verranno utilizzati per la nuova merce da collocare. In caso di sovraccarico delle capacità di stoccaggio, questa misura diventa estremamente necessaria, altrimenti potrebbe semplicemente non esserci spazio sufficiente per collocare la nuova merce, il che porterà all'arresto dei processi di stoccaggio e rifornimento e, conseguentemente, all'arrivo e partenza. Prima dell'implementazione del sistema WMS, tale operazione veniva eseguita manualmente, risultando poco efficace, poiché il processo di ricerca dei giacenze adatte negli scaffali era piuttosto lungo. Ora, con l'implementazione del sistema WMS, abbiamo deciso di automatizzare, accelerare e rendere intelligente questo processo.

Il processo di risoluzione di questo compito è suddiviso in 2 fasi:

• nella prima fase, troviamo gruppi di lotti vicini per data da comprimere (questo compito è dedicato l'articolo precedente);
• nella seconda fase calcoliamo per ogni gruppo di lotti la collocazione più compatta possibile delle giacenze nei pallet.

Nell'articolo attuale ci concentreremo sulla seconda fase dell'algoritmo.

Panoramica delle soluzioni esistenti

Prima di passare alla descrizione degli algoritmi che abbiamo sviluppato, è opportuno fare una breve panoramica dei sistemi già esistenti sul mercato sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda., nei quali è implementata una funzionalità simile di compressione ottimale.

In primo luogo, è necessario sottolineare il prodotto "1C: Enterprise 8. WMS Logistica. Gestione del Magazzino 4", che appartiene e viene distribuito dalla società 1C ed è relativo alla quarta generazione sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.-sistemi, sviluppati dalla società AXELOT. In questo sistema è dichiarata la funzionalità di compressione, che è destinata a unire giacenze di merce disperse in un unico pallet. Vale la pena specificare che la funzionalità di compressione in un tale sistema include anche altre possibilità, come la correzione della collocazione dei prodotti nei pallet secondo le loro classi ABC, ma su queste non ci soffermeremo.

Analizzando il codice del sistema «1C: Impresa 8. WMS Logistica. Gestione del magazzino 4» (che in questa parte funzionale è aperto), si può concludere quanto segue. L'algoritmo di compressione delle rimanenze realizza una logica lineare piuttosto primitiva e non si può parlare di una compressione «ottimale». Ovviamente, non prevede la clustering delle partite. Alcuni clienti che hanno implementato un sistema simile si sono lamentati dei risultati della pianificazione della compressione. Ad esempio, spesso nella pratica, durante la compressione si verificava questa situazione: si pianificava di spostare 100 pezzi di merce da una cella a un'altra, dove c'era 1 pezzo di merce, mentre sarebbe stato ottimale, in termini di spesa di tempo, fare il contrario.

Anche la funzionalità di compressione delle rimanenze di merci nelle celle è stata dichiarata in molti sistemi esteri, sistemi WMS, operano nel settore della logistica di magazzino o produttiva, così come a programmatori interessati alle applicazioni della matematica nel business e all'ottimizzazione dei processi in azienda.ma, sfortunatamente, non abbiamo né feedback reali sull'efficacia del lavoro degli algoritmi (è un segreto commerciale), né tantomeno una comprensione della 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 il problema, è necessario prima formulare chiaramente il problema in modo matematico, cosa che faremo.

Ci sono molte celle , in cui si trovano le rimanenze di un certo prodotto. D'ora in poi, queste celle saranno chiamate celle-donatrici. Indichiamo il volume del prodotto presente nella cella $.

È importante dire che nella procedura di compressione può partecipare solo un prodotto di una singola partita, o di più partite precedentemente unite in un cluster (leggi l'articolo precedente), il che è dovuto alla specificità dello stoccaggio e della disposizione dei prodotti. Per diversi prodotti o diversi cluster di partite, deve essere avviata una propria procedura di compressione separata.

Ci sono molte celle , in cui possono essere potenzialmente trasferite le rimanenze delle celle-donatrici. Queste celle saranno chiamate celle-contenitori. Possono essere sia celle libere nel magazzino che celle-donatrici da un insieme di . Un insieme di rimanenze è sempre un sottoinsieme di Ogni cella .

dell'insieme ha restrizioni sulla capacità sono state stabilite limitazioni sulla capacità , misurati in dm3. Un dm3 è un cubo con lati di 10 cm. I prodotti stoccati in magazzino sono abbastanza grandi, quindi in questo caso tale discrezionamento è più che sufficiente.

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

Indichiamo i «costi» per il trasferimento della merce dalla cella alla cella . Indichiamo i «costi» per la scelta del contenitore per trasferire al suo interno i residui da altre celle. Come e in quali unità di misura saranno calcolati i valori e lo vedremo più avanti (vedi sezione preparazione dei dati di input), ora è sufficiente dire che tali grandezze saranno direttamente proporzionali alle grandezze e rispettivamente.

Indichiamo con una variabile che assume il valore 1, se i residui dalla cella vengono trasferiti nel contenitore , e 0 in caso contrario. Indichiamo con una variabile che assume il valore 1, se il contenitore contiene residui di merce, e 0 in caso contrario.

Il problema è formulato così: è necessario trovare un insieme di contenitori e così «collegare» le celle donatrici alle celle contenitore, per minimizzare la funzione

soggetta a vincoli

In sintesi, nel calcolo della soluzione del problema ci proponiamo di:

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

Quest'ultimo vincolo significa che non possiamo trasferire beni in un contenitore che non abbiamo scelto, e di conseguenza non abbiamo «sostenuto costi» per la sua scelta. Questo vincolo significa anche che il volume dei beni trasferiti dalle celle al contenitore non deve superare la capacità del contenitore. Per soluzione del problema intendiamo un insieme di contenitori e i modi per collegare le celle donatrici ai contenitori.

Questa formulazione del problema di ottimizzazione non è nuova ed è stata studiata da molti matematici fin dai primi anni '80 dello scorso secolo. Nella letteratura straniera ci sono 2 problemi di ottimizzazione con un modello matematico adatto: Single-Source Capacitated Facility Location Problem e Multi-Source Capacitated Facility Location Problem (parleremo delle differenze tra i compiti più avanti). È importante notare che nella letteratura matematica la formulazione di questi due problemi di ottimizzazione è espressa in termini di localizzazione delle strutture, da cui il nome "Facility Location". Questo è in gran parte un omaggio alla tradizione, poiché la necessità di risolvere tali problemi combinatori è emersa principalmente dal campo della logistica, in gran parte dall'industria militare negli anni '50 del secolo scorso. Nel contesto della localizzazione delle strutture, questi problemi vengono formulati come segue:

• Esiste un insieme finito di città dove è potenzialmente possibile localizzare le strutture produttive (di seguito città-produttrici). Per ogni città-produttore sono dati i costi di apertura di una struttura e le limitazioni sulla capacità produttiva della struttura che sarà aperta.
• Esiste un insieme finito di città dove si trovano effettivamente i clienti (di seguito città-clienti). Per ogni città-cliente è definito il volume di domanda per i prodotti. Per semplicità, considereremo che il prodotto che le strutture producono e che i clienti consumano sia lo stesso.
• Per ogni coppia città-produttore e città-cliente è specificato l’importo dei costi di trasporto per la consegna del volume richiesto di prodotti dal produttore al cliente.

È necessario determinare in quali città aprire le strutture e come associare i clienti a tali strutture in modo tale che:

• I costi complessivi di apertura delle strutture e i costi di trasporto siano minimi;
• Il volume della domanda dei clienti associati a una struttura aperta non superi la capacità produttiva di tale struttura.

Ora è opportuno menzionare l’unica differenza tra questi due classici problemi:

• Single-Source Capacitated Facility Location Problem – il cliente è rifornito solo da una sola struttura aperta;
• Multi-Source Capacitated Facility Location Problem – il cliente può essere rifornito da più strutture aperte contemporaneamente.

Questa differenza tra i due problemi, a prima vista, sembra trascurabile, ma in realtà porta a strutture combinatorie completamente diverse per tali problemi e, di conseguenza, a algoritmi di soluzione completamente diversi. La differenza tra i problemi è mostrata nell'immagine sottostante.

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

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

Entrambi i problemi -è difficile, cioè non esiste un algoritmo esatto che risolva un tale compito in tempo polinomiale rispetto alla dimensione dei dati di input. In altre parole, tutti gli algoritmi esatti per risolvere il problema richiederanno tempo esponenziale, anche se, possibilmente, più veloce rispetto a una ricerca esaustiva di tutte le opzioni. Poiché il compito -è difficile, quindi considereremo solo euristiche approssimative, cioè algoritmi che calcoleranno stabilmente soluzioni molto vicine all'ottimale e funzioneranno abbastanza rapidamente. Se ci fosse interesse per tali compiti, qui si può trovare una buona panoramica in russo.

Se si utilizza la terminologia del nostro compito di compressione ottimale delle merci nelle celle, allora:

• città-clienti – sono celle-donatrici con le rimanenze di merci,
• città-produttori – celle-contenitori , in cui si prevede di collocare le rimanenze da altre celle,
• costi di trasporto – costi di tempo del magazziniere per spostare il volume delle merci dalla cella-donatrice alla cella-contenitore ;
• costi di avvio dell'azienda – costi per la scelta del contenitore , pari al volume della cella-contenitore , moltiplicato per un certo coefficiente di risparmio del volume libero (il valore del coefficiente è sempre > 1) (vedere la sezione preparazione dei dati di input).

Dopo aver tracciato l'analogia con i noti problemi classici di fornitura, è necessario rispondere a una domanda importante da cui dipende la scelta dell'architettura dell'algoritmo di soluzione: è possibile spostare le rimanenze da una cella-donatrice solo su un solo contenitore (Single-Source), o è possibile spostare le rimanenze in più celle-contenitori (Multi-Source)?

Vale la pena notare che, nella pratica, entrambe le formulazioni del problema sono valide. Di seguito elencheremo tutti i 'pro' e 'contro' per ciascuna di queste formulazioni:

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

Poiché il numero di vantaggi della variante Single-Source è maggiore e tenendo conto del fatto che minore è il numero di rimanenze nelle celle donatrici, minore è la differenza nel grado di compattezza nella compressione calcolata secondo entrambe le varianti del problema, la nostra scelta è caduta sulla variante Single-Source.

Vale la pena dire che la soluzione della variante Multi-Source ha anch'essa rilevanza. Ci sono molti algoritmi efficaci per la sua risoluzione, la maggior parte dei quali si riduce alla risoluzione di una serie di problemi di trasporto. Ci sono anche algoritmi non solo efficaci, ma eleganti, ad esempio, qui.

Preparazione dei dati di input

Prima di procedere all'analisi e allo sviluppo dell'algoritmo per risolvere il problema, è necessario decidere quali dati e in quale forma presenteremo al suo ingresso. Non ci sono problemi con i volumi di rimanenze delle merci nelle celle donatrici e la capacità delle celle contenitore, poiché queste quantità saranno misurate in m3, ma con i costi di utilizzo della cella contenitore e la matrice dei costi per il trasporto non è tutto così semplice!

Iniziamo con il calcolo costi per il trasferimento delle merci dalla cella donatrice alla cella contenitore. Prima di tutto, è necessario stabilire in quali unità di misura calcoleremo i costi di trasferimento. Due opzioni evidenti sono i metri e i secondi. Calcolare i costi di trasferimento in 'metri puri' è privo di senso. Dimostriamo questo con un esempio. Supponiamo che la cella si trovi al primo piano, la cella si trovi a 30 metri di distanza e si trovi al secondo piano:

• Il trasferimento da in è più costoso del trasferimento da in , poiché è più facile scendere dal secondo piano (1,5-2 metri dal pavimento) che salire al secondo, anche se la distanza percorsa sarà la stessa;
• Trasferire 1 unità di merce dalla cella in sarà più facile che trasferire 10 unità della stessa merce, anche se la distanza percorsa sarà la stessa.

È meglio considerare i costi di trasferimento in secondi, poiché questo consente di tenere conto sia delle differenze di piano sia delle differenze nella quantità di merci trasferite. Per calcolare i costi di trasferimento in secondi, dobbiamo scomporre l'operazione di trasferimento nelle sue componenti elementari e misurare il tempo impiegato per eseguire ciascuna componente elementare.

Supponiamo che dalla cella venga trasferita unità di merce nel contenitore . Supponiamo che sia la velocità media di movimento del lavoratore nel magazzino, misurata in m/sec. Supponiamo che e sia la velocità media di esecuzione delle operazioni di prelievo e deposito, rispettivamente per un volume di merce pari a 4 dm3 (volume medio che un dipendente del magazzino preleva in un solo intervento). 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 piano (suolo) è di 1 m, il secondo piano è di 2 m e così via. Allora la formula per calcolare il tempo totale per eseguire l'operazione di trasferimento è la seguente:

Nella tabella 2 sono riportate le statistiche sui tempi di esecuzione di ciascuna operazione elementare, raccolte dai dipendenti del magazzino tenendo conto delle specificità delle merci stoccate.

Denominazione dell'operazione	Designazione	Valore medio
Velocità media di movimento del lavoratore nel magazzino		1,5 m/sec
Velocità media di esecuzione di un'operazione di deposito (per un volume di merce di 4 dm3)		2,4 sec

Tabella 2. Tempo medio di esecuzione delle operazioni di magazzino

Abbiamo definito il metodo di calcolo dei costi di trasferimento. Ora è necessario capire come calcolare i costi per la scelta della cella contenitoreQui tutto è molto, molto più complicato rispetto ai costi di movimentazione, poiché:

• in primo luogo, i costi devono dipendere direttamente dal volume del contenitore – è preferibile trasferire lo stesso volume di residui da celle donatrici in un contenitore più piccolo piuttosto che in uno grande, a condizione che tale volume possa essere completamente contenuto in entrambi i contenitori. Così, minimizzando i costi totali per la scelta dei contenitori, cerchiamo di salvaguardare le «scorte» di spazio di magazzino nella zona di prelievo, per eseguire le successive operazioni di collocazione della merce nelle celle. Nella figura 4 sono mostrati i vari modi di trasferire residui in contenitori di grandi e piccoli volumi e le conseguenze di tali modalità di movimentazione nel corso delle successive operazioni di magazzino.
• In secondo luogo, poiché nella soluzione del problema iniziale dobbiamo minimizzare proprio i costi totali, che sono la somma dei costi di movimentazione e dei costi di scelta dei contenitori, i volumi delle celle in metri cubi devono essere in qualche modo correlati ai secondi, il che non è affatto banale.

Fig. 4. Modi di trasferimento dei residui in contenitori di capacità diversa.

Nella figura 4 il volume dei residui che non può già essere contenuto nel contenitore nella seconda fase di collocazione dei successivi prodotti è indicato in rosso.

Per correlare i metri cubici dei costi di scelta del contenitore con i secondi dei costi di movimentazione, è necessario considerare i seguenti requisiti per le soluzioni calcolate del problema:

• È necessario che i residui dalla cella donatrice siano spostati nella cella contenitore in ogni caso, se ciò riduce il numero totale di celle contenitore in cui si trova la merce.
• È necessario mantenere un equilibrio tra i volumi dei contenitori e i costi di tempo per la movimentazione: ad esempio, se nella nuova soluzione rispetto alla precedente il guadagno in volume è grande e la perdita di tempo è piccola, allora è necessario scegliere la nuova opzione.

Iniziamo con l'ultimo requisito. Per specificare il termine polisemico «equilibrio», abbiamo condotto un sondaggio tra i dipendenti del magazzino per determinare quanto segue. Supponiamo di avere una cella contenitore con un volume , nella quale è previsto il trasferimento dei residui di merci da celle donatrici e il tempo totale di tale movimentazione è pari a . Ci siano anche ulteriori opzioni alternative per disporre la stessa quantità di merce dagli stessi magazzini in altri contenitori, dove ogni disposizioine ha le sue valutazioni , dove < e , dove >.

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

Fig. 5. Diagramma della relazione tra il risparmio minimo di volume ammissibile e l'aumento della differenza nel tempo di esecuzione dell'operazione

Cioè, se i costi aggiuntivi in termini di tempo ammontano a 40 secondi, siamo disposti a spenderli solo quando il guadagno in volume sarà di almeno 500 dm3. Anche se nella relazione si osserva una leggera non linearità, per semplificare i calcoli successivi, supponiamo che la relazione tra le grandezze sia lineare e sia descritta da un'ineguaglianza

Nell'immagine sottostante esamineremo i seguenti modi di disporre 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 contenitori è più preferibile rispetto all'opzione iniziale, poiché soddisfa l'ineguaglianza: (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. Ma l'opzione (c) non si inserisce in tale logica! Esaminiamo questa opzione più in dettaglio. Da un lato, l'ineguaglianza (800-400)/10>=200-120, quindi l'ineguaglianza 40 >= 80 non è soddisfatta, il che indica che il guadagno in volume non vale una così grande perdita di tempo.

Ma d'altra parte, in questa opzione (c), non stiamo solo riducendo il volume totale occupato, ma stiamo anche diminuendo il numero di celle occupate, che è la prima di due importanti requisiti per le soluzioni calcolate ai compiti sopra menzionati. È ovvio che, affinché questo requisito inizi a essere soddisfatto, è necessario aggiungere un certo valore positivo al lato sinistro dell'ineguaglianza , e tale costante deve essere aggiunta solo nel caso in cui il numero di contenitori diminuisca. Ricordiamo che è una variabile che vale 1 quando il contenitore è selezionato e 0 quando il contenitore non selezionato. Indichiamo, – un numero di contenitori nella soluzione iniziale e – un numero di contenitori nella nuova soluzione. In generale, la nuova disuguaglianza apparirà così:

Trasformando la disuguaglianza sopra, otteniamo

Da ciò, abbiamo la 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, che nel nostro caso è di 100 m. Sia – il volume massimo della cella-contenitore nel magazzino, pari nel nostro caso a 1000 dm3.

Il primo metodo per calcolare la grandezza . Consideriamo la situazione in cui ci sono 2 contenitori al primo piano, nei quali si trova già fisicamente la merce, cioè essi stessi sono celle-donatrici, e il costo per spostare la merce in quelle stesse celle è, ovviamente, 0. È necessario trovare un valore per la costante , per il quale sarebbe vantaggioso spostare sempre i resti dal contenitore 1 al contenitore 2. Sostituendo i valori e nella disuguaglianza sopra, otteniamo:

da cui segue

Sostituendo i valori dei tempi medi di esecuzione delle operazioni elementari nella formula sopra, otteniamo

Il 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, nel quale ci sono già beni, e il cui volume consente di contenere i resti di tutte le celle. Per semplicità, supporremo che il volume della merce spostata dalle celle-donatrici nei contenitori sia identico e pari a . È necessario trovare un valore per la costante , per il quale l'inserimento di tutti i resti dalle celle nel contenitore 2 sarebbe sempre più vantaggioso rispetto a inserirli in contenitori diversi:

Trasformando la disuguaglianza otteniamo

Per «rafforzare» il valore della grandezza , assumiamo che = 0. La media delle celle normalmente coinvolte nella procedura di compressione dei resti in magazzino è pari a 10. Sostituendo i valori noti delle grandezze, otteniamo il seguente valore per la costante

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

Ecco, ora, dopo tutti gli sforzi titanici per 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, la complessità e l'importanza della fase di preparazione e trasformazione dei dati in ingresso per l'algoritmo sono spesso sottovalutate. In questo articolo abbiamo dedicato particolare attenzione a tale fase per dimostrare che solo dati di ingresso preparati con qualità e intelligenza possono rendere le soluzioni calcolate dall'algoritmo veramente preziose per il cliente. Sì, sono state tratte molte conclusioni riguardo alle formule, ma vi avevamo avvertito già prima del taglio 🙂

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

Articolo preparato da
Roman Shankin, programmatore del dipartimento progetti,
azienda Primo Bit, Città di Chelyabinsk

Fonte: habr.com