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

References

• Ascheuer, N., M. Júnger, and G. Reinelt. 2000. “A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints.” Computational Optimization and Applications 17 (1): 61–84. https://doi.org/10.1023/A:1008779125567.
   Web of Science ®Google Scholar
• Bennell, Julia A., and Jose F. Oliveira. 2008. “The Geometry of Nesting Problems: A Tutorial.” European Journal of Operational Research 184 (2): 397–415. https://doi.org/10.1016/j.ejor.2006.11.038.
   Web of Science ®Google Scholar
• Castelino, Kenneth, Roshan D'Souza, and Paul K. Wright. 2003. “Toolpath Optimization for Minimizing Airtime During Machining.” Journal of Manufacturing Systems 22 (3): 173–180. https://doi.org/10.1016/S0278-6125(03)90018-5.
   Web of Science ®Google Scholar
• Chentsov, Alexander. 2014. “Problem of Successive Megalopolis Traversal with the Precedence Conditions.” Automation and Remote Control 75 (4): 728–744. https://doi.org/10.1134/S0005117914040122.
   Web of Science ®Google Scholar
• Chentsov, Alexander G., Pavel A. Chentsov, Alexander A. Petunin, and Alexander N. Sesekin. 2018. “Model of Megalopolises in the Tool Path Optimisation for CNC Plate Cutting Machines.” International Journal of Production Research 56 (14): 4819–4830. https://doi.org/10.1080/00207543.2017.1421784.
   Web of Science ®Google Scholar
• Chentsov, A. G., M. Yu. Khachai, and D. M. Khachai. 2016. “An Exact Algorithm with Linear Complexity for a Problem of Visiting Megalopolises.” Proceedings of the Steklov Institute of Mathematics 295 (S1): 38–46. https://doi.org/10.1134/S0081543816090054.
   Google Scholar
• Cherri, Luiz Henrique, Maria Antónia Carravilla, Cristina Ribeiro, and Franklina Maria Bragion Toledo. 2019. “Optimality in Nesting Problems: New Constraint Programming Models and a New Global Constraint for Non-Overlap.” Operations Research Perspectives 6:100125. https://doi.org/10.1016/j.orp.2019.100125.
   Web of Science ®Google Scholar
• Cuellar-Usaquén, Daniel, Alejandro Palacio, Emilia Ospina, Marcelo Botero, and David Álvarez Martínez. 2023. “Modeling and Solving the Endpoint Cutting Problem.” International Transactions in Operational Research 30 (2): 800–830. https://doi.org/10.1111/itor.v30.2.
   Web of Science ®Google Scholar
• Desrochers, Martin, and Gilbert Laporte. 1991. “Improvements and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints.” Operations Research Letters 10 (1): 27–36. https://doi.org/10.1016/0167-6377(91)90083-2.
   Web of Science ®Google Scholar
• Dewil, Reginald, Pieter Vansteenwegen, and Dirk Cattrysse. 2014. “Construction Heuristics for Generating Tool Paths for Laser Cutters.” International Journal of Production Research 52 (20): 5965–5984. https://doi.org/10.1080/00207543.2014.895064.
   Web of Science ®Google Scholar
• Dewil, Reginald, Pieter Vansteenwegen, and Dirk Cattrysse. 2016. “A Review of Cutting Path Algorithms for Laser Cutters.” The International Journal of Advanced Manufacturing Technology 87 (5-8): 1865–1884. https://doi.org/10.1007/s00170-016-8609-1.
   Web of Science ®Google Scholar
• Dewil, Reginald, Pieter Vansteenwegen, Dirk Cattrysse, Manuel Laguna, and Thomas Vossen. 2015. “An Improvement Heuristic Framework for the Laser Cutting Tool Path Problem.” International Journal of Production Research 53 (6): 1761–1776. https://doi.org/10.1080/00207543.2014.959268.
   Web of Science ®Google Scholar
• Dyckhoff, Harald. 1990. “A Typology of Cutting and Packing Problems.” European Journal of Operational Research 44 (2): 145–159. Cutting and Packing. https://doi.org/10.1016/0377-2217(90)90350-K.
   Web of Science ®Google Scholar
• Gendreau, Michel, and Jean-Yves Potvin.. 2019. “Handbook of Metaheuristics.” 3rd ed., International Series in Operations Research & Management Science 272. Springer International Publishing.
   Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1961. “A Linear Programming Approach to the Cutting-Stock Problem.” Operations Research 9 (6): 849–859. https://doi.org/10.1287/opre.9.6.849.
   Web of Science ®Google Scholar
