Mathématiques discrètes pour WMS : algorithme de compression des produits dans les cellules (partie 1)

Dans cet article, nous allons expliquer comment nous avons résolu le problème du manque d'espaces libres dans l'entrepôt et comment nous avons développé un algorithme d'optimisation discrète pour aborder ce défi. Nous parlerons de la manière dont nous avons « construit » le modèle mathématique du problème d'optimisation et des difficultés imprévues que nous avons rencontrées lors du traitement des données d'entrée pour l'algorithme.

Si les applications des mathématiques en affaires vous intéressent et que vous n'avez pas peur de transformations algébriques complexes au niveau de la 5ème année, bienvenue sous le spoiler !

Cet article sera utile à ceux qui mettent en œuvre WMS-systèmes, qui travaillent dans le secteur de la logistique d'entrepôt ou de production, ainsi qu'aux programmeurs intéressés par les applications des mathématiques en affaires et l'optimisation des processus d'entreprise.

Partie introductive

Cette publication fait suite à une série d'articles dans lesquels nous partageons notre expérience réussie de mise en œuvre d'algorithmes d'optimisation dans les processus d'entrepôt.

Dans l'article précédent Nous décrivons les spécificités de l'entrepôt où nous avons mis en œuvre WMS-système, ainsi que les raisons pour lesquelles nous avons eu besoin de résoudre le problème de la classification des lots de stocks lors de la mise en œuvre de WMS-système, et comment nous y sommes parvenus.

Lorsque nous avons terminé d'écrire l'article sur les algorithmes d'optimisation, celui-ci s'est avéré très volumineux, c'est pourquoi nous avons décidé de diviser le matériel accumulé en 2 parties :

• Dans la première partie (cet article), nous raconterons comment nous avons « construit » le modèle mathématique du problème et les grandes difficultés rencontrées lors du traitement et de la transformation des données d'entrée pour l'algorithme.
• Dans la deuxième partie, nous examinerons en détail la mise en œuvre de l'algorithme en langage C++, nous réaliserons une expérience de calcul et résumerons l'expérience acquise lors de l'implémentation de ces « technologies intelligentes » dans les processus d'affaires du client.

Comment lire l'article. Si vous avez lu l'article précédent, vous pouvez passer directement à la section « Revue des solutions existantes », sinon, la description du problème à résoudre se trouve dans le spoiler ci-dessous.

Description du problème à résoudre dans l'entrepôt du client

Goulot d'étranglement dans les processus

En 2018, nous avons réalisé un projet de mise en œuvre WMS-système dans l'entrepôt « Maison de commerce « LD » à Tcheliabinsk. Nous avons déployé le produit « 1C-Logistique : Gestion d'entrepôt 3 » sur 20 postes de travail : opérateurs WMS, magasiniers, conducteurs de chariots élévateurs. L'entrepôt a une superficie d'environ 4 000 m2, avec 5 000 emplacements et 4 500 SKU. L'entrepôt stocke des vannes à bille fabriquées en interne de différentes tailles, allant de 1 kg à 400 kg. Les stocks sont conservés par lots, car il est nécessaire de sélectionner les produits selon la méthode FIFO.

Au cours de la conception des schémas d'automatisation des processus d'entreposage, nous avons rencontré un problème existant de stockage non optimal des stocks. La spécificité du stockage et de l'empilement des vannes est telle que dans un emplacement de stockage unitaire ne peut se trouver qu'une seule nomenclature d'un lot (voir fig. 1). Les produits arrivent à l'entrepôt quotidiennement et chaque arrivée constitue un lot distinct. En conséquence, à la fin d'un mois de fonctionnement de l'entrepôt, 30 lots distincts sont créés, chacun devant être stocké dans un emplacement séparé. Les articles sont souvent prélevés non par palettes entières, mais pièce par pièce, et cela entraîne une situation dans la zone de prélèvement unitaire où de nombreux emplacements montrent ce tableau : dans un emplacement de plus de 1 m3, plusieurs vannes occupent moins de 5 à 10 % du volume de l'emplacement.

Fig. 1. Photo de plusieurs pièces dans un emplacement

