Comment nous avons sélectionné le fret pour les transporteurs

Bonne après-midi. Notre nom est Ilya Bashtanov (développeur, Tochka-Tochka ) et Tatyana Voronova (analyste de données, 2M Center ). Et nous voulons parler de la mise en œuvre technique de la tâche de sélection des marchandises à transporter.

L'essence du problème est la suivante. Il y a des marchandises dans l'entrepôt qui doivent être transportées de la ville A à la ville B. On peut supposer que seul le poids des marchandises est pris en compte, et leurs tailles sont plus ou moins standard (euro palettes). Un transporteur qui souhaite prendre un fret de passage souhaite transporter autant que possible, mais est limité par le poids et le nombre de colis. Il faut lui former plusieurs variantes des lots à partir des marchandises disponibles à l'entrepôt.

Tâches résolues pour les entreprises dans ce cas:

1. Chargez les véhicules aussi efficacement que possible et augmentez ainsi les revenus de transport.
2. Résoudre le problème de livraison dans un délai acceptable pour l'utilisateur (y compris le principe FIFO).

Le projet parut immédiatement attractif. D'abord, du point de vue des mathématiques: il a été proposé de mettre en œuvre un algorithme pour résoudre le problème classique d'optimisation combinatoire. Deuxièmement, PostgreSQL a été proposé en tant que SGBD, dont la popularité n'a cessé de croître ces dernières années en raison d'un grand nombre de fonctionnalités, de fiabilité et de bonnes performances. Et, bien sûr, l'importance de la tâche pratique et l'ampleur du projet, qui impliquait de nombreux participants différents, sont également devenues une grande incitation.

Algorithme

Cette tâche est une variante du problème classique d' emballage de sac à dos . Le problème de sac à dos est NP-complet . De tels problèmes ne peuvent pas être résolus en temps polynomial, bien que cela ne soit pas encore prouvé mathématiquement. Cela signifie que les algorithmes exacts, tels que la recherche exhaustive de variantes ou de ses variétés optimisées, ne fonctionnent pas dans la pratique, car ils sont complexes$$ . Les méthodes approximatives fournissent des solutions pour le meilleur moment. Par exemple, l'algorithme gourmandsuppose que le poids maximum est placé dans le sac à dos aussi longtemps que possible. Sa complexité ne dépasse pas la complexité du tri$O(2^n)$$$ , mais le résultat peut être loin d'être optimal. Il existe encore une classe d'algorithmes génétiques qui donnent de bons résultats dans un temps limité, mais ils ne sont pas déterministes, ce qui dans notre cas conduirait à différentes options pour l'émission lors d'appels répétés, il serait difficile d'expliquer au client et aux transporteurs. En conséquence, le choix s'est porté sur desméthodes approximativesqui donnent le résultat avec une précision garantie en temps polynomial. Donc nous avons:$(O(n * log n))$

• Poids avec poids $$$w_1,w_2,... , w_n$
• Limite du poids total des marchandises $$$W_\max$
• Limite de chargement $$$Q_\max$

Il est nécessaire de trouver un sous-ensemble de marchandises dont le poids total maximum satisfait aux contraintes.

L'idée est de réduire la variété des produits en grossissant leurs poids et d'appliquer l'algorithme gourmand. Dans ce cas, la solution approximative est trouvée dans un temps complètement polynomial, c'est-à-dire une solution avec une précision garantie$$$1- \varepsilon$ obtenu avec la complexité étant un polynôme dans $$$n$et $$$\varepsilon$.

À l'entrée de l'algorithme, nous avons une plaque contenant les poids arrondis des marchandises et le nombre de sièges pour chaque poids. En utilisant un algorithme gourmand, nous essayons d'obtenir des options de style pour les poids totaux$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. Pour ce faire, après avoir défini le poids total cible, dans le cycle, nous sélectionnons le poids maximal de la cargaison parmi les charges restantes afin de ne pas dépasser le poids total cible. Si le montant maximum autorisé est atteint$$$Q_\max$, le cycle se termine. Les combinaisons résultantes sont stockées dans un tableau temporaire.

Le nombre de combinaisons possibles peut être important et il est commode pour l'utilisateur de choisir parmi un petit nombre d'options, mais en même temps, il devrait toujours y avoir un choix. Une tâche supplémentaire se pose de choisir les combinaisons préférées. Afin de ne pas compliquer les choses, nous avons décidé de toujours proposer deux options, si possible. Pour un entrepôt, il est tout d'abord conseillé d'envoyer les charges les plus lourdes, nous classons donc les combinaisons par ordre décroissant du plus grand poids de la cargaison. Si les combinaisons avec le poids maximum maximum sont supérieures à deux, nous en donnons deux: avec la plus grande et la plus petite quantité de marchandises.

Les tests

Pour les tests, nous avons sélectionné deux implémentations de l'algorithme considéré, qui diffèrent par des détails insignifiants: l'une en Java, l'autre en PL / pgSQL, le langage procédural du SGBD PostgreSQL. Il convient de noter tout de suite que le choix final a été influencé non seulement par les résultats des tests, mais également par des considérations architecturales, la convivialité et d'autres facteurs. Mais d'abord, la tâche consistait à choisir l'une des deux implémentations.

Deux environnements de test ont été utilisés: un bureau pour tester le développement et un serveur pour tester dans des conditions similaires à celles réelles.

