Математические модели и алгоритмы маршрутизации для САПР технологической подготовки процессов раскроя

К ресурсосберегающим технологиям раскроя листового материала относятся технологии ICP и ECP, допускающие совмещение фрагментов контуров вырезаемых деталей. В статье изложены математическая модель проблемы вырезания деталей при использовании данных технологий и алгоритмы нахождения маршрутов режущего инструмента, удовлетворяющих технологическим ограничениям. Дано решение проблемы представления раскройного плана в виде плоского графа $G=(V,F,E)$, являющегося гомеоморфным образом раскройного плана. Это позволило формализовать технологические ограничения на траекторию вырезания деталей по раскройному плану и предложить серию алгоритмов построения маршрута в графе $G=(V,F,E)$, являющемся образом допустимой траектории. Используя известные координаты прообразов вершин графа $G=(V,F,E)$ и размещения фрагментов раскройного плана, являющихся прообразами ребер графа $G=(V,F,E)$, найденный маршрут в графе $G=(V,E)$ можно интерпретировать как траекторию режущего инструмента.
Предложенные алгоритмы нахождения маршрутов в связном графе $G$ имеют полиномиальную вычислительную сложность. Для нахождения оптимального маршрута в несвязном графе $G$ необходимо для каждой разделяющей грани $f$ графа $G$ решение задачи коммивояжера на множестве граней, смежных $f$.