Il y a un usage non optimal des capacités de l'entrepôt. Pour illustrer l'ampleur du problème, je peux fournir des chiffres : en moyenne, il y a entre 100 et 300 de ces emplacements de plus de 1 m3 avec des « restes minimes » à différents moments de l'activité de l'entrepôt. Étant donné que l'entrepôt est relativement petit, ce facteur devient un « goulot d'étranglement » pendant les saisons de forte charge, ralentissant fortement les processus de réception et d'expédition.

Idée de solution au problème

L'idée est née : regrouper les lots de restes ayant des dates de péremption les plus proches en un lot unique et stocker ces restes avec un lot unifié de manière compacte ensemble dans un ou plusieurs emplacements si l'espace dans un seul emplacement n'est pas suffisant pour accueillir l'ensemble des restes. Un exemple de ce « compactage » est illustré à la figure 2.

Fig. 2. Schéma de compactage des restes dans les emplacements

Cela permet de réduire considérablement l'espace d'entrepôt occupé, qui sera utilisé pour le nouveau produit à stocker. Dans une situation de surcharge des capacités d'entreposage, cette mesure est absolument nécessaire ; sans cela, il se peut tout simplement qu'il n'y ait pas assez d'espace libre pour accueillir le nouveau produit, ce qui entraînera un blocage des processus de placement et d'approvisionnement, et par conséquent, un blocage de la réception et de l'expédition. Auparavant, avant l'implémentation du système WMS, cette opération était effectuée manuellement, ce qui était inefficace, car le processus de recherche des stocks appropriés dans les emplacements prenait un certain temps. Maintenant, avec l'introduction du système WMS, nous avons décidé d'automatiser ce processus, de l'accélérer et de le rendre intelligent.

Le processus de résolution de cette tâche se divise en 2 étapes :

