Comment découper un maximum de fenêtres de tailles différentes dans un minimum de plaques de verre, tout en garantissant un minimum de pertes ? Si elle s’apparente à un casse-tête ludique, la question n’a rien d’un jeu. C’est même un réel problème d’optimisation industrielle qui a poussé Saint-Gobain, spécialisé dans la production, la transformation et la distribution de matériaux, à le soumettre aux meilleurs scientifiques dans le cadre du Challenge ROADEF 2018.
Tous les 2 ans depuis 20 ans, le challenge ROADEF propose un sujet à la communauté des chercheurs, en partenariat avec un industriel. Il s’agit la plupart du temps de créer un programme informatique pour résoudre une problématique de logistique industrielle. Pour les industriels, ce challenge est l’occasion d’avoir une meilleure perception des développements récents dans le domaine de la Recherche Opérationnelle, et pour les candidats, de se confronter à des problèmes industriels scientifiquement intéressants.
Florian Fontan, diplômé de
Grenoble INP – Ensimag, et Luc Libralesso, diplômé de
Polytech Grenoble, tous deux en doctorat au sein de l'équipe ROSP (Recherche Opérationnelle pour les Systèmes de Production) du
laboratoire G-SCOP, ont eu envie de relever le défi proposé par Saint-Gobain en février 2018.
Et ce ne fut pas une mince affaire. Outre les problèmes de « packing » classiques, qui consistent à satisfaire toutes les demandes en utilisant le moins de plaques possible, se rajoutent de nombreuses contraintes spécifiques, rendant le problème beaucoup plus complexe. «
Ici typiquement, il faut éviter les défauts éventuellement présents dans le verre, et dont la position varie en fonction des plaques, expliquent les doctorants. Mais il y a aussi des contraintes techniques, comme celle liée à la nécessité de respecter une distance minimale des bords, ou encore celles liées à l’utilisation de la coupe guillotine, qui impose de faire une entaille sur toute la longueur de la pièce. »
Complémentaires dans leurs expertises, les deux jeunes chercheurs ont proposé un programme original basé sur des algorithmes de recherche arborescente. Extrêmement performante, leur solution leur a permis de devancer toutes les autres équipes, y compris des chercheurs experts, et de remporter haut la main le premier prix du concours.
*CNRS, Grenoble INP, UGA
