Программные продукты и системы

Программное обеспечение для решения многих задач дискретной оптимизации основано на математической модели обобщенной задачи коммивояжера (Generalized Traveling Salesman Problem, GTSP), одной из самых известных задач комбинаторной оптимизации, заинтересовавшей многих исследователей. В GTSP для заданного взвешенного орграфа  G = (V, E, c) и разбиения V1 È … È Vm набора узлов V графа G на непустые взаимно непересекающиеся кластеры требуется найти замкнутый тур с минимальной стоимостью, который посещает каждый кластер Vi точно один раз.

В данной статье рассматривается обобщенная задача коммивояжера с ограничениями предшествования (Precedence Constrained Ge- neralized Traveling Salesman Problem, PCGTSP), каждому допустимому маршруту которой необходимо посещать кластеры в соответствии с заданным частичным порядком. Эта модификация задачи GTSP имеет множество практических применений, среди которых следующие: оптимизация траектории инструмента для станков с ЧПУ, минимизация времени и стоимости резки в процессе раскроя листового металла, настройка координатно-измерительного оборудования, оптимизация траектории при множественном сверлении отверстий.

Подробное описание дается в статье «Программное обеспечение для решения обобщенной задачи коммивояжера с ограничениями предшествования», авторы Петунин А.А., Уколов С.С., Хачай М.Ю. (Уральский федеральный университет им. первого Президента России Б.Н. Ельцина, а также Институт математики и механики им. Н.Н. Красовского УрО РАН, г. Екатеринбург).