• à la première étape, nous trouvons des groupes de lots similaires en date pour la compression (cette tâche est consacrée l'article précédent);
• à la deuxième étape, nous calculons pour chaque groupe de lots un emplacement maximalement compact des stocks de produits dans les emplacements.

Dans cet article, nous nous arrêterons à la deuxième étape de l'algorithme.

Vue d'ensemble des solutions existantes

Avant de passer à la description des algorithmes que nous avons développés, il convient de faire un bref aperçu des systèmes déjà existants sur le marché WMS, qui réalisent une telle fonctionnalité d'optimisation de compression.

En premier lieu, il est nécessaire de mentionner le produit « 1C: Entreprise 8. WMS Logistique. Gestion de l'entrepôt 4 », qui appartient et est distribué par la société 1C et fait partie de la quatrième génération WMS- systèmes, développés par l'entreprise AXELOT. Dans ce système, une fonctionnalité de compression est déclarée, conçue pour regrouper des stocks de produits disparates dans un même emplacement général. Il convient de préciser que la fonctionnalité de compression dans un tel système comprend également d'autres possibilités, par exemple, la correction de l'emplacement des produits dans les emplacements selon leurs classes ABC, mais nous ne nous attarderons pas sur ces points.

Si nous analysons le code du système «1C: Entreprise 8. WMS Logistique. Gestion d'entrepôt 4» (qui dans cette partie fonctionnelle est ouvert), nous pouvons conclure ce qui suit. L'algorithme de compression des stocks met en œuvre une logique linéaire plutôt primitive, et il ne peut pas y avoir de véritable « compression optimale ». Évidemment, il ne prévoit pas la clusterisation des lots. Plusieurs clients ayant déployé ce système se sont plaints des résultats de la planification de la compression. Par exemple, il arrive souvent dans la pratique qu'en cas de compression, la situation suivante se produise : 100 pièces de stock d'un même emplacement sont prévues pour être déplacées vers un autre emplacement, où se trouve 1 pièce de produit, alors qu'il serait optimal, en termes de temps, de faire l'inverse.

La fonctionnalité de compression des stocks de produits dans les emplacements est également annoncée dans de nombreux systèmes étrangers, WMS-mais, malheureusement, nous n'avons ni retours réels sur l'efficacité des algorithmes (c'est un secret commercial), ni même une idée de la profondeur de leur logique (logiciel propriétaire à code fermé), nous ne pouvons donc pas juger.

Recherche d'un modèle mathématique du problème

Pour concevoir des algorithmes de qualité pour résoudre ce problème, il est nécessaire de formuler d'abord ce problème de manière précise sur le plan mathématique, ce que nous allons faire.

Il y a de nombreux emplacements , dans lesquels se trouvent des stocks d'un certain produit. Nous appellerons ces emplacements des emplacements-donneurs. Désignons le volume du produit se trouvant dans l'emplacement $.

Il est important de dire que dans la procédure de compression, peut participer uniquement un produit d'un seul lot, ou de plusieurs lots, préalablement regroupés en un cluster (lire l'article précédent), ce qui est dû aux spécificités du stockage et de la disposition des produits. Pour différents produits ou clusters de lots différents, une procédure de compression distincte doit être lancée.

Il y a de nombreux emplacements , dans lesquels les restes des emplacements-donneurs peuvent potentiellement être placés. Nous appellerons ces emplacements des emplacements-conteneurs. Cela peut être à la fois des emplacements vides dans l'entrepôt, ainsi que des emplacements-donneurs de nombreux . L'ensemble de est toujours un sous-ensemble de .

Pour chaque emplacement de l'ensemble des restrictions sur la capacité sont spécifiées , mesurés en dm3. Un dm3 représente un cube de 10 cm de côté. Les produits stockés dans l'entrepôt sont suffisamment grands, donc dans ce cas, cette discrétisation est tout à fait suffisante.

Une matrice des distances les plus courtes a été définie en mètres entre chaque paire de cellules , où et appartiennent à des ensembles et respectivement.

Désignons les « coûts » de déplacement des marchandises d'une cellule à une autre cellule . Dénommons les « coûts » du choix du conteneur pour y déplacer les restes d'autres cellules. La manière et les unités dans lesquelles les valeurs seront calculées et seront examinées plus loin (voir la section préparation des données d'entrée), pour l'instant, il suffit de dire que ces quantités seront directement proportionnelles aux quantités et respectivement.

Désignons par une variable prenant la valeur 1, si les restes de la cellule sont déplacés vers le conteneur , et 0 sinon. Dénommons par une variable prenant la valeur 1, si le conteneur contient des restes de marchandises, et 0 sinon.

Le problème est formulé comme suit: il est nécessaire de trouver un ensemble de conteneurs et de « lier » les cellules donneuses aux cellules conteneurs de manière à minimiser la fonction

sous contraintes

Au final, lors du calcul de la solution du problème, nous cherchons à :

• tout d'abord, économiser de la capacité de stockage ;
• ensuite, économiser le temps des magasiniers.

La dernière contrainte signifie que nous ne pouvons pas déplacer des marchandises dans un conteneur qui n'a pas été choisi, et nous n'avons donc pas « encouru de coûts » pour son choix. Cela signifie également que le volume des marchandises déplacées des cellules au conteneur ne doit pas dépasser la capacité du conteneur. La solution du problème consiste à comprendre l'ensemble des conteneurs et les moyens de relier les cellules donneuses aux conteneurs.

Une telle formulation du problème d'optimisation n'est pas nouvelle et a été étudiée par de nombreux mathématiciens depuis le début des années 80 du siècle dernier. Dans la littérature étrangère, il existe 2 problèmes d'optimisation avec un modèle mathématique approprié : Problème de localisation d'installation capacitaire à source unique et Problème de localisation d'installation capacitaire à sources multiples (Nous aborderons les différences entre les tâches plus tard.) Il convient de souligner que dans la littérature mathématique, la formulation de ces deux problèmes d'optimisation est exprimée en termes de localisation des entreprises, d'où le nom « Localisation des Installations ». En grande partie, c'est un hommage à la tradition, puisque le besoin de résoudre de tels problèmes combinatoires est d'abord venu du domaine de la logistique, principalement dans l'industrie militaro-industrielle des années 50 du siècle dernier. En termes de localisation d'entreprises, ces problèmes se formulent ainsi :

• Un ensemble fini de villes existe, où il est potentiellement possible de localiser des entreprises de production (ci-après villes-producteurs). Pour chaque ville-producteur, des coûts d'ouverture d'une entreprise y sont définis, ainsi qu'une limite sur les capacités de production de l'entreprise qui y sera ouverte.
• Un ensemble fini de villes existe, où se trouvent effectivement les clients (ci-après villes-clients). Pour chaque ville-client, un volume de demande pour le produit est défini. Pour simplifier, nous considérerons que le produit fabriqué par les entreprises et consommé par les clients est le même.
• Pour chaque paire ville-producteur et ville-client, une valeur des coûts de transport pour livrer le volume requis de produits du producteur au client est définie.

Il est nécessaire de déterminer dans quelles villes ouvrir des entreprises et comment attacher les clients à ces entreprises de manière à ce que :

• Les coûts totaux d'ouverture des entreprises et les coûts de transport soient minimaux ;
• Le volume de demande des clients attachés à une entreprise ouverte ne dépasse pas les capacités de production de cette entreprise.

Il est maintenant important de mentionner la seule différence entre ces deux problèmes classiques :

• Le Problème de Localisation des Installations à Capacité Unique – un client est Fournie exclusivement par une seule entreprise ouverte ;
• Le Problème de Localisation des Installations à Capacité Multiple – un client peut être Fournie simultanément par plusieurs entreprises ouvertes.

Cette différence entre les deux problèmes peut sembler insignifiante au premier abord, mais en réalité, elle conduit à des structures combinatoires très différentes pour ces problèmes et, par conséquent, à des algorithmes totalement différents pour les résoudre. La différence entre les problèmes est démontrée dans l'image ci-dessous.

Fig.3. a) Problème de Localisation des Installations à Capacité Multiple

Fig.3. b) Problème de Localisation des Installations à Capacité Unique