• dev: station client HP Probook 4740s + 32 bits 2 x Pentium® Dual-Core CPU E5300 @ 2,60 GHz et 4 Go de RAM, Ubuntu Linux 16.04, PostgreSQL 10.3.
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

Une table de test a été préparée dans la base de données PostgreSQL contenant 7000 charges avec des poids aléatoires de 20 à 800 kg. Pour les tests, nous avons utilisé l'utilitaire pgBench standard de PostgreSQL, qui pendant le test a effectué 500 transactions (10 connexions de 50 transactions chacune). Chaque transaction a fait appel à l'algorithme avec des paramètres aléatoires (restriction sur le poids de 10 à 1000 kg et sur le nombre de marchandises de 1 à 50 pièces). Toutes les variables aléatoires sont réparties uniformément.

Pour le premier algorithme, chaque transaction a démarré une machine Java et lui a transmis une archive JAR avec le code de l'algorithme pour exécution. La classe Java principale connectée à la base de données via le pilote JDBC, a reçu les données de test de la table et leur a appliqué l'algorithme.

Pour le deuxième algorithme, chaque transaction a effectué un appel à la fonction stockée de la base de données PostgreSQL, qui a lu les données de test de la table et appliqué l'algorithme.

Tableau 1. Résultats du test principal



En plus du test principal, dont les résultats sont présentés dans le tableau 1, un test supplémentaire de l'algorithme 2 a été effectué, dans lequel différentes options pour obtenir les données initiales ont été comparées: à partir d'une base de données, à partir d'un fichier, génération de tableaux aléatoires. Il s'est avéré que pour 7000 chargements, le transfert de données d'un SGBD vers une baie locale nécessite plus de temps que l'algorithme d'empilement réel.

Résultats.

1. Dans notre tâche, les performances dépendent davantage de l'architecture du système et de la vitesse d'interaction avec la base de données que de l'algorithme utilisé. Cela est confirmé par un test supplémentaire de l'algorithme 1, dans lequel la sélection des données de la base de données a pris la majeure partie du temps.
2. L'option 2 évolue légèrement mieux, apparemment en raison d'exigences de RAM plus modestes (des tables de base de données temporaires sont utilisées pour stocker les résultats intermédiaires).

En conséquence, le deuxième algorithme a été choisi, qui, avec des modifications mineures, a été utilisé pour la deuxième année. En conséquence, une solution est recherchée avec une précision acceptable avec un temps de transaction moyen inférieur à 1 seconde.

Exploitation

Comme toujours, la vie a fait des ajustements et j'ai dû peaufiner la mise en œuvre.

En réalité, le transporteur réserve l'envoi dans une vente aux enchères Yankee avec un prix flottant. À strictement parler, cette option de vente aux enchères ne l'est pas, mais c'est le sujet d'une conversation distincte sur un autre site. En plus du poids maximal de la cargaison et de la quantité maximale, le transporteur définit deux villes (début et fin de l'itinéraire) et l'heure de chargement souhaitée. Après cela, la procédure de sélection pour chaque paire d'entrepôts (dans la ville de départ et la ville de destination) filtre les cargaisons selon plusieurs critères, en particulier, en tenant compte des heures de travail de l'entrepôt et du coût maximal de transport, auquel les coûts sont toujours couverts par le paiement de l'expéditeur et transfère leurs poids à l'algorithme d'emballage. À la sortie de l'algorithme, une liste de poids est obtenue, selon laquelle des ensembles de marchandises spécifiques sont sélectionnés, qui sont émis en tant qu'offre aux enchères.

Initialement, les poids ont été arrondis à des valeurs qui sont des multiples de 10 kg. Pendant le fonctionnement, il est devenu clair que la précision en souffre sensiblement, et les résultats commencent à contredire le bon sens, par exemple, en présence de marchandises pesant 12 et 19 kg, le système peut choisir le premier. Les balances d'entrepôt donnent des données avec une précision de 1 kg, et pour le volume et la charge actuels, les performances de l'algorithme pour les valeurs entières des balances se sont avérées tout à fait acceptables, ils ont donc refusé l'arrondi. À l'avenir, avec une augmentation du nombre de livraisons, il est prévu d'utiliser l'arrondi à des valeurs qui sont des multiples de 5 kg.

La surcharge pour le fonctionnement de l'algorithme d'empilement avec le volume de données et l'intensité de requête actuels n'est pas critique. Beaucoup plus de ressources sont nécessaires au stade de la sélection du fret, ainsi que pour les autres processus d'exploitation du système.

Constatations commerciales

La mission du Point-Point est un processus logistique efficace, en particulier, l'utilisation optimale du véhicule en termes d'encombrement: lors du transport d'un minimum de vides.

Les objectifs mondiaux de résolution des problèmes d'optimisation du transport de marchandises: économiser des ressources contribue à la croissance économique, crée des opportunités supplémentaires pour les petites et moyennes entreprises et améliore l'environnement.

Les spécialistes du Centre 2M et de Tochka-Tochki ont trouvé une solution mathématique logicielle adaptée à tous les participants au processus de transport. Il peut être utilisé pour le réseau fédéral, à chaque point duquel 7 000 palettes (correspondant à la taille du terrain de football) sont demandées par 500 transporteurs et avec le résultat obtenu en moins d'une seconde.

Auteurs de l'article: Ilya Bashtanov (i-bash), Tatyana Voronova (tvoronova)