• Gutin, Gregory, and Abraham P. Punnen. 2007. The Traveling Salesman Problem and Its Variations. Boston, MA:Springer US.
   Google Scholar
• Han, Guk-Chan, and Suck-Joo Na. 1999. “A Study on Torch Path Planning in Laser Cutting Processes Part 2: Cutting Path Optimization Using Simulated Annealing.” Journal of Manufacturing Systems 18 (2): 62–70. https://doi.org/10.1016/S0278-6125(99)80027-2.
   Google Scholar
• Helsgaun, Keld. 2000. “An Effective Implementation of the Lin–Kernighan Traveling Salesman Heuristic.” European Journal of Operational Research 126 (1): 106–130. https://doi.org/10.1016/S0377-2217(99)00284-2.
   Web of Science ®Google Scholar
• Herrmann, J. W., and D. R. Delalio. 2001. “Algorithms for Sheet Metal Nesting.” IEEE Transactions on Robotics and Automation 17 (2): 183–190. https://doi.org/10.1109/70.928563.
   Google Scholar
• Hoeft, Jeffrey, and Udatta S. Palekar. 1997. “Heuristics for the Plate-Cutting Traveling Salesman Problem.” IIE Transactions 29 (9): 719–731.
   Web of Science ®Google Scholar
• Hu, Qirut, Zhiwei Lin, and Jianzhong Fu. 2022. “A Robust Fast Bridging Algorithm for Laser Cutting.” The International Journal of Advanced Manufacturing Technology 121 (3-4): 2083–2094. https://doi.org/10.1007/s00170-022-09465-w.
   Web of Science ®Google Scholar
• Imahori, Shinji, Motoki Kushiya, Takeru Nakashima, and Kokichi Sugihara. 2008. “Generation of Cutter Paths for Hard Material in Wire EDM.” Journal of Materials Processing Technology 206 (1-3): 453–461. https://doi.org/10.1016/j.jmatprotec.2007.12.039.
   Web of Science ®Google Scholar
• Kandasamy, Vijay, and S. Udhayakumar. 2020. “Effective Location of Micro Joints and Generation of Tool Path Using Heuristic and Genetic Approach for Cutting Sheet Metal Parts.” International Journal of Material Forming 13 (2): 317–329. https://doi.org/10.1007/s12289-019-01488-1.
   Web of Science ®Google Scholar
• Karapetyan, Daniel., and Gregory Gutin. 2012. “Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem.” European Journal of Operational Research 219 (2): 234–251. https://doi.org/10.1016/j.ejor.2012.01.011.
   Web of Science ®Google Scholar
• Khachai, Daniil, Ruslan Sadykov, Olga Battaia, and Michael Khachay. 2023. “Precedence Constrained Generalized Traveling Salesman Problem: Polyhedral Study, Formulations, and Branch-And-cut Algorithm.” European Journal of Operational Research 309 (2): 488–505. https://doi.org/10.1016/j.ejor.2023.01.039.
   Web of Science ®Google Scholar
• Khachay, Michael, Andrei Kudriavtsev, and Alexander Petunin. 2020. “PCGLNS: A Heuristic Solver for the Precedence Constrained Generalized Traveling Salesman Problem.” LNCS 12422:196–208.
   Google Scholar
• Khachay, Michael, and Katherine Neznakhina. 2020. “Complexity and Approximability of the Euclidean Generalized Traveling Salesman Problem in Grid Clusters.” Annals of Mathematics and Artificial Intelligence 88 (1-3): 53–69. https://doi.org/10.1007/s10472-019-09626-w.
   Web of Science ®Google Scholar
• Lee, Moon-Kyu, and Ki-Bum Kwon. 2006. “Cutting Path Optimization in CNC Cutting Processes Using a Two-Step Genetic Algorithm.” International Journal of Production Research 44 (24): 5307–5326. https://doi.org/10.1080/00207540600579615.
   Web of Science ®Google Scholar
• Makarovskikh, T. A., A. V. Panyukov, and E. A. Savitskiy. 2018. “Mathematical Models and Routing Algorithms for Economical Cutting Tool Paths.” International Journal of Production Research 56 (3): 1171–1188. https://doi.org/10.1080/00207543.2017.1401746.
   Web of Science ®Google Scholar
• Manber, Udi, and Sharat Israni. 1984. “Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting.” Journal of Manufacturing Systems 3 (1): 81–89. https://doi.org/10.1016/0278-6125(84)90024-4.
   Web of Science ®Google Scholar