Les deux problèmes -difficiles, c'est-à-dire qu'il n'existe pas d'algorithme exact qui résoudrait un tel problème en temps polynomial par rapport à la taille des données d'entrée. Pour le dire plus simplement, tous les algorithmes exacts pour résoudre le problème fonctionneront en temps exponentiel, même s'ils peuvent être plus rapides qu'une recherche exhaustive. Puisque le problème -est difficile, nous allons donc nous concentrer uniquement sur des heuristiques approximatives, c'est-à-dire des algorithmes qui calculeront des solutions très proches des optimales et qui fonctionneront assez rapidement. Si cela vous intéresse, vous pouvez trouver ici un bon aperçu en russe.

Si l'on transpose à la terminologie de notre problème d'optimisation du stockage des produits dans les cellules, alors :

• les villes-clients – ce sont des cellules-donors avec des stocks restants,
• les villes-productrices – ce sont des cellules-conteneurs , dans lesquelles on prévoit de placer les restes provenant d'autres cellules,
• les coûts de transport – sont les coûts en temps du magasinier pour déplacer le volume de produits de la cellule-donor vers la cellule-conteneur ;
• les coûts d'ouverture de l'entreprise – sont les coûts de choix du conteneur , égaux au volume de la cellule-conteneur , multiplié par un certain coefficient d'économie d'espace libre (la valeur du coefficient est toujours > 1) (voir la section préparation des données d'entrée).

Après avoir établi l'analogie avec les livraisons classiques connues, il est nécessaire de répondre à une question importante, qui conditionne le choix de l'architecture de l'algorithme de solution : le transfert des restes de la cellule-donor est-il possible uniquement vers un seul conteneur (Single-Source), ou bien est-il possible de transférer les restes vers plusieurs cellules-conteneurs (Multi-Source) ?

Il convient de noter qu'en pratique, les deux formulations du problème existent. Nous allons exposer tous les « pour » et « contre » pour chaque formulation ci-dessous :

Tableau 1. Avantages et inconvénients des variantes Single-Source et Multi-Source.

Comme le nombre d'avantages de la variante Single-Source est plus élevé, et en tenant compte du fait que plus le stock dans les cellules sources est faible, moins la différence dans le degré de compacité des compressions calculées selon les deux variantes de tâches est importante, nous avons choisi la variante Single-Source.

Il convient de mentionner que la solution Multi-Source a aussi sa place. Il existe un grand nombre d'algorithmes efficaces pour sa résolution, dont beaucoup se résument à résoudre une série de problèmes de transport. Il existe également des algorithmes non seulement efficaces, mais aussi élégants, par exemple, ici.

Préparation des données d'entrée

Avant de procéder à l'analyse et au développement de l'algorithme pour résoudre le problème, il est nécessaire de déterminer quelles données et sous quelle forme nous allons les lui transmettre en entrée. Les volumes de stocks de produits dans les cellules sources et la capacité des cellules-containers ne posent pas de problème, car c'est trivial – de telles valeurs seront mesurées en m3, mais en ce qui concerne les coûts d'utilisation de la cellule-container et la matrice des coûts de déplacement, ce n'est pas si simple !

Commencez par examiner le calcul coûts de déplacement des marchandises d'une cellule-donatrice à une cellule-conteneur. Tout d'abord, il est nécessaire de décider dans quelles unités de mesure nous allons calculer les coûts de déplacement. Les deux options les plus évidentes sont les mètres et les secondes. Il est sans objet de calculer les coûts de déplacement en mètres 'purs'. Illustrons cela par un exemple. Supposons que la cellule soit située au premier niveau, et que la cellule soit à 30 mètres au-dessus et située au deuxième niveau :

• Le déplacement depuis dans est plus coûteux que le déplacement depuis dans , car abaisser d'un niveau (1,5-2 mètres du sol) est plus facile que de soulever à partir du deuxième niveau, même si la distance parcourue est identique ;
• Déplacer 1 pièce de produit depuis la cellule dans sera plus facile que de déplacer 10 pièces du même produit, bien que la distance parcourue soit identique.

Il est préférable de prendre en compte les coûts de déplacement en secondes, car cela permet de prendre en compte à la fois la différence de niveaux et la différence dans la quantité de produits déplacés. Pour tenir compte des coûts de déplacement en secondes, nous devons décomposer l'opération de déplacement en ses éléments fondamentaux et chronométrer le temps nécessaire pour exécuter chaque élément.

Supposons que depuis la cellule se déplace pièces de produit dans le conteneur . Supposons que soit la vitesse moyenne de déplacement d'un travailleur dans l'entrepôt, mesurée en m/s. Supposons que et soient les vitesses moyennes d'exécution des opérations de prise et de dépôt respectivement pour un volume de produit égal à 4 dm3 (volume moyen que prend un employé à l'entrepôt lors de l'exécution des opérations). Supposons que et soient les hauteurs des cellules à partir desquelles les opérations de prise et de dépôt sont effectuées respectivement. Par exemple, la hauteur moyenne du premier niveau (sol) est de 1 m, le deuxième niveau est de 2 m, etc. Alors la formule pour calculer le temps total nécessaire pour exécuter l'opération de déplacement est la suivante :

Le tableau 2 présente les statistiques concernant le temps d'exécution de chaque opération élémentaire, recueillies par les employés de l'entrepôt en tenant compte des spécificités des marchandises stockées.

Dénomination de l'opération	Notation	Valeur moyenne
Vitesse moyenne de déplacement d'un employé dans l'entrepôt		1,5 m/s
Vitesse moyenne d'exécution d'une opération de dépôt (pour un volume de produit de 4 dm3)		2,4 sec

Tableau 2. Temps moyen d'exécution des opérations d'entrepôt

Nous avons défini la méthode de calcul des coûts de déplacement. Maintenant, il est nécessaire de déterminer comment calculer les coûts liés au choix de la cellule-conteneur.C'est beaucoup plus compliqué ici que les coûts de transport, car :

• tout d'abord, les coûts doivent être directement liés au volume de la cellule – le même volume de stocks déplacés des cellules donneuses doit être mieux placé dans un conteneur de plus petit volume que dans un grand conteneur, à condition que ce volume puisse être entièrement contenu dans les deux conteneurs. Ainsi, en minimisant les coûts globaux de sélection des conteneurs, nous cherchons à économiser les capacités d'entreposage « déficientes » dans la zone de prélèvement, pour effectuer les opérations ultérieures de placement des marchandises dans les cellules. La figure 4 illustre les options de déplacement des stocks dans des conteneurs de grande et de petite taille et les conséquences de ces options de déplacement lors de l'exécution des opérations d'entrepôt ultérieures.
• Deuxièmement, puisque nous devons minimiser les coûts globaux dans la solution du problème initial, qui sont la somme des coûts de transport et des coûts de sélection des conteneurs, il est nécessaire de corréler les volumes des cellules en mètres cubes avec des secondes, ce qui n'est pas trivial.

Fig. 4. Options de déplacement des stocks dans des conteneurs de différentes capacités.

Dans la figure 4, le volume des stocks qui ne peut plus être contenu dans le conteneur à la deuxième étape de placement des marchandises est illustré en rouge.

Les exigences suivantes pour les solutions calculées du problème aideront à relier les mètres cubes de coûts de sélection de conteneurs avec les secondes de coûts de transport :

• Il est nécessaire que les stocks de la cellule donneuse soient déplacés vers la cellule conteneur dans tous les cas, si cela réduit le nombre total de cellules conteneurs dans lesquelles se trouvent les marchandises.
• Il est important de maintenir un équilibre entre les volumes des conteneurs et le temps nécessaire pour le transport : par exemple, si dans la nouvelle option de solution par rapport à l'option précédente, le gain en volume est important, mais la perte en temps est faible, alors il faut choisir la nouvelle option.

Commençons par la dernière exigence. Pour préciser le mot ambigu « équilibre », nous avons mené une enquête auprès du personnel de l'entrepôt pour déterminer ce qui suit. Supposons qu'il y ait un conteneur de volume , dans lequel le déplacement des stocks des cellules donneuses est prévu et le temps total de ce déplacement est égal à . Supposons qu'il y ait plusieurs options alternatives pour le placement de la même quantité de marchandises des mêmes cellules donneuses dans d'autres conteneurs, où chaque placement a ses propres évaluations. , où < et , où >.

La question se pose : quel est le gain minimum en volume acceptable, pour une perte de temps donnée ? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagramme de la dépendance de l'économie minimale acceptable en volume par rapport à l'augmentation de la différence de temps d'exécution de l'opération.

C'est-à-dire que si les coûts supplémentaires en temps s'élèvent à 40 secondes, nous sommes prêts à les accepter seulement si le gain en volume est d'au moins 500 dm3. Bien qu'une légère non-linéarité soit observée dans la dépendance, pour la simplicité des calculs ultérieurs, nous considérerons que la relation entre les grandeurs est linéaire et décrite par une inégalité.

Sur le dessin ci-dessous, nous examinerons les différentes méthodes de placement des marchandises dans les conteneurs.

Fig. 6. Option (a) : 2 conteneurs, volume total 400 dm3, temps total 150 sec.

Fig. 6. Option (b) : 2 conteneurs, volume total 600 dm3, temps total 190 sec.

Fig. 6. Option (c) : 1 conteneur, volume total 400 dm3, temps total 200 sec.

L'option (a) de sélection des conteneurs est plus préférable que l'option initiale, car l'inégalité est satisfaite : (800-400)/10 >= 150-120 d'où il s'ensuit que 40 >= 30. L'option (b) est moins souhaitable que l'option initiale, car l'inégalité n'est pas satisfaite : (800-600)/10 >= 190-150 d'où il s'ensuit que 20 >= 40. Mais l'option (c) ne s'inscrit pas dans cette logique ! Examinons cette option plus en détail. D'une part, l'inégalité (800-400)/10 >= 200-120, ce qui signifie que l'inégalité 40 >= 80 n'est pas satisfaite, ce qui indique que le gain en volume ne vaut pas une telle perte de temps.

Mais d'autre part, dans cette option (c), nous ne réduisons pas seulement le volume total occupé, mais nous diminuons également le nombre de cellules occupées, ce qui est la première des deux exigences importantes pour les solutions calculées des problèmes mentionnés ci-dessus. Il est évident que pour que cette exigence soit remplie, il est nécessaire d'ajouter une certaine constante positive au côté gauche de l'inégalité. , et cette constante doit être ajoutée uniquement lorsque le nombre de conteneurs diminue. Rappelons que — est une variable égale à 1 lorsque le conteneur est sélectionné, et 0 lorsque le conteneur non sélectionné. Désignons, – un grand nombre de conteneurs dans la solution initiale et – un grand nombre de conteneurs dans la nouvelle solution. En termes généraux, la nouvelle inégalité se présentera comme suit :

En transformant l'inégalité ci-dessus, nous obtenons

À partir de cela, nous avons une formule pour calculer le coût total d'une certaine variante de la résolution du problème :

Mais maintenant, la question se pose: quelle valeur doit avoir cette constante ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Soit – la distance maximale entre les cellules d'un entrepôt dans une zone ABC, qui est ici de 100 m. Soit – le volume maximal d'une cellule-conteneur dans l'entrepôt, qui est ici de 1000 dm3.

Première méthode de calcul de la taille . Considérons la situation où il y a 2 conteneurs au premier niveau, dans lesquels se trouve déjà physiquement la marchandise, c'est-à-dire qu'ils sont eux-mêmes des cellules-donateurs, et que les coûts de déplacement des marchandises vers ces mêmes cellules sont, naturellement, égaux à 0. Il est nécessaire de trouver une telle valeur pour la constante , pour laquelle il serait toujours avantageux de déplacer les restes du conteneur 1 vers le conteneur 2. En substituant les valeurs et dans l'inégalité donnée ci-dessus, nous obtenons :

ce qui implique

En substituant les valeurs du temps moyen d'exécution des opérations élémentaires dans la formule ci-dessus, nous obtenons

Deuxième méthode de calcul de la taille . Considérons la situation où il y a cellules-donateurs desquelles il est prévu de déplacer des marchandises vers le conteneur 1. Désignons – la distance de la cellule-donateur au conteneur 1. Il y a aussi le conteneur 2, qui contient déjà des produits, et dont le volume permet d'accueillir les restes de toutes les cellules. Pour simplifier, nous supposerons que le volume des marchandises déplacées des cellules-donateurs vers les conteneurs est le même et égal à . Il est nécessaire de trouver une telle valeur pour la constante , pour laquelle le placement de tous les restes des cellules dans le conteneur 2 serait toujours plus avantageux que de les placer dans différents conteneurs :

En transformant l'inégalité, nous obtenons

Pour 'renforcer' la valeur de la taille , supposons que = 0. Le nombre moyen de cellules généralement impliquées dans la procédure de compression des restes dans l'entrepôt est de 10. En substituant les valeurs connues des grandeurs, nous avons la valeur de la constante suivante

Prenons la plus grande valeur, calculée pour chaque variante, c'est cela qui sera la valeur de la taille pour les paramètres donnés de l'entrepôt. Maintenant, pour être complet, écrivons la formule de calcul des coûts totaux pour une certaine solution acceptable :

Voilà, maintenant, après tous les efforts titanesques de transformation des données d'entrée, nous pouvons dire que toutes les données ont été converties au format requis et sont prêtes à être utilisées dans l'algorithme d'optimisation.

Conclusion

Comme le montre la pratique, la charge de travail et l'importance de l'étape de préparation et de transformation des données d'entrée pour l'algorithme sont souvent sous-estimées. Dans cet article, nous avons consacré beaucoup d'attention à cette étape pour montrer que seules des données d'entrée préparées de manière qualitative et intelligente peuvent rendre les solutions calculées par l'algorithme véritablement précieuses pour le client. Oui, il y a eu beaucoup de conclusions de formules, mais nous vous avions prévenus bien avant le kata 🙂

Dans le prochain article, nous aborderons enfin ce pourquoi les 2 publications précédentes ont été conçues - l'algorithme d'optimisation discrète.

Article préparé par
Roman Shangin, programmeur au département des projets,
entreprise Premier Bit, ville de Tcheliabinsk

Source : habr.com