Программное обеспечение для построения a-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе

Программное обеспечение для построения a-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе

Автор: Макаровских Татьяна Анатольевна

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 1 т.8, 2019 года.

Бесплатный доступ

В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.

Еще

Плоский граф, маршрут, раскройный план, полиномиальный алгоритм

Короткий адрес: https://sciup.org/147233189

IDR: 147233189   |   DOI: 10.14529/cmse190103

Список литературы Программное обеспечение для построения a-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе

  • Dewil R., Vansteenwegen P., Cattrysse D. A Review of Cutting Path Algorithms for Laser Cutters // International Journal Adv Manuf. Technol. 2016. Vol. 87. P. 1865-1884. DOI: 10.1007/s00170-016-8609-1
  • 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. P. 868-882.
  • 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, Issue 6. P. 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). P. 719-731.
  • Dewil R., Vansteenwegen P., Cattrysse D. Construction Heuristics for Generating Tool Paths for Laser Cutters. // International Journal of Production Research. 2014. Vol. 52(20). P. 5965-5984.
  • Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации перемещений при листовой резке деталей // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2017. Т. 10, № 3. С. 25-39.
  • 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 // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2018. Т. 11, № 1. С. 60-74.
  • 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. P. 23-28.
  • 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. P. 651-655.
  • 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. P. 68-77.
  • Manber U., Israni S. Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting // J. Manuf. Syst. Vol 3(1). 1984. P. 81-89.
  • DOI: 10.1016/0278-6125(84)90024-4
  • Panyukova T.A. Constructing of OE-postman Path for a Planar Graph // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2014. Т. 7, № 4. С. 90-101.
  • DOI: 10.14529/mmp140407
  • Garfinkel R.S., Webb I.R. On Crossings, the Crossing Postman Problem, and the Rural Postman Problem. // Networks. 1999. Vol. 34(3). P. 173-180.
  • Manber U., Bent S.W. On Non-intersecting Eulerian Circuits // Discrete Applied Mathematics. 1987. Vol. 18. P. 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. № 45.
  • Филиппов А.Ф. Элементарное доказательство теоремы Жордана // Успехи математических наук. 1950. Т. 5, Вып. 5(39). C. 173-176.
  • Makarovskikh T., Panyukov A. The Cutter Trajectory Avoiding Intersections of Cuts // IFAC-PapersOnLine. 2017. Vol. 50, Issue 1. P. 2284-2289.
  • Makarovskikh T., Panyukov A. Development of Routing Methods for Cutting out Details // CEUR Workshop Proceedings. 2018. Vol. 2098. P. 249-263. URL: htpp://ceur-ws.org/ Vol-2098 (дата обращения: 20.07.2018).
  • Зыков А.А. Основы теории графов. М.: Вузовская книга, 2004. 664 с.
  • 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. P. 821-826.
  • DOI: 10.1016/j.ifacol.2016.07.876
  • Szeider S. Finding Paths in Graphs Avoiding Forbidden Transitions // Discrete Applied Mathematics. 2003. No. 126. P. 261-273.
  • DOI: 10.1016/S0166-218X(02)00251-2
  • Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. 2007. Vol. 46, No. 1(10). P. 83-92.
  • DOI: 10.1134/S1064230707010108
  • Савицкий Е.А. Использование алгоритма поиска в ширину для определения уровней вложенности ребер плоского графа // Информационные технологии и системы: Труды Третьей междунар. науч. конф. Челябинск: Изд-во ЧелГУ, 2014. C. 43-45.
  • Панюкова Т.А. Цепи с упорядоченным охватыванием в плоских графах // Дискретный анализ и исследование операций. Часть 2. 2006. Т. 13, № 2. С. 31-43.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp