A simulated annealing approach for the circular cutting problem

Mhand Hifi*, CERMSEM et PRiSM
Vangelis Th. Paschos**, LAMSADE
Vassilis Zissimopoulos***, LIPN

Résumé. Dans cet article, nous proposons un algorithme approché pour la résolution du problème de découpe circulaire. Nous traitons les deux versions du problème : le cas contraint et non-contraint. L'algorithme proposé s'appuie sur la méthode du recuit simulé. Dans un premier temps, nous avons présenté le problème en terme de système dynamiqueprincipalement caractérisé par une fonction énergie. Cette fonction est composée de facteurs de pénalisationqui reflètent les contraintes du problème et qui forcent les pièces circulaires à se concentrer dans le coin bas-gauchedu support initial. Les grandes valeurs de la fonction énergiecorrespondent aux configurations pour lesquelles beaucoup de pièces circulaires se chevauchent mutuellement où dépassent les arêtes du support initial ; alos que les petites valeurs de la fonction énergiecorrespondent aux configurations dont les chevauchements ou les dépassement sont totalement éliminés. La performance de la méthode proposée est évaluée sur (i) un ensemble d'instances générées aléatoirement et (ii) un autre ensemble d'instances de la littérature. Notre méthode donne des résultats très satisfaisant comparée aux résultats produits par différentes approches de la littérature.
Mots clés : Découpe, heuristiques, optimisation, recuit simulé.

Abstract. We propose a heuristic for the constrained and the unconstrained circular cutting problem based upon simulated annealing. We define an energy, the small values of which provide a good concentration of the circular pieces on the left bottom corner of the initial rectangle. Such values of the energy correspond to configurations where pieces are placed in the rectangle without overlapping. Appropriate software has been devised and computational results and comparisons with some other algorithms are also provided and discussed.
Keywords : Cutting, heuristics, optimization, simulated annealing.

JEL Classification : C44, C61, C63.

*PRiSM, Université de Versailles Saint Quentin en Yvelines, 45 Avenue des Etats-Unis, 78035 Versailles cedex, France.
**LAMSADE, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.
***LIPN, Université Paris XIII, Avenue Jean-Baptiste Clément, 93430 Villetaneuse, France.