L'article décrit comment mettre en œuvre WMS-système, nous avons été confrontés à la nécessité de résoudre un problème de clustering non standard et aux algorithmes que nous avons utilisés pour le résoudre. Nous vous expliquerons comment nous avons appliqué une approche systématique et scientifique pour résoudre le problème, quelles difficultés nous avons rencontrées et quelles leçons nous avons tirées.
Cette publication commence une série d'articles dans lesquels nous partageons notre expérience réussie dans la mise en œuvre d'algorithmes d'optimisation dans les processus d'entrepôt. Le but de la série d'articles est de familiariser le public avec les types de problèmes d'optimisation des opérations d'entrepôt qui se posent dans presque tous les entrepôts de taille moyenne et grande, ainsi que de parler de notre expérience dans la résolution de ces problèmes et des pièges rencontrés en cours de route. . Les articles seront utiles à ceux qui travaillent dans le secteur de la logistique d'entrepôt, mettent en œuvre WMS-systèmes, ainsi que les programmeurs intéressés par les applications des mathématiques en entreprise et l'optimisation des processus dans une entreprise.
Goulot d'étranglement dans les processus
En 2018, nous avons réalisé un projet visant à mettre en œuvre WMS-systèmes dans l'entrepôt de la société «Trading House «LD» à Chelyabinsk. Nous avons mis en œuvre le produit « 1C-Logistics : Warehouse Management 3 » pour 20 postes de travail : opérateurs WMS, magasiniers, caristes. L'entrepôt moyen fait environ 4 2 m5000, le nombre de cellules est de 4500 1 et le nombre de SKU est de 400 XNUMX. L'entrepôt stocke des robinets à tournant sphérique de notre propre production de différentes tailles de XNUMX kg à XNUMX kg. L'inventaire dans l'entrepôt est stocké par lots, car il est nécessaire de sélectionner les marchandises selon le FIFO.
Lors de la conception de programmes d’automatisation des processus d’entrepôt, nous avons été confrontés au problème existant du stockage non optimal des stocks. Les spécificités du stockage et de l'arrimage des grues sont telles qu'une cellule de stockage unitaire ne peut contenir que les articles d'un seul lot. Les produits arrivent quotidiennement à l’entrepôt et chaque arrivée constitue un lot distinct. Au total, après 1 mois de fonctionnement de l'entrepôt, 30 lots distincts sont créés, malgré le fait que chacun doit être stocké dans une cellule distincte. Les produits sont souvent sélectionnés non pas par palettes entières, mais par morceaux, et par conséquent, dans la zone de sélection des pièces de nombreuses cellules, l'image suivante est observée : dans une cellule d'un volume de plus de 1 m3, il y a plusieurs morceaux de grues qui occupent moins de 5 à 10 % du volume cellulaire.
Fig 1. Photo de plusieurs marchandises dans une cellule
Il est clair que la capacité de stockage n’est pas utilisée de manière optimale. Pour imaginer l'ampleur de la catastrophe, je peux donner des chiffres : en moyenne, il y a de 1 à 3 cellules de ce type avec un volume de plus de 100 m300 avec des soldes « minuscules » pendant différentes périodes d'exploitation de l'entrepôt. Étant donné que l'entrepôt est relativement petit, pendant les saisons de pointe, ce facteur devient un « goulot d'étranglement » et ralentit considérablement les processus de l'entrepôt.
Idée de solution au problème
Une idée est née : les lots de restes avec les dates les plus proches devraient être réduits à un seul lot, et ces restes avec un lot unifié devraient être placés ensemble de manière compacte dans une cellule, ou dans plusieurs, s'il n'y a pas assez d'espace dans une pour accueillir le la totalité des restes.
Fig.2. Schéma de compression des résidus dans les cellules
Cela vous permet de réduire considérablement l'espace d'entrepôt occupé qui sera utilisé pour le placement de nouvelles marchandises. Dans une situation où la capacité de l'entrepôt est surchargée, une telle mesure est extrêmement nécessaire, sinon il pourrait tout simplement ne pas y avoir suffisamment d'espace libre pour accueillir de nouvelles marchandises, ce qui entraînerait un arrêt des processus de placement et de réapprovisionnement de l'entrepôt. Avant la mise en œuvre WMS-les systèmes effectuaient cette opération manuellement, ce qui était inefficace, car le processus de recherche de résidus appropriés dans les cellules était assez long. Aujourd’hui, avec l’introduction d’un système WMS, nous avons décidé d’automatiser le processus, de l’accélérer et de le rendre intelligent.
Le processus de résolution d'un tel problème est divisé en 2 étapes :
- dans un premier temps, nous trouvons des groupes de lots proches en date de compression ;
- dans un deuxième temps, pour chaque groupe de lots, nous calculons le placement le plus compact des marchandises restantes dans les cellules.
Dans l’article actuel, nous nous concentrerons sur la première étape de l’algorithme et laisserons la couverture de la deuxième étape pour le prochain article.
Rechercher un modèle mathématique du problème
Avant de nous asseoir pour écrire du code et réinventer notre roue, nous avons décidé d'aborder ce problème de manière scientifique, à savoir : le formuler mathématiquement, le réduire à un problème d'optimisation discrète bien connu et utiliser des algorithmes existants efficaces pour le résoudre, ou prendre ces algorithmes existants comme base et les adapter aux spécificités du problème pratique à résoudre.
Puisqu’il ressort clairement de la formulation commerciale du problème que nous avons affaire à des ensembles, nous formulerons un tel problème en termes de théorie des ensembles.
Laisser – l'ensemble de tous les lots du reste d'un certain produit dans un entrepôt. Laisser – étant donné la constante de jours. Laisser – un sous-ensemble de lots, où la différence de dates pour toutes les paires de lots du sous-ensemble ne dépasse pas une constante . Nous devons trouver le nombre minimum de sous-ensembles disjoints , de telle sorte que tous les sous-ensembles pris ensemble donnerait beaucoup .
En d’autres termes, nous devons trouver des groupes ou des clusters de partis similaires, où le critère de similarité est déterminé par la constante . Cette tâche nous rappelle le problème bien connu du clustering. Il est important de dire que le problème considéré diffère du problème de clustering en ce sens que notre problème a une condition strictement définie pour le critère de similarité des éléments du cluster, déterminé par la constante , mais dans le problème du clustering, une telle condition n'existe pas. L'énoncé du problème de clustering et des informations sur ce problème peuvent être trouvés
Nous avons donc réussi à formuler le problème et à trouver un problème classique avec une formulation similaire. Il est désormais nécessaire de considérer des algorithmes bien connus pour le résoudre, afin de ne pas réinventer la roue, mais de prendre les meilleures pratiques et de les appliquer. Pour résoudre le problème du clustering, nous avons considéré les algorithmes les plus populaires, à savoir : -moyens -moyens, algorithme d'identification des composants connectés, algorithme d'arbre couvrant minimum. Une description et une analyse de ces algorithmes peuvent être trouvées
Pour résoudre notre problème, des algorithmes de clustering -des moyens et -les moyens ne sont pas du tout applicables, puisque le nombre de clusters n'est jamais connu à l'avance et de tels algorithmes ne prennent pas en compte la contrainte de jours constants. De tels algorithmes ont été initialement écartés.
Pour résoudre notre problème, l'algorithme d'identification des composants connectés et l'algorithme du spanning tree minimum sont plus adaptés, mais il s'est avéré qu'ils ne peuvent pas être appliqués « de front » au problème à résoudre et obtenir une bonne solution. Pour expliquer cela, considérons la logique de fonctionnement de tels algorithmes par rapport à notre problème.
Considérez le graphique , dans lequel les sommets sont l'ensemble des parties , et l'arête entre les sommets и a un poids égal à la différence de jours entre les lots и . Dans l'algorithme d'identification des composants connectés, le paramètre d'entrée est spécifié Où , et dans le graphique tous les bords pour lesquels le poids est supérieur sont supprimés . Seules les paires d'objets les plus proches restent connectées. Le but de l'algorithme est de sélectionner une telle valeur , dans lequel le graphe « se désagrège » en plusieurs composantes connexes, où les parties appartenant à ces composantes satisferont notre critère de similarité, déterminé par la constante . Les composants résultants sont des clusters.
L'algorithme d'arbre couvrant minimum s'appuie d'abord sur un graphique arbre couvrant minimum, puis supprime séquentiellement les arêtes avec le poids le plus élevé jusqu'à ce que le graphe « s'effondre » en plusieurs composants connectés, où les parties appartenant à ces composants satisferont également notre critère de similarité. Les composants résultants seront des clusters.
Lors de l'utilisation de tels algorithmes pour résoudre le problème considéré, une situation comme dans la figure 3 peut se produire.
Fig 3. Application des algorithmes de clustering au problème à résoudre
Disons que notre constante pour la différence entre les jours de lot est de 20 jours. Graphique a été représenté sous forme spatiale pour faciliter la perception visuelle. Les deux algorithmes ont produit une solution à 3 clusters, qui peut être facilement améliorée en combinant les lots placés dans des clusters séparés les uns avec les autres ! Il est évident que de tels algorithmes doivent être modifiés pour s'adapter aux spécificités du problème à résoudre, et leur application sous sa forme pure pour résoudre notre problème donnera de mauvais résultats.
Ainsi, avant de commencer à écrire du code pour des algorithmes graphiques modifiés pour notre tâche et à réinventer notre propre vélo (dans les silhouettes duquel nous pouvions déjà discerner les contours de roues carrées), nous avons, encore une fois, décidé d'aborder un tel problème de manière scientifique, à savoir : essayez de le réduire à un autre problème discret d'optimisation, dans l'espoir que les algorithmes existants pour le résoudre pourront être appliqués sans modifications.
Une autre recherche sur un problème classique similaire a été couronnée de succès ! Nous avons réussi à trouver un problème d'optimisation discret dont la formulation coïncide 1 en 1 avec la formulation de notre problème. Cette tâche s'est avérée être problème de couverture. Présentons la formulation du problème par rapport à nos spécificités.
Il existe un ensemble fini et la famille de tous ses sous-ensembles disjoints de partis, de telle sorte que la différence de dates pour toutes les paires de partis de chaque sous-ensemble de la famille ne dépasse pas les constantes . Un revêtement s'appelle une famille de la moindre puissance, dont les éléments appartiennent à , tel que l'union des ensembles de la famille devrait donner l'ensemble de toutes les parties .
Une analyse détaillée de ce problème peut être trouvée и D'autres options pour l'application pratique du problème du revêtement et de ses modifications peuvent être trouvées
Algorithme pour résoudre le problème
Nous avons décidé du modèle mathématique du problème à résoudre. Examinons maintenant l'algorithme permettant de le résoudre. Sous-ensembles de la famille peut être facilement trouvé par la procédure suivante.
- Organiser les lots à partir d'un ensemble par ordre décroissant de leurs dates.
- Recherchez les dates de lots minimales et maximales.
- Pour tous les jours de la date minimale à la date maximale, retrouver tous les lots dont les dates diffèrent de pas plus que (donc la valeur Il vaut mieux prendre le nombre pair).
Logique de la procédure de formation d'une famille d'ensembles à jours est présenté à la figure 4.
Figure 4. Formation de sous-ensembles de partis
Cette procédure n'est pas nécessaire pour tout le monde parcourir tous les autres lots et vérifier la différence entre leurs dates ou par rapport à la valeur actuelle déplacez-vous vers la gauche ou la droite jusqu'à trouver un lot dont la date est différente de de plus de la moitié de la valeur de la constante. Tous les éléments suivants, lorsqu'ils se déplacent à la fois vers la droite et vers la gauche, ne nous intéresseront pas, car pour eux la différence en jours ne fera qu'augmenter, puisque les éléments du tableau ont été initialement ordonnés. Cette approche permettra de gagner beaucoup de temps lorsque le nombre de soirées et la répartition de leurs dates sont très importants.
Le problème de couverture d’ensemble est -difficile, ce qui signifie qu'il n'existe pas d'algorithme rapide (avec un temps de fonctionnement égal à un polynôme des données d'entrée) et précis pour le résoudre. Par conséquent, pour résoudre le problème de couverture d’ensemble, un algorithme glouton rapide a été choisi, qui, bien sûr, n’est pas précis, mais présente les avantages suivants :
- Pour des problèmes de petite taille (et c'est exactement notre cas), il calcule des solutions assez proches de l'optimum. À mesure que l’ampleur du problème augmente, la qualité de la solution se détériore, mais encore assez lentement ;
- Très simple à mettre en œuvre ;
- Rapide, puisque son estimation du temps d'exécution est .
L'algorithme glouton sélectionne les ensembles selon la règle suivante : à chaque étape, un ensemble est sélectionné qui couvre le nombre maximum d'éléments non encore couverts. Une description détaillée de l'algorithme et de son pseudocode peut être trouvée
Une comparaison de la précision d'un tel algorithme glouton sur des données de test du problème à résoudre avec d'autres algorithmes connus, tels que l'algorithme glouton probabiliste, l'algorithme des colonies de fourmis, etc., n'a pas été effectuée. Les résultats de la comparaison de tels algorithmes sur des données aléatoires générées peuvent être trouvés
Implémentation et mise en œuvre de l'algorithme
Cet algorithme a été implémenté dans le langage 1S et a été inclus dans un traitement externe appelé "Residue Compression" qui était connecté à WMS-système. Nous n'avons pas implémenté l'algorithme dans le langage C ++ et l'utiliser depuis un composant Natif externe, ce qui serait plus correct, puisque la vitesse du code est moindre C + + fois et dans certains exemples même des dizaines de fois plus rapide que la vitesse d'un code similaire sur 1S. Sur la langue 1S L’algorithme a été mis en œuvre pour gagner du temps de développement et faciliter le débogage dans la base de production du client. Le résultat de l'algorithme est présenté dans la figure 5.
Figure 5. Traitement pour « comprimer » les résidus
La figure 5 montre que dans l'entrepôt spécifié, les soldes actuels des marchandises dans les cellules de stockage sont divisés en clusters, au sein desquels les dates des lots de marchandises ne diffèrent pas de plus de 30 jours les unes des autres. Étant donné que le client produit et stocke des robinets à bille métalliques dans l'entrepôt, dont la durée de conservation est calculée en années, une telle différence de date peut être négligée. A noter qu'un tel traitement est actuellement utilisé systématiquement en production, et les opérateurs WMS confirmer la bonne qualité du regroupement des partis.
Conclusions et suite
La principale expérience que nous avons acquise en résolvant un problème aussi pratique est la confirmation de l’efficacité de l’utilisation du paradigme : les mathématiques. énoncé du problème célèbre tapis. modèle célèbre algorithme algorithme prenant en compte les spécificités du problème. L'optimisation discrète existe depuis plus de 300 ans et, pendant cette période, les gens ont réussi à considérer de nombreux problèmes et à accumuler beaucoup d'expérience pour les résoudre. Tout d’abord, il est plus conseillé de se tourner vers cette expérience, et ensuite seulement de commencer à réinventer sa roue.
Dans le prochain article, nous continuerons l'histoire des algorithmes d'optimisation et examinerons le plus intéressant et le plus complexe : un algorithme de « compression » optimale des résidus cellulaires, qui utilise comme entrée les données reçues de l'algorithme de clustering par lots.
Preparé par
Roman Shangin, programmeur du département projets,
Première entreprise BIT, Chelyabinsk
Source: habr.com