A local search approach to a circle cutting problem arising in the motor cycle industry

Abstract

This paper is concerned with the development of a customized circle packing algorithm for a manufacturer of sprockets for the motor cycle industry. Practical constraints mean that the problem differs somewhat from those tackled elsewhere in the literature. In particular, the layouts need to conform to a given structure. This is achieved by using a local search algorithm with an appropriate starting solution and a series of neighbourhoods designed to preserve the layout structure. Empirical evidence based on real data shows that the quality of the resulting solutions closely matches that of cutting patterns currently produced by human experts. Computation times average around 20–30 s per order as compared to several hours for an equivalent manual solution.

Keywords:

• heuristics
• local search
• cutting stock problem
• production