Approche hybride pour résoudre des problèmes réels

Rapports scientifiques volume 13, Numéro d'article : 11777 (2023) Citer cet article

418 accès

2 Altmétrique

Détails des métriques

Ranger efficacement les articles dans les bacs est une tâche quotidienne courante. Connu sous le nom de Bin Packing Problem, ce problème a été étudié de manière intensive dans le domaine de l’intelligence artificielle, grâce au large intérêt de l’industrie et de la logistique. Depuis des décennies, de nombreuses variantes ont été proposées, le problème tridimensionnel Bin Packing étant le plus proche des cas d’utilisation réels. Nous introduisons un cadre hybride quantique-classique pour résoudre les problèmes tridimensionnels réels d'emballage de bacs (Q4RealBPP), en considérant différentes caractéristiques réalistes, telles que : (1) les dimensions du colis et du bac, (2) les restrictions de surpoids, (3) les affinités entre catégories d'articles et (4) préférences pour la commande d'articles. Q4RealBPP permet de résoudre des cas de 3 dBPP orientés vers le monde réel, en tenant compte des restrictions bien appréciées par les secteurs industriels et logistiques.

L'optimisation du conditionnement des produits dans un nombre fini de contenants est une tâche quotidienne cruciale dans le domaine de la production et de la distribution. En fonction des caractéristiques des emballages et des conteneurs, de multiples problèmes d'emballage peuvent être formulés, généralement appelés Bin Packing Problems (BPP)1. Dans cette catégorie, le BPP unidimensionnel (1 dBPP) est considéré comme le plus simple2, dont le but est de regrouper tous les éléments dans le moins de conteneurs possible. De nombreuses variantes avec un nombre variable de contraintes ont été proposées pour faire face à des situations réelles en logistique et en industrie3. Le BPP tridimensionnel (3 dBPP)4, dans lequel chaque boîtier a trois dimensions : hauteur, largeur et profondeur, est la variante la plus connue et la plus complexe. Mis en avant dans plusieurs études5,6,7, le 3 dBPP présente un intérêt pratique dans de nombreux contextes industriels. Ces dernières années, il a été formulé pour posséder des applications diverses et pratiques telles que le chargement de palettes8, le transport routier9, le fret aérien10, etc. En raison de sa complexité, 3 dBPP est également utilisé de manière récurrente comme référence pour tester des méthodes et des mécanismes nouvellement développés11,12. .

Sur un autre front, l’informatique quantique en est encore à ses débuts mais a suscité beaucoup d’attention de la part de la communauté scientifique car elle offre aux chercheurs et aux praticiens un paradigme révolutionnaire pour aborder différents types de problèmes pratiques d’optimisation13,14,15,16. En particulier, les recuits quantiques ont été récemment appliqués à une grande variété de problèmes d’optimisation inspirés des domaines de l’industrie17, de la logistique18 et de l’économie19. Cependant, les recherches sur le BPP menées dans la communauté quantique sont encore rares, même si le BPP a été largement étudié classiquement en tant que problème d’optimisation.

Le travail pionnier sur le BPP dans le domaine de l'informatique quantique présente une méthode hybride quantique-classique pour résoudre le 1 dBPP20, dont le solveur est composé de deux modules : (1) un sous-programme quantique avec lequel rechercher un ensemble de configurations réalisables pour en remplir une. bac unique et (2) une heuristique informatique classique qui construit des solutions complètes en utilisant les sous-ensembles donnés par le sous-programme quantique. Pour approfondir les performances du sous-programme quantique développé, des tests supplémentaires ont été menés sur un échantillonnage aléatoire et une heuristique basée sur la marche aléatoire21. Outre ces deux articles, une étude supplémentaire formule un problème lié à l’industrie de l’énergie atomique comme étant de 1 dBPP, le résolvant à l’aide du recuit quantique D-Wave22. D'autres travaux montrent des techniques de calcul évolutives d'inspiration quantique comme alternative pour résoudre les problèmes liés au BPP23,24,25. Les techniques d'inspiration quantique constituent une classe spécifique d'algorithmes évolutionnaires qui utilisent la physique quantique pour définir leurs opérations et sont conçus pour être exécutés sur un ordinateur classique26. Ainsi, ils ne peuvent être exécutés sur aucune machine quantique.

Contrairement à 1 dBPP, aborder 3 dBPP dans le domaine quantique est beaucoup plus difficile en raison de deux raisons liées : (1) sa complexité, qui augmente à mesure que les contraintes du monde réel sont prises en compte et (2) l'état naissant de développement des ordinateurs quantiques commerciaux actuels, dont les capacités sont encore limitées par la décohérence et les erreurs, ce qui pourrait constituer un obstacle à la résolution de problèmes très contraints. Dans cet article, nous présentons un cadre informatique hybride quantique-classique pour le 3 dBPP orienté monde réel, appelé Quantum for Real Bin Packing Problem (Q4RealBPP). Le cadre proposé fait appel au solveur hybride Leap Constrained Quadratic Model (CQM) (LeapCQMHybrid27) de D-Wave. Dans le même temps, Q4RealBPP est construit sur un code existant28. Ce code de référence est un excellent point de départ, qui a ouvert la voie à ces deux contributions principales développées dans ce travail :