Построение самонепересекающихся OE-маршрутов в плоском эйлеровом графе
Аннотация
В статье предложен полиномиальный алгоритм построения самонепересекающегося маршрута с упорядоченным охватыванием в плоском эйлеровом графе.
Предложенный подход состоит в расщеплении всех вершин исходного графа степени выше 4 и введении фиктивных вершин и ребер, сводя, таким образом, исходную задачу к решенной ранее автором задаче построения A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. Приведенный алгоритм сведения решает поставленную задачу за полиномиальное время. Рассмотрен тестовый пример построения самонепересекающейся цепи с упорядоченным охватыванием. Данная задача возникает при технологической подготовке процесса раскроя, когда требуется определить маршрут движения режущего инструмента, при котором отсутствуют самопересечения траектории резки и отрезанная от листа часть не требует разрезаний. Раскройный план представлен в виде плоского графа, являющегося его гомеоморфным образом. Предложенный в статье алгоритм решает проблему маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента одновременно наложены такие технологические ограничения.
Ключевые слова
Полный текст:
PDFЛитература
Silva E.F., Oliveira L.T., Oliveira J.F., Toledo F.M.B. Exact approaches for the cutting path determination problem. Computers & Operations Research. 2019. vol. 112, art. 104772. DOI: 10.1016/j.cor.2019.104772.
Makarovskikh Т.А., Panyukov А.V., Savitsky E.A. Mathematical Models and Routing Algorithms for CAD Technological Preparation of Cutting Processes. Automation and Remote Control. 2017. vol. 78, no. 4. pp. 868–882. DOI: 10.1016/10.1134/S0005117917050095.
Dewil R., Vansteenwegen P., Cattrysse D. A Review of Cutting Path Algorithms for Laser Cutters. International Journal Adv Manuf. Technol. 2016. vol. 87. pp. 1865–1884. DOI: 10.1007/s00170-016-8609-1.
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. DOI: 10.1080/00207543.2014.959268.
Hoeft J., Palekar U. Heuristics for the Plate-cutting Travelling Salesman Problem. IIE Transactions. 1997. vol. 29(9). pp. 719–731. DOI: 10.1023/A:1018582320737.
Dewil R., Vansteenwegen P., Cattrysse D. Construction Heuristics for Generating Tool Paths for Laser Cutters. International Journal of Production Research. 2014. vol. 52(20). pp. 5965–5984. DOI: 10.1080/00207543.2014.895064.
Petunin A.A., Chentsov A.G., Chentsov P.A. On the Issue of Routing Movements in Sheet Cutting of Parts. Bulletin of the South Ural State University. Series: Mathematical Modelling and Programming. 2017. vol. 10, no. 3. pp. 25–39. (in Russian) DOI: 10.14529/mmp170303.
Chentsov A.G., Grigoryev A.M., Chentsov A.A. Solving a Routing Problem with the Aid of an Independent Computations Scheme. Bulletin of the South Ural State University. Series: Mathematical Modelling and Programming. 2018. vol. 11, no. 1. pp. 60–74. (in Russian) DOI: 10.14529/mmp180106.
Petunin A., Stylios C. Optimization Models of Tool Path Problem for CNC Sheet Metal Cutting Machines. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016 (Troyes, France, June, 28–30, 2016). IFAC-PapersOnLine. 2016. vol. 49. pp. 23–28. DOI: 10.1016/j.ifacol.2016.07.544.
Chentsov A., Khachay M., Khachay D. Linear Time Algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016 (Troyes, France, June, 28–30, 2016). IFAC-PapersOnLine. 2016. vol. 49. pp. 651–655. DOI: 10.1016/j.ifacol.2016.07.767.
Khachay M., Neznakhina K. Towards Tractability of the Euclidean Generalized Travelling Salesman Problem in Grid Clusters Defined by a Grid of Bounded Height. Communications in Computer and Information Science. 2018. vol. 871. pp. 68–77. DOI: 10.1007/978-3-319-93800-4_6.
Manber U., Israni S. Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting. J. Manuf. Syst. 1984. vol. 3(1). pp. 81–89. DOI: 10.1016/0278-6125(84)90024-4.
Panyukova T. Chain Sequences with Ordered Enclosing. Journal of Computer and System Sciences International. 2007. vol. 46, no. 1(10). pp. 83–92. DOI: 10.1134/S1064230707010108.
Borse Y.M. Splitting Lemma for 2-Connected Graphs. International Scholarly Research Network, ISRN Discrete Mathematics. 2012. vol. 2012. Art. 850538. DOI: 10.5402/2012/850538.
Makarovskikh T.A. Software for Constructing of A-chains with Ordered Enclosing for a Plane Connected 4-regular Graph. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2019. vol. 8, no. 1. pp. 36–53. (in Russian) DOI: 10.14529/cmse190103.
Filippov A.F. The Elementary Proof of Jordan Theorem. Advances in Mathematical Sciences. 1950. vol. 5:5(39). pp. 173–176. (in Russian)
Manber U., Bent S.W. On Non-intersecting Eulerian Circuits. Discrete Applied Mathematics. 1987. vol. 18. pp. 87–94. DOI: 10.1016/0166-218X(87)90045-X.
Fleischner H. Eulerian Graphs and Related Topics. Part 1, vol. 1. Ann. Discrete Mathematics. 1990. no. 45.
Panyukova T.A. Constructing of OE-postman Path for a Planar Graph. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software. 2014. vol. 7, no. 4. pp. 90–101. DOI: 10.14529/mmp140407.
Makarovskikh Т.А., Panyukov А.V., Savitsky E.A. Mathematical Models and Routing Algorithms for CAM of Technological Support of Cutting Processes. ScienceDirect IFAC-PapersOnLine 49–12. 2016. pp. 821–826. DOI: 10.1016/j.ifacol.2016.07.876.
Makarovskikh T., Panyukov A. The Cutter Trajectory Avoiding Intersections of Cuts. IFAC-PapersOnLine. 2017. vol. 50, no. 1. pp. 2284–2289. DOI: 10.1016/j.ifacol.2017.08.226.
Szeider S. Finding Paths in Graphs Avoiding Forbidden Transitions. Discrete Applied Mathematics. 2003. no. 126. pp. 261–273. DOI: 10.1016/S0166-218X(02)00251-2.
DOI: http://dx.doi.org/10.14529/cmse190403