This paper concerns the problem to place N non overlapping circles in a circular container with minimum radius. This is a well known and widely studied problem with applications in manufacturing and logistics and, in particular, to problems related to cutting and packing. In this paper we propose an algorithm that by applying a strength along a selected direction on each circle, simulates the shifting of circles on the plane and tries to reduce the radius of the circular container during this movements. The algorithm is based on a multistart technique where the starting solutions are produced by a tabu search heuristic that uses also the current best solution. The algorithm takes part in a public international contest in order to find optimal solutions to a special case in circle packing. The contest saw the participation of 155 teams and our algorithm achieved the tenth position

A Tabu Search Approach for the Circle Packing Problem

CARRABS, FRANCESCO;CERRONE, CARMINE;CERULLI, Raffaele
2014

Abstract

This paper concerns the problem to place N non overlapping circles in a circular container with minimum radius. This is a well known and widely studied problem with applications in manufacturing and logistics and, in particular, to problems related to cutting and packing. In this paper we propose an algorithm that by applying a strength along a selected direction on each circle, simulates the shifting of circles on the plane and tries to reduce the radius of the circular container during this movements. The algorithm is based on a multistart technique where the starting solutions are produced by a tabu search heuristic that uses also the current best solution. The algorithm takes part in a public international contest in order to find optimal solutions to a special case in circle packing. The contest saw the participation of 155 teams and our algorithm achieved the tenth position
978-1-4799-4224-4
978-1-4799-4226-8
978-1-4799-4224-4
978-1-4799-4226-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4645241
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 6
social impact