• Miller, C. E., A. W. Tucker, and R. A. Zemlin. 1960. “Integer Programming Formulation of Traveling Salesman Problems.” Journal of the ACM 7 (4): 326–329. https://doi.org/10.1145/321043.321046.
   Web of Science ®Google Scholar
• Moreira, Luís M., José F. Oliveira, A. Miguel Gomes, and J. Soeiro Ferreira. 2007. “Heuristics for a Dynamic Rural Postman Problem.” Computers & Operations Research 34 (11): 3281–3294. https://doi.org/10.1016/j.cor.2005.12.008.
   Web of Science ®Google Scholar
• Noon, Charles E., and James C. Bean. 1993. “An Efficient Transformation of The Generalized Traveling Salesman Problem.” INFOR: Information Systems and Operational Research 31 (1): 39–44.
   Web of Science ®Google Scholar
• Oliveira, Larissa Tebaldi, Everton Fernandes Silva, José Fernando Oliveira, and Franklina Maria Bragion Toledo. 2020. “Integrating Irregular Strip Packing and Cutting Path Determination Problems: A Discrete Exact Approach.” Computers and Industrial Engineering 149:106757. https://doi.org/10.1016/j.cie.2020.106757.
   Web of Science ®Google Scholar
• Petunin, Alexander. 2019. “General Model of Tool Path Problem for the CNC Sheet Cutting Machines.” IFAC-PapersOnLine 52 (13): 2662–2667. https://doi.org/10.1016/j.ifacol.2019.11.609.
   Google Scholar
• Petunin, Alexander, Michael Khachay, Stanislav Ukolov, and Pavel Chentsov. 2022. “Using PCGTSP Algorithm for Solving Generalized Segment Continuous Cutting Problem.” IFAC-PapersOnLine 55 (10): 578–583. https://doi.org/10.1016/j.ifacol.2022.09.456.
   Google Scholar
• Petunin, Alexander A., and Chrysostomos Stylios. 2016. “Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting Machines.” IFAC-PapersOnLine 49 (12): 23–28. https://doi.org/10.1016/j.ifacol.2016.07.544.
   Google Scholar
• Rodrigues, Ana Maria, and José Soeiro Ferreira. 2012. “Cutting Path As a Rural Postman Problem: Solutions by Memetic Algorithms.” International Journal of Combinatorial Optimization Problems and Informatics 3 (1): 31–46.
   Google Scholar
• Salman, Raad, Fredrik Ekstedt, and Peter Damaschke. 2020. “Branch-And-bound for the Precedence Constrained Generalized Traveling Salesman Problem.” Operations Research Letters 48 (2): 163–166. https://doi.org/10.1016/j.orl.2020.01.009.
   Web of Science ®Google Scholar
• Sherif, S. Umar, N. Jawahar, and M. Balamurali. 2014. “Sequential Optimization Approach for Nesting and Cutting Sequence in Laser Cutting.” Journal of Manufacturing Systems 33 (4): 624–638. https://doi.org/10.1016/j.jmsy.2014.05.011.
   Web of Science ®Google Scholar
• Silva, Everton Fernandes, Larissa Tebaldi Oliveira, José Fernando Oliveira, and Franklina Maria Bragion Toledo. 2019. “Exact Approaches for the Cutting Path Determination Problem.” Computers & Operations Research 112:104772. https://doi.org/10.1016/j.cor.2019.104772.
   Web of Science ®Google Scholar
• Vapnik, Vladimir N. 1998. “Statistical Learning Theory.” In Adaptive and learning systems for signal processing, communications, and control. Wiley.
   Google Scholar
• Wäscher, Gerhard, Heike Haußner, and Holger Schumann. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183 (3): 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047.
   Web of Science ®Google Scholar
• Yuan, Yuan, Diego Cattaruzza, Maxime Ogier, and Frédéric Semet. 2020. “A Branch-And-cut Algorithm for the Generalized Traveling Salesman Problem with Time Windows.” European Journal of Operational Research 286 (3): 849–866. https://doi.org/10.1016/j.ejor.2020.04.024.
   Web of Science ®Google Scholar
• Zhang, Tai, Shaowen Yao, Qiang Liu, Lijun Wei, and Hao Zhang. 2024. “Heuristic Approaches for the Cutting Path Problem.” Expert Systems with Applications 237:121567. https://doi.org/10.1016/j.eswa.2023.121567.
   Web of Science ®Google Scholar