Discrete cutting path problems: a general solution framework and industrial applications

Abstract

The optimal tool routing for cutting machines, also known as cutting path optimisation is an important problem in production research. This problem is relevant in various manufacturing environments such as aeronautic, automotive, garment and semiconductor industries. In this paper, we introduce a general solution framework for the discrete Cutting Path Problem which includes: (i) the universal approach to reduce numerous settings of this problem to the appropriate auxiliary instances of the well-known Precedence Constrained Generalized Traveling Salesman Problem; (ii) the proposition of efficient solution methods for finding (sub-) optimal solutions. We carry out extensive computational experiments in order to evaluate performance of the proposed framework and the obtained results demonstrate its efficiency for real-life industrial instances.

Keywords:

• Cutting path problem
• endpoint cutting problem
• precedence constrained generalised travelling salesman problem
• branch-and-cut algorithm
• adaptive large neighbourhood search
• industry
• innovation and infrastructure

Acknowledgments

We thank N.N. Krasovskii Institute of Mathematics and Mechanics for providing us access to ‘Uran’ Supercomputing centre and technical support. We also thank the anonymous reviewers, whose invaluable comments helped us to significantly improve the paper.

Data availability statement

All used data is provided in the paper and it is available on https://github.com/EnsignDaniels/CPP along with the source codes. If readers have any question about the data used in this research they are invited to contact the corresponding author who will share all available information.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

This work was supported by L'Agence nationale de la recherche[ANR-20-CE40-0021].

Notes on contributors

Daniil Khachai

Daniil Khachai currently a research assistant at Centre of Excellence Supply Chain (CESIT) at Kedge Business School, Bordeaux, France. He has a PhD in Applied Mathematics and Computer Science from University of Bordeaux. His second PhD in Business Administration was achieved at Kedge Business School. He is passionate about combinatorial optimization, operations research, supply chains and their applications in the industry.

Olga Battaïa

Prof. Olga Battaïa has a Senior Professor position in Department of Operations Management and Information Systems at Kedge Business School. She serves as Associated Editor for several international peer-reviewed journals, including the Journal of Manufacturing Systems, IISE Transactions (Institute of Industrial and Systems Engineers) and Omega-the International Journal of Management Science. She is an Associate Member of the International Academy for Production Engineering (CIRP) and a Member of IFAC Technical Committee 5.2. Management and Control in Manufacturing and Logistics. Her research interests lie in the domains of Supply Chain Management, Industry 4.0, Sustainable manufacturing, Business Analytics, Decision Support Systems. She was invited to present her research at several renowned international conferences and universities in Europe, Africa, America, Asia, and Australia.

Alexander Petunin

Alexander Petunin is a full professor of information technologies and automation and deputy director of institute for science and innovations at Ural Federal University, Ekaterinburg, Russia. His main research interests lie in the field of industrial applications of many problems related to the combinatorial optimization.

Michael Khachay

Michael Khachay is full professor in applied mathematics, head of Mathematical Programming Lab at Krasovsky Institute of Mathematics and Mechanics, Ekaterinburg Russia, and Corresponding member of Russian Academy of Sciences. His research interests lie in algorithmic design and analysis for combinatorial optimization, operations research, and machine learning.