phone +7 (3412) 91 60 92

Archive of Issues

Russia Yekaterinburg
Section Mathematics
Title Some applications of optimization routing problems with additional constraints
Author(-s) Petunin A.A.a, Chentsov A.G.ab, Chentsov P.A.ab
Affiliations Ural Federal Universitya, Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesb
Abstract The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.
Keywords dynamic programming, additional constraints, megalopolises, routing, CNC sheet cutting machines, tool path problem
UDC 517.958
MSC 49L20, 90C39
DOI 10.35634/vm220203
Received 30 March 2022
Language English
Citation Petunin A.A., Chentsov A.G., Chentsov P.A. Some applications of optimization routing problems with additional constraints, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2022, vol. 32, issue 2, pp. 187-210.
  1. Korobkin V.V., Sesekin A.N., Tashlykov O.L., Chentsov A.G. Metody marshrutizatsii i ikh prilozheniya v zadachakh povysheniya effektivnosti i bezopasnosti ekspluatatsii atomnykh stantsii (Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants), Moscow: Novye Tekhnologii, 2012.
  2. Chentsov A.G. Dynamic programming in routing problems (nuclear power, Engineering), AIP Conference Proceedings, 2020, vol. 2315, issue 1, 040011.
  3. Petunin A.A., Chentsov A.G., Chentsov P.A. Optimal'naya marshrutizatsiya instrumenta mashin figurnoi listovoi rezki s chislovym programmnym upravleniem. Matematicheskie modeli i algoritmy (Optimal tool routing for CNC shape sheet cutting machines. Mathematical models and algorithms), Yekaterinburg: Ural University, 2020.
  4. 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, International Journal of Production Research, 2018, vol. 56, no. 14, pp. 4819-4830.
  5. Gutin G., Punnen A.P. The traveling salesman problem and its variations, Springer Science and Business Media, 2006.
  6. Cook W.J. In pursuit of the traveling salesman: mathematics at the limits of computation, Princeton University Press, 2011.
  7. Gimadi E.K., Khachay M.Y. Ekstremal'nye zadachi na mnozhestvakh perestanovok (Extremal problems on sets of permutations), Yekaterinburg: Izd. UMTs UPI, 2016.
  8. Melamed I.I., Sergeev S.I., Sigal I.K. The traveling salesman problem. I: Theoretical issues, Automation and Remote Control, 1989, vol. 50, no. 9, pp. 1147-1173.
  9. Bellman R. Dynamic programming treatment of the travelling salesman problem, Journal of the ACM, 1962, vol. 9, issue 1, pp. 61-63.
  10. Held M., Karp R.M. A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied Mathematics, 1962, vol. 10, no. 1, pp. 196-210.
  11. Chentsov A.G. Ekstremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal problems of routing and assignment of tasks: questions of theory), Moscow-Izhevsk: Regular and Chaotic Dynamics, Institute of Computer Science, 2008.
  12. Dewil R., Vansteenwegen P., Cattrysse D. Sheet metal laser cutting tool path generation: dealing with overlooked problem aspects, Key Engineering Materials, 2015, vol. 639, pp. 517-524.
  13. Dowsland K.A., Dowsland W.B. Solution approaches to irregular nesting problems, European Journal of Operational Research, 1995, vol. 84, pp. 506-521.
  14. Stoyan Y., Pankratov A., Romanova T. Placement problems for irregular objects: mathematical modeling, optimization and applications, Optimization Methods and Applications: In Honor of Ivan V. Sergienko's 80th Birthday, Cham, Switzerland: Springer, 2017, pp. 521-559.
  15. Alvarez-Valdés R., Carravilla M.A., Oliveira J.F. Cutting and packing, Handbook of Heuristics, Berlin: Springer, 2018, pp. 931-998.
  16. Hoeft J.S., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem, IIE Transactions, 1997, vol. 29, pp. 719-731.
  17. Dewil R., Vansteenwegen P., Cattrysse D. A review of cutting path algorithms for laser cutters, International Journal of Advanced Manufacturing Technology, 2016, vol. 87, no. 5, pp. 1865-1884.
  18. Dewil R., Vansteenwegen P., Cattrysse D., Laguna M., Vossen T. An improvement heuristic framework for the laser cutting tool path problem, International Journal of Production Research, 2015, vol. 53, no. 6, pp. 1761-1776.
  19. Levichev N., Rodrigues G.C., Duflou J.R. Real-time monitoring of fiber laser cutting of thick plates by means of photodiodes, Procedia CIRP, 2020, vol. 94, pp. 499-504.
  20. Sonawane S., Patil P., Bharsakade R., Gaigole P. Optimizing tool path sequence of plasma cutting machine using tsp approach, E3S Web of Conferences, 2020, vol. 184, p. 01037.
  21. Ganelina N.D., Frolovskiy V.D. Decomposition method for optimizing the design of control programs for thermal cutting of metal on CNC equipment, Nauchnyi Vestnik NGTU, 2006, no. 2, pp. 9-19 (in Russian).
  22. Verkhoturov M.A., Tarasenko P.Yu. Mathematical support of the problem of optimizing the path of the cutting tool for flat shape cutting based on chain cutting, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta, 2008, vol. 10, no. 2, pp. 123-130 (in Russian).
  23. Makarovskikh T.A., Panyukov A.V. Software for constructing A-chains with ordered enclosing for a plane connected 4-regular graph, IFAC-PapersOnLine, 2019, vol. 52, pp. 2650-2655.
  24. Makarovskikh T.A., Panyukov A.V., Savitskiy E.A. Mathematical models and routing algorithms for economical cutting tool paths, International Journal of Production Research, 2018, vol. 56, no. 3, pp. 1171-1188.
  25. Makarovskikh T., Panyukov A., Savitsky E. Software development for cutting tool routing problems, Procedia Manufacturing, 2019, vol. 29, pp. 567-574.
  26. Petunin A.A., Chentsov P.A. Routing in CNC cutting machines: Engineering constraints, Acta Polytechnica Hungarica, 2020, vol. 17, no. 8, pp. 165-177.
  27. Petunin A. General model of tool path problem for the CNC sheet cutting machines, IFAC-PapersOnLine, 2019, vol. 52, issue 13, pp. 2662-2667.
  28. Petunin A.A., Stylios C. Optimization models of tool path problem for CNC sheet metal cutting machines, IFAC-PapersOnLine, 2016, vol. 49, issue 12, pp. 23-28.
  29. Mejia D., Moreno A., Arbelaiz A., Posada J., Ruiz-Salguero O., Chopitea R. Accelerated thermal simulation for three-dimensional interactive optimization of computer numeric control sheet metal laser cutting, Journal of Manufacturing Science and Engineering, 2018, vol. 140, no. 3, p. 031006.
  30. Petunin A.A., Polyshuk E.G., Chentsov P.A., Ukolov S.S., Krotov V.I. The termal deformation reducing in sheet metal at manufacturing parts by CNC cutting machines, IOP Conference Series: Materials Science and Engineering, 2019, vol. 613, p. 012041.
  31. Lagerkvist M.Z., Nordkvist M., Rattfeldt M. Laser cutting path planning using CP, Principles and Practice of Constraint Programming, Berlin: Springer, 2013, pp. 790-804.
  32. Makbul H., Viboon T., Chorkaew J., Chaiya D. Laser cutting path optimization using simulated annealing with an adaptive large neighborhood search, The International Journal of Advanced Manufacturing Technology, 2019, vol. 103, no. 1-4, pp. 781-792.
  33. Balamurali M., Jawahar N., Sivaramakrishnan B., Thirumoolam M. Realization of effective laser blanking process by heat zone spread resistance coating and optimization methods, Materials Research Express, 2019, vol. 6, no. 4, p. 046416.
  34. Yuan Y., Cattaruzza D., Ogier M., Semet F. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, European Journal of Operational Research, 2020, vol. 286, no. 3, pp. 849-866.
  35. Khachai M., Neznakhina E. Approximability of the problem about a minimum-weight cycle cover of a graph, Doklady Mathematics, 2015, vol. 91, no. 2, pp. 240-245.
  36. Gendreau M., Ghiani G., Guerriero E. Time-dependent routing problems: A review, Computers and Operations Research, 2015, vol. 64, pp. 189-197.
  37. Kinable J., Cire A., van Hoeve W.-J. Hybrid optimization methods for time-dependent sequencing problems, European Journal of Operational Research, 2017, vol. 259, issue 3, pp. 887-897.
  38. Alkaya A.F., Duman E. A new generalization of the traveling salesman problem, Applied and Computational Mathematics, 2010, vol. 9, no. 2, pp. 162-175.
  39. Gutin G., Karapetyan D. A memetic algorithm for the generalized traveling salesman problem, Natural Computing, 2010, vol. 9, no. 1, pp. 47-60.
  40. Helsgaun K. Solving the equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun algorithm, Mathematical Programming Computation, Berlin-Heidelberg: Springer, 2015, pp. 1-19.
  41. Smith S.L., Imeson F. GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem, Computers and Operations Research, 2017, vol. 87, pp. 1-19.
  42. Salman R., Carlson J.S., Ekstedt F., Spensieri D., Torstensson J., Söderberg R. An industrially validated CMM inspection process with sequence constraints, Procedia CIRP, 2016, vol. 44, pp. 138-143.
  43. Salman R., Ekstedt F., Damaschke P. Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem, Operations Research Letters, 2020, vol. 48, no. 2, pp. 163-166.
  44. Hajad M., Tangwarodomnukun V., Dumkum C., Jaturanonda C. Solving the laser cutting path problem using population-based simulated annealing with adaptive large neighborhood search, Key Engineering Materials, 2020, vol. 833, pp. 29-34.
  45. Li J., Zhu H., Zhang T., He L., Guan Y., Zhang H. Automatic generation of auxiliary cutting paths based on sheet material semantic information, The International Journal of Advanced Manufacturing Technology, 2020, vol. 106, pp. 3787-3797.
  46. Xin Y., Li Y., Li W., Wang G. Towards efficient milling of multi-cavity aeronautical structural parts considering aco-based optimal tool feed position and path, Micromachines, 2021, vol. 12, no. 1, article 88.
  47. Al-Janan D.H., Liu T.-K. Path optimization of CNC PCB drilling using hybrid Taguchi genetic algorithm, Kybernetes, 2016, vol. 45, pp. 107-125.
  48. Starostin N.D., Mironov K.V., Mironov K.V. Algorithm modification of the level-by-level approximation to the minimum route, 2017 IEEE International Symposium on Signal Processing and Information Technology (ISSPIT), 2017, pp. 270-275.
  49. Kandasamy V.A., Udhayakumar S. 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, 2020, vol. 13, pp. 317-329.
  50. Kuratovskiy K., Mostovskiy A. Teoriya mnozhestv (Set theory), Moscow: Mir, 1970.
  51. Dieudonné J. Foundations of modern analysis, New York: Academic Press Inc., 1960.
  52. Cormen T.H., Leizerson C.E., Rivest R.L., Stein C. Introduction to algorithms, Third Edition, Cambridge: MIT Press, 2009.
  53. Chentsov A.G., Chentsov P.A. Routing under constraints: Problem of visit to megalopolises, Automation and Remote Control, 2016, vol. 77, no. 11, pp. 1957-1974.
  54. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems, Report BW106, Amsterdam: Mathematisch Centrum, 1979.
  55. Tavaeva A., Petunin A., Ukolov S., Krotov V. A cost minimizing at laser cutting of sheet parts on CNC machines, Communications in Computer and Information Science, 2019, vol. 10, pp. 422-437.
Full text
<< Previous article
Next article >>