phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2022 - 2 issue » pp. 187-210

Archive of Issues

Russia Yekaterinburg
Year
2022
Volume
32
Issue
2
Pages
187-210
<<
>>
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.
References
  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. https://doi.org/10.1063/5.0036656
  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. https://doi.org/10.1080/00207543.2017.1421784
  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. https://doi.org/10.1145/321105.321111
  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. https://doi.org/10.1137/0110015
  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. https://doi.org/10.4028/www.scientific.net/KEM.639.517
  13. Dowsland K.A., Dowsland W.B. Solution approaches to irregular nesting problems, European Journal of Operational Research, 1995, vol. 84, pp. 506-521. https://doi.org/10.1016/0377-2217(95)00019-m
  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. https://doi.org/10.1007/978-3-319-68640-0_25
  15. Alvarez-Valdés R., Carravilla M.A., Oliveira J.F. Cutting and packing, Handbook of Heuristics, Berlin: Springer, 2018, pp. 931-998. https://doi.org/10.1007/978-3-319-07124-4_43
  16. Hoeft J.S., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem, IIE Transactions, 1997, vol. 29, pp. 719-731. https://doi.org/10.1023/A:1018582320737
  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. https://doi.org/10.1007/s00170-016-8609-1
  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. https://doi.org/10.1080/00207543.2014.959268
  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. https://doi.org/10.1016/j.procir.2020.09.171
  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. https://doi.org/10.1016/j.ifacol.2019.11.607
  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. https://doi.org/10.1080/00207543.2017.1401746
  25. Makarovskikh T., Panyukov A., Savitsky E. Software development for cutting tool routing problems, Procedia Manufacturing, 2019, vol. 29, pp. 567-574. https://doi.org/10.1016/j.promfg.2019.02.123
  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. https://doi.org/10.12700/aph.17.8.2020.8.12
  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. https://doi.org/10.1016/j.ifacol.2019.11.609
  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. https://doi.org/10.1016/j.ifacol.2016.07.544
  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. https://doi.org/10.1115/1.4038207
  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. https://doi.org/10.1088/1757-899x/613/1/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. https://doi.org/10.1007/978-3-642-40627-0_58
  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. https://doi.org/10.1007/s00170-019-03569-6
  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. https://doi.org/10.1088/2053-1591/aafc01
  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. https://doi.org/10.1016/j.ejor.2020.04.024
  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. https://doi.org/10.1134/S1064562415020313
  36. Gendreau M., Ghiani G., Guerriero E. Time-dependent routing problems: A review, Computers and Operations Research, 2015, vol. 64, pp. 189-197. https://doi.org/10.1016/j.cor.2015.06.001
  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. https://doi.org/10.1016/j.ejor.2016.11.035
  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. https://doi.org/10.1007/s11047-009-9111-6
  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. https://doi.org/10.1016/j.cor.2017.05.010
  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. https://doi.org/10.1016/j.procir.2016.02.136
  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. https://doi.org/10.1016/j.orl.2020.01.009
  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. https://doi.org/10.4028/www.scientific.net/KEM.833.29
  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. https://doi.org/10.1007/s00170-019-04768-x
  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. https://doi.org/10.3390/mi12010088
  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. https://doi.org/10.1108/K-03-2015-0069
  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. https://doi.org/10.1109/ISSPIT.2017.8388654
  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. https://doi.org/10.1007/s12289-019-01488-1
  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. https://doi.org/10.1134/S0005117916110060
  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. https://doi.org/10.1007/978-3-030-33394-2_33
Full text
/doc/issues-2022/22-02-03.pdf
<< Previous article
Next article >>