A generic algorithm-based heuristic for constrained circular cutting problems

Mhand Hifi*, LaRIA et CERMSEM
Rym M'Hallah**, ISG - Sousse

Résumé. Dans cet article, nous étudions le problème de découpe circulaire. Une instance du problème est caractérisée par une plaque rectangulaire R de dimensions (L,W) et d'un ensemble de n types de pièces circulaires. Chaque type de pièce i est représenté par son rayon r_i , i = 1,...,n, et par sa demande d_i (une borne supérieure sur le nombre d'apparitions de la pièce du type i dans un plan de découpe). Nous proposons deux méthodes approchées pour la résolution du problème de découpe circulaire. Les méthodes proposées s'appuient principalement sur la recherche du meilleur ordre de placement des pièces et utilisent une adaptation de la procédure de la recherche de la meilleure position locale (proposée dans Hifi et M'Hallah [13]) afin d'identifier le meilleur sous-plan de découpe associé à l'ordre prédéfinit. La procédure de positionnement a été revisitée vu la spécificité du problème étudié. Les deux méthodes sont comparées aux meilleures approches de la littérature.
Mots-clés : Meilleure position locale, découpe circulaire, optimisation combinatoire, algorithmes génétique, heuristiques.

Abstract. In this paper, we study the problem of cutting a rectangular plate R of dimensions (L,W) into as many circular pieces as possible. The circular pieces are of n different types with radii r_i , i = 1,...,n. We solve the constrained circular problem, where d_i the maximum demand for piece type i is specified, using two heuristics : a constructive procedure based heuristic and a genetic algorithm based heuristic. Both of these approaches search for a good ordering of the pieces and use an adaptation of the best local position procedure [13] to find the "best" layout of this ordered set. This positioning procedure is specifically tailored to circular cutting problems. It acts, for constrained problems, as one of the mutation operators of the genetic algorithm. We compare the performance of both proposed approaches to that of existing approximate and exact algorithms on several problem instances taken from the literature. The computational results show that the proposed approaches produce high-quality solutions within reasonable computational times. The genetic algorithm based heuristic is easily parallelizable ; one of its important features to be investigated in the near future.
Keywords : Best local position, circular cutting problem, combinatorial optimization, genetic algorithms, heuristics.

JEL Classification : C44, C61, C63.

*LaRIA, Laboratoire de Recherche en Informatique d'Amiens, 5 rue du Moulin Neuf, 80000 Amiens.
**Department of Quantitative Methods, ISG de Sousse, B.P. 763, Sousse 4000, Tunisia