Hakim Akeb (Laboratoire de Recherche en Informatique d'Amiens)

Le Placement de cercles (identiques ou non-identiques) dans des containers de différentes formes est un problème qu’on rencontre dans beaucoup de domaines (Découpe, Transport, fibres optiques, …). Le calcul des placements les plus denses est NP-Complet.

Nous proposons des heuristiques de base pour résoudre ces différents problèmes. Une heuristique de base est implémentée à travers un algorithme glouton qui définit une (des) règle(s) permettant de séletionner la position du prochain cercle à chaque étape.

Nous proposons d’abord une heuristique appelée “Degré Maximum de Trou” (Maximum Hole Degree, MHD) pour le problème du placement de cercles identiques dans le rectangle. Cette heuristique consiste à calculer la largeur minimale du container rectangulaire (dont la hauteur est fixée) afin d’y placer tous les cercles sans chevauchement. MHD obtient actuellement les meilleurs résultats de la littérature sur des instances connues (instances de Stoyan & Yaskov).

Pour le problème du placement de cercles identiques dans le cercle, les approches qui donnent actuellement les meilleurs résultats sont de type stochastique comme la “Simulation de Billard” (BS) dont les résultats pour placer jusqu’à 500 cercles sont connus. L’inconvénient de telles méthodes est que le temps de calcul explose avec le nombre de cercles à placer. Il faut des semaines sinon des mois pour s’assurer que la solution ne peut plus àªtre améliorée. Nous proposons une heuristique de base, appelée “Dommage Minimum” (Minimum Damage, MinD) pour placer un grand nombre de cercles identiques dans le cercle (plusieurs milliers). Les résultats de MinD ont été comparés avec ceux obtenus par différentes méthodes connues dans la litérature. Les résultats expérimentaux ont montré que notre approche obtient des résultats avec un bon rapport entre la qualité des solutions et le temps de calcul.

Enfin, nous proposons une coopération entre les deux heuristiques (MHD et MinD) pour résoudre le problème du placement de cercles identiques dans le cercle sur des instances contenant des proportions différentes de cercles identiques et non-identiques. L’heuristique obtenue s’appelle “Dommage Nul MHD” (Null-Dammage MHD, NDMHD).

Mots clés : Circle packing, Heuristiques, Algorithmes gloutons, Optimisation combinatoire.