Une Heuristique pour le Placement de Sphères dans un Container

Session : SS16-2 / SS16 : Résolution parallèle des problèmes mono ou multi objectifs (continu et/ou combinatoire)
Vendredi 12 février 10:30 - 11:50 Salle : RP9
Yousef Labib et Hifi Mhand

Nous nous intéressons à la résolution du Problème de Placement de Sphères (noté PPS) dans un container en trois dimensions. Une instance de PPS est représentée par un ensemble $N$ de $n$ d'items (sphères), où chacune des sphères est caractérisée par son rayon, et le container par ses dimensions $(L,W,H)$. Le but du problème est de placer un nombre maximum de sphères dans le container de sorte à maximiser le volume du container. Notons que dans une version plus général, chacune des sphères peut être représentée par un poids (ou un score) et le but revient à maximiser le poids des sphères placées. Dans ce travail, nous proposons une heuristique qui principalement s'appuie sur la coopération enter une recherche simple gloutonne et une recherche par troncature dans un arbre de recherche.

Mots clés : heuristic, placement, recherche tronquée