Построение самонепересекающихся OE-маршрутов в плоском эйлеровом графе
Автор: Макаровских Татьяна Анатольевна
Статья в выпуске: 4 т.8, 2019 года.
Бесплатный доступ
В статье предложен полиномиальный алгоритм построения самонепересекающегося маршрута с упорядоченным охватыванием в плоском эйлеровом графе. Предложенный подход состоит в расщеплении всех вершин исходного графа степени выше 4 и введении фиктивных вершин и ребер, сводя, таким образом, исходную задачу к решенной ранее автором задаче построения A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. Приведенный алгоритм сведения решает поставленную задачу за полиномиальное время. Рассмотрен тестовый пример построения самонепересекающейся цепи с упорядоченным охватыванием. Данная задача возникает при технологической подготовке процесса раскроя, когда требуется определить маршрут движения режущего инструмента, при котором отсутствуют самопересечения траектории резки и отрезанная от листа часть не требует разрезаний. Раскройный план представлен в виде плоского графа, являющегося его гомеоморфным образом. Предложенный в статье алгоритм решает проблему маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента одновременно наложены такие технологические ограничения.
Плоский граф, маршрут, раскройный план, полиномиальный алгоритм, процесс раскроя
Короткий адрес: https://sciup.org/147233206
IDR: 147233206 | DOI: 10.14529/cmse190403
Список литературы Построение самонепересекающихся OE-маршрутов в плоском эйлеровом графе
- 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. P. 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. P. 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. 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. 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). P. 5965-5984.
- DOI: 10.1080/00207543.2014.895064
- Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации перемещений при листовой резке деталей // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 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.
- 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. P. 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. P. 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. Vol. 3(1). 1984. P. 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). P. 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
- Макаровских Т.А. Программное обеспечение для построения A-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2019. Т. 8, № 1. С. 36-53.
- DOI: 10.14529/cmse190103
- Филиппов А.Ф. Элементарное доказательство теоремы Жордана // Успехи математических наук. 1950. Т. 5:5(39). С. 173-176.
- 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. no. 45.
- Panyukova T.A. Constructing of OE-postman Path for a Planar Graph // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2014. Т. 7, № 4. С. 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. P. 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. P. 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. P. 261-273.
- DOI: 10.1016/S0166-218X(02)00251-2
