Skip to main content

2021 | OriginalPaper | Buchkapitel

Library of Sample Image Instances for the Cutting Path Problem

verfasst von : Alexander Petunin, Alexander Khalyavka, Michael Khachay, Andrei Kudriavtsev, Pavel Chentsov, Efim Polishchuk, Stanislav Ukolov

Erschienen in: Pattern Recognition. ICPR International Workshops and Challenges

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The Cutting Path Problem (CPP) is a complex continuous and combinatorial optimization problem that is about finding an optimal tool path for CNC technologies equipment. The problem has many valuable industrial applications arising from the Industry 4.0 strategy, such as those, related to tool path routing for the sheet metal cutting machines. The CPP is strongly NP-hard enclosing variants of the well-known Traveling Salesman Problem (TSP) as sub-problems. In this paper, we for the first time propose an open access library of sample instances (CPPLib) for the CPP to facilitate the benchmarking of optimization algorithms, most of them are heuristics or metaheuristics. Each instance is obtained as an image of a finite set of mutually nested industrial parts on a metal sheet and is presented in the DXF vector format that is induced by a solution result of the well-known 2D nesting problem. For the first time we propose geometric and quantitative principles for constructing different groups (classes) of such image instances. Along with continuous CPP settings, the library contains their discrete counterparts presented in the form of instances of the Precedence Constraints Generalized Traveling Salesman Problem (PCGTSP), since the solution processes for the CPP mostly based on discretizing boundary contours of parts. In addition, the paper presents examples of testing some optimization algorithms for solving the cutting path problem on test instances from the developed CPPLib library.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
3.
Zurück zum Zitat Oliveira J.F.C., Ferreira J.A.S.: Algorithms for nesting problems. In: Vidal R.V.V. (eds) Applied Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, vol 396. Springer, Berlin, Heidelberg (1993). https://doi.org/https://doi.org/10.1007/978-3-642-46787-5_13 Oliveira J.F.C., Ferreira J.A.S.: Algorithms for nesting problems. In: Vidal R.V.V. (eds) Applied Simulated Annealing. Lecture Notes in Economics and Mathematical Systems, vol 396. Springer, Berlin, Heidelberg (1993). https://​doi.​org/​https://​doi.​org/​10.​1007/​978-3-642-46787-5_​13
5.
Zurück zum Zitat Chentsov, A.G., Khachay, M.Yu., Khachay, D.M.: Linear time algorithm for precedence constrained asymmetric Generalized Traveling Salesman Problem. IFAC-PapersOnLine 49(12), 651–655 (2016). https://doi.org/https://doi.org/10.1016/j.ifacol.2016.07.767. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016 Chentsov, A.G., Khachay, M.Yu., Khachay, D.M.: Linear time algorithm for precedence constrained asymmetric Generalized Traveling Salesman Problem. IFAC-PapersOnLine 49(12), 651–655 (2016). https://​doi.​org/​https://​doi.​org/​10.​1016/​j.​ifacol.​2016.​07.​767. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016
8.
Zurück zum Zitat Chentsov, A.G., Chentsov, P.A., Petunin, A.A., Sesekin, A.N.: Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Int. J. Prod. Res. 56(14), 4819–4830 (2018)CrossRef Chentsov, A.G., Chentsov, P.A., Petunin, A.A., Sesekin, A.N.: Model of megalopolises in the tool path optimisation for CNC plate cutting machines. Int. J. Prod. Res. 56(14), 4819–4830 (2018)CrossRef
12.
Zurück zum Zitat Petunin, A.A.: Modeling of tool path for the CNC sheet cutting machines. In: Pasheva, B., Popivanov, N., Venkov, G. (eds.) 41st International Conference "Applications of Mathematics in Engineering and Economics", AMEE 2015, 1690. [060002] (AIP Conference Proceedings; 1690. American Institute of Physics Publising LLC (2015). https://doi.org/10.1063/1.4936740 Petunin, A.A.: Modeling of tool path for the CNC sheet cutting machines. In: Pasheva, B., Popivanov, N., Venkov, G. (eds.) 41st International Conference "Applications of Mathematics in Engineering and Economics", AMEE 2015, 1690. [060002] (AIP Conference Proceedings; 1690. American Institute of Physics Publising LLC (2015). https://​doi.​org/​10.​1063/​1.​4936740
13.
Zurück zum Zitat Tavaeva, A.F., Petunin, A.A., Polishchuk, E.G.: Methods of Cutting Cost Minimizing in Problem of Tool Route Optimization for CNC Laser Machines. In: Radionov, A.A., Kravchenko, O.A., Guzeev, V.I., Rozhdestvenskiy, Y.V. (eds.) ICIE 2019. LNME, pp. 447–455. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-22063-1_48CrossRef Tavaeva, A.F., Petunin, A.A., Polishchuk, E.G.: Methods of Cutting Cost Minimizing in Problem of Tool Route Optimization for CNC Laser Machines. In: Radionov, A.A., Kravchenko, O.A., Guzeev, V.I., Rozhdestvenskiy, Y.V. (eds.) ICIE 2019. LNME, pp. 447–455. Springer, Cham (2020). https://​doi.​org/​10.​1007/​978-3-030-22063-1_​48CrossRef
16.
Metadaten
Titel
Library of Sample Image Instances for the Cutting Path Problem
verfasst von
Alexander Petunin
Alexander Khalyavka
Michael Khachay
Andrei Kudriavtsev
Pavel Chentsov
Efim Polishchuk
Stanislav Ukolov
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-68821-9_21