Title: Heuristic methods for the leather nesting problem in the automotive industry

Authors: Telmo Miguel Pires Pinto; Cláudio Manuel Martins Alves; José Manuel Vasconcelos Valério De Carvalho; Pedro Alexandre Fonseca Brás

Addresses: Algoritmi Research Centre, School of Engineering, University of Minho, 4710-057 Braga, Portugal ' Algoritmi Research Centre, School of Engineering, University of Minho, 4710-057 Braga, Portugal ' Algoritmi Research Centre, School of Engineering, University of Minho, 4710-057 Braga, Portugal ' Algoritmi Research Centre, School of Engineering, University of Minho, 4710-057 Braga, Portugal

Abstract: In this paper, we address a real leather nesting problem (LNP) with holes and quality zones that arises in the automotive industry. We describe two approaches for the solution of the LNP. The first approach consists in a constructive heuristic, while the second relies on local search methods. The constructive heuristic is based on a simulation of the positioning of a piece so as to evaluate its fitness within the hide and within the current layout. The later approach suggested in this paper is based in a local search method whose neighbourhood structure operates on cutting patterns. In order to improve this procedure, we also describe an improvement of our constructive heuristic to apply it at each iteration of the local search procedure. The proposed methods were implemented and tested on real instances of the automotive industry. The obtained results for both heuristics illustrate the adequacy and the potential of the proposed approaches.

Keywords: decision support systems; DSS; operations research; heuristics; enterprise applications; tools; combinatorial optimisation; residual cutting stock; local search; nesting problem; leather hides; leather nesting; automobile industry; automotive leather; local search; simulation; cutting patterns; irregular surfaces; vehicle modelling; car seats.

DOI: 10.1504/IJBEX.2016.075594

International Journal of Business Excellence, 2016 Vol.9 No.3, pp.332 - 347

Received: 29 May 2014
Accepted: 17 Jun 2014

Published online: 26 Jan 2016 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article