L'articolo descrive come implementare WMS-system, ci siamo trovati di fronte alla necessità di risolvere un problema di clustering non standard e quali algoritmi abbiamo utilizzato per risolverlo. Ti racconteremo come abbiamo applicato un approccio sistematico e scientifico alla risoluzione del problema, quali difficoltà abbiamo incontrato e quali lezioni abbiamo imparato.
Questa pubblicazione inizia una serie di articoli in cui condividiamo la nostra esperienza di successo nell'implementazione di algoritmi di ottimizzazione nei processi di magazzino. Lo scopo della serie di articoli è quello di far conoscere al pubblico i tipi di problemi di ottimizzazione delle operazioni di magazzino che si presentano in quasi tutti i magazzini di medie e grandi dimensioni, nonché di raccontare la nostra esperienza nella risoluzione di tali problemi e le insidie incontrate lungo il percorso . Gli articoli saranno utili a chi lavora nel settore della logistica di magazzino, implementarli WMS-sistemi, nonché programmatori interessati alle applicazioni della matematica nel mondo degli affari e all'ottimizzazione dei processi in un'impresa.
Collo di bottiglia nei processi
Nel 2018 abbiamo completato un progetto da implementare WMS-sistemi presso il magazzino della società “Trading House “LD” a Chelyabinsk. Abbiamo implementato il prodotto “1C-Logistics: Warehouse Management 3” per 20 posti di lavoro: operatori WMS, magazzinieri, carrellisti. Il magazzino medio è di circa 4mila m2, il numero di celle è 5000 e il numero di SKU è 4500. Il magazzino immagazzina valvole a sfera di nostra produzione di diverse dimensioni da 1 kg a 400 kg. L'inventario nel magazzino viene immagazzinato in lotti, poiché è necessario selezionare le merci secondo FIFO.
Durante la progettazione degli schemi di automazione dei processi di magazzino, ci siamo trovati di fronte al problema esistente di uno stoccaggio non ottimale delle scorte. Le specifiche delle gru di stoccaggio e stivaggio sono tali che una cella di stoccaggio unitaria può contenere solo articoli di un lotto. I prodotti arrivano al magazzino quotidianamente e ogni arrivo costituisce un lotto separato. In totale, dopo 1 mese di funzionamento del magazzino, vengono creati 30 lotti separati, nonostante ciascuno debba essere conservato in una cella separata. Spesso i prodotti vengono selezionati non in pallet interi, ma in pezzi e, di conseguenza, nella zona di selezione dei pezzi in molte celle si osserva la seguente immagine: in una cella con un volume superiore a 1 m3 ci sono diversi pezzi di gru che occupano meno del 5-10% del volume cellulare.
Fig 1. Foto di diversi articoli in una cella
È chiaro che la capacità di stoccaggio non viene utilizzata in modo ottimale. Per immaginare l'entità del disastro, posso fornire delle cifre: in media, ci sono da 1 a 3 celle di tali celle con un volume superiore a 100 m300 con saldi “minuscoli” durante diversi periodi di funzionamento del magazzino. Poiché il magazzino è relativamente piccolo, durante i periodi di maggiore affluenza di magazzino questo fattore diventa un “collo di bottiglia” e rallenta notevolmente i processi di magazzino.
Idea per la soluzione del problema
È nata un'idea: i lotti di avanzi con le date più vicine dovrebbero essere ridotti a un unico lotto, e tali avanzi con un lotto unificato dovrebbero essere collocati insieme in modo compatto in una cella, o in più celle, se in una non c'è abbastanza spazio per accogliere il intera quantità di avanzi.
Fig.2. Schema per comprimere i residui nelle cellule
Ciò consente di ridurre notevolmente lo spazio occupato nel magazzino che verrà utilizzato per il posizionamento della nuova merce. In una situazione in cui la capacità del magazzino è sovraccarica, tale misura è estremamente necessaria, altrimenti potrebbe semplicemente non esserci abbastanza spazio libero per accogliere nuove merci, il che porterà ad un arresto dei processi di posizionamento e rifornimento del magazzino. In precedenza prima dell'implementazione WMS-i sistemi eseguivano questa operazione manualmente, il che era inefficace, poiché il processo di ricerca dei residui idonei nelle cellule era piuttosto lungo. Ora, con l’introduzione di un sistema WMS, abbiamo deciso di automatizzare il processo, velocizzarlo e renderlo intelligente.
Il processo di risoluzione di tale problema è diviso in 2 fasi:
- nella prima fase troviamo gruppi di lotti vicini per data di compressione;
- nella seconda fase, per ciascun gruppo di lotti si calcola la collocazione più compatta della merce rimanente nelle celle.
Nel presente articolo ci concentreremo sulla prima fase dell'algoritmo e lasceremo la trattazione della seconda fase per il prossimo articolo.
Cerca un modello matematico del problema
Prima di sederci a scrivere codice e reinventare la nostra ruota, abbiamo deciso di affrontare questo problema scientificamente, vale a dire: formularlo matematicamente, ridurlo a un noto problema di ottimizzazione discreta e utilizzare efficaci algoritmi esistenti per risolverlo, o prendere questi algoritmi esistenti come base e modificarli in base alle specificità del problema pratico da risolvere.
Poiché dalla formulazione commerciale del problema risulta chiaramente che abbiamo a che fare con gli insiemi, formuleremo tale problema in termini di teoria degli insiemi.
lasciare – l'insieme di tutti i lotti della rimanenza di un determinato prodotto in un magazzino. Permettere – data la costante dei giorni. Permettere – un sottoinsieme di lotti, dove la differenza di date per tutte le coppie di lotti nel sottoinsieme non supera una costante . Dobbiamo trovare il numero minimo di sottoinsiemi disgiunti , tale che tutti i sottoinsiemi presi insieme ne darebbero molti .
In altre parole, dobbiamo trovare gruppi o cluster di partiti simili, dove il criterio di somiglianza è determinato dalla costante . Questo compito ci ricorda il noto problema del clustering. È importante dire che il problema in esame differisce dal problema del clustering in quanto il nostro problema ha una condizione strettamente definita per il criterio di somiglianza degli elementi del cluster, determinata dalla costante , ma nel problema del clustering non esiste tale condizione. È possibile trovare la dichiarazione del problema del clustering e le informazioni su questo problema
Siamo quindi riusciti a formulare il problema e a trovare un problema classico con una formulazione simile. Ora è necessario considerare algoritmi noti per risolverlo, in modo da non reinventare la ruota, ma prendere le migliori pratiche e applicarle. Per risolvere il problema del clustering, abbiamo considerato gli algoritmi più diffusi, vale a dire: -significa, -mezzi, algoritmo per l'identificazione delle componenti connesse, algoritmo del minimo spanning tree. È possibile trovare una descrizione e un'analisi di tali algoritmi
Per risolvere il nostro problema, algoritmi di clustering -significa e -i mezzi non sono affatto applicabili, poiché il numero di cluster non è mai noto in anticipo e tali algoritmi non tengono conto del vincolo di giorni costanti. Tali algoritmi furono inizialmente scartati dalla considerazione.
Per risolvere il nostro problema, l'algoritmo per l'identificazione dei componenti connessi e l'algoritmo dell'albero di copertura minimo sono più adatti, ma, come si è scoperto, non possono essere applicati "frontalmente" al problema da risolvere e ottenere una buona soluzione. Per spiegare questo, consideriamo la logica di funzionamento di tali algoritmi in relazione al nostro problema.
Considera il grafico , in cui i vertici sono l'insieme dei partiti e il bordo tra i vertici и ha un peso pari alla differenza di giorni tra lotti и . Nell'algoritmo per l'identificazione dei componenti collegati, viene specificato il parametro di input Dove e nel grafico tutti i bordi per i quali il peso è maggiore vengono rimossi . Solo le coppie di oggetti più vicine rimangono connesse. Lo scopo dell'algoritmo è selezionare tale valore , in cui il grafico “si sfalda” in più componenti connesse, dove le parti appartenenti a queste componenti soddisferanno il nostro criterio di similarità, determinato dalla costante . I componenti risultanti sono cluster.
L'algoritmo dell'albero di copertura minimo si basa innanzitutto su un grafico albero ricoprente minimo, e poi rimuove sequenzialmente gli archi con il peso più alto finché il grafo “si divide” in più componenti connesse, dove anche le parti appartenenti a queste componenti soddisferanno il nostro criterio di similarità. I componenti risultanti saranno cluster.
Quando si utilizzano tali algoritmi per risolvere il problema in esame, può verificarsi una situazione come nella Figura 3.
Fig 3. Applicazione degli algoritmi di clustering al problema da risolvere
Supponiamo che la nostra costante per la differenza tra i giorni batch sia 20 giorni. Grafico è stato raffigurato in forma spaziale per facilitare la percezione visiva. Entrambi gli algoritmi hanno prodotto una soluzione a 3 cluster, che può essere facilmente migliorata combinando tra loro i lotti inseriti in cluster separati! È ovvio che tali algoritmi necessitano di essere modificati per adattarsi alle specificità del problema da risolvere, e la loro applicazione nella sua forma pura alla soluzione del nostro problema darà scarsi risultati.
Quindi, prima di iniziare a scrivere codice per algoritmi grafici modificati per il nostro compito e a reinventare la nostra bicicletta (nelle cui sagome potevamo già distinguere i contorni delle ruote quadrate), abbiamo deciso, ancora una volta, di affrontare questo problema scientificamente, vale a dire: cercare di ridurlo ad un altro problema discreto di ottimizzazione, nella speranza che gli algoritmi esistenti per risolverlo possano essere applicati senza modifiche.
Un'altra ricerca per un problema classico simile ha avuto successo! Siamo riusciti a trovare un problema di ottimizzazione discreta, la cui formulazione coincide 1 in 1 con la formulazione del nostro problema. Questo compito si è rivelato essere impostare il problema della copertura. Presentiamo la formulazione del problema in relazione alle nostre specificità.
Esiste un insieme finito e famiglia di tutti i suoi sottoinsiemi disgiunti di partiti, in modo tale che la differenza nelle date per tutte le coppie di partiti di ciascun sottoinsieme dalla famiglia non supera le costanti . Una copertura è chiamata famiglia della potenza minore, i cui elementi appartengono , tale che l'unione degli insiemi dalla famiglia dovrebbe dare l'insieme di tutte le parti .
È possibile trovare un'analisi dettagliata di questo problema и Si possono trovare altre opzioni per l'applicazione pratica del problema della copertura e delle sue modifiche
L'algoritmo per risolvere il problema
Abbiamo deciso il modello matematico del problema da risolvere. Ora diamo un'occhiata all'algoritmo per risolverlo. Sottoinsiemi dalla famiglia possono essere facilmente reperiti con la seguente procedura.
- Organizzare i lotti da un set in ordine decrescente delle loro date.
- Trova le date minime e massime del batch.
- Per ogni giorno dalla data minima alla massima, trova tutti i batch le cui date differiscono non più di (quindi il valore È meglio prendere il numero pari).
Logica del procedimento per formare una famiglia di insiemi a giorni è presentato nella Figura 4.
Fig.4. Formazione di sottoinsiemi di partiti
Questa procedura non è necessaria per tutti esamina tutti gli altri batch e controlla la differenza nelle loro date o rispetto al valore corrente spostati a sinistra o a destra finché non trovi un batch la cui data è diversa da di più della metà del valore della costante. Tutti gli elementi successivi, quando ci sposteremo sia a destra che a sinistra, non ci interesseranno, poiché per loro la differenza di giorni non farà altro che aumentare, poiché gli elementi nell'array erano inizialmente ordinati. Questo approccio farà risparmiare tempo in modo significativo quando il numero di feste e la diffusione delle loro date sono significativamente elevati.
Il problema della copertura del set è -difficile, il che significa che non esiste un algoritmo veloce (con tempo operativo pari a un polinomio dei dati di input) e accurato per risolverlo. Pertanto, per risolvere il problema della copertura dell'insieme, è stato scelto un algoritmo veloce e greedy, che, ovviamente, non è accurato, ma presenta i seguenti vantaggi:
- Per problemi di piccole dimensioni (ed è proprio il nostro caso), calcola soluzioni abbastanza vicine all'ottimale. Man mano che la dimensione del problema aumenta, la qualità della soluzione peggiora, ma sempre piuttosto lentamente;
- Molto facile da implementare;
- Veloce, poiché la stima del tempo di esecuzione lo è .
L'algoritmo greedy seleziona gli insiemi in base alla seguente regola: in ogni fase viene selezionato un insieme che copre il numero massimo di elementi non ancora coperti. È possibile trovare una descrizione dettagliata dell'algoritmo e del suo pseudocodice
Non è stato effettuato un confronto dell'accuratezza di un tale algoritmo greedy sui dati di test del problema da risolvere con altri algoritmi noti, come l'algoritmo greedy probabilistico, l'algoritmo delle colonie di formiche, ecc. È possibile trovare i risultati del confronto di tali algoritmi su dati casuali generati
Implementazione e implementazione dell'algoritmo
Questo algoritmo è stato implementato nel linguaggio 1S ed è stato incluso in un'elaborazione esterna denominata "Residue Compression" a cui era collegato WMS-sistema. Non abbiamo implementato l'algoritmo nel linguaggio C ++ e usarlo da un componente nativo esterno, che sarebbe più corretto, poiché la velocità del codice è inferiore C++ volte e in alcuni esempi anche decine di volte più veloce della velocità di un codice simile 1S. Sulla lingua 1S L’algoritmo è stato implementato per risparmiare tempo di sviluppo e facilitare il debug presso la base di produzione del cliente. Il risultato dell'algoritmo è presentato nella Figura 5.
Fig.5. Lavorazione per “comprimere” i residui
La Figura 5 mostra che nel magazzino specificato, i saldi attuali delle merci nelle celle di stoccaggio sono divisi in cluster, all'interno dei quali le date dei lotti di merci differiscono l'una dall'altra di non più di 30 giorni. Poiché il cliente produce e immagazzina in magazzino valvole a sfera metalliche, la cui durata di conservazione è calcolata in anni, tale differenza di data può essere trascurata. Si noti che tale elaborazione è attualmente utilizzata sistematicamente nella produzione e negli operatori WMS confermare la buona qualità del clustering dei partiti.
Conclusioni e seguito
L'esperienza principale che abbiamo acquisito risolvendo un problema così pratico è la conferma dell'efficacia dell'utilizzo del paradigma: la matematica. dichiarazione problema famoso tappetino. modello famoso algoritmo algoritmo tenendo conto delle specificità del problema. L'ottimizzazione discreta esiste da più di 300 anni e durante questo periodo le persone sono riuscite a considerare molti problemi e ad accumulare molta esperienza nel risolverli. Prima di tutto, è più consigliabile rivolgersi a questa esperienza, e solo allora iniziare a reinventare la propria ruota.
Nel prossimo articolo continueremo la storia sugli algoritmi di ottimizzazione e vedremo quello più interessante e molto più complesso: un algoritmo per la “compressione” ottimale dei residui cellulari, che utilizza come input i dati ricevuti dall'algoritmo di clustering batch.
Preparato l'articolo
Roman Shangin, programmatore del dipartimento progetti,
Prima azienda BIT, Chelyabinsk
Fonte: habr.com