Квазипирамидальные маршруты для обобщенной задачи коммивояжера

Пирамидальные маршруты являются широко известными объектами, рассматриваемыми в контексте классической Задачи коммивояжера (TSP) и десятилетиями притягивают интерес многочисленных исследователей. Хорошо известно, что для произвольной матрицы транспортных издержек оптимальный пирамидальный маршрут может быть найден за время O(n 2 ), а в случае евклидовой метрики задача обладает точными алгоритмами с субквадратичной трудоемкостью. Известны также условия В.Демиденко и Дж. Ван дер Веена, гарантирующие существование оптимальных пирамидальных маршрутов (и, как следствие, полиномиальную разрешимость соответствующих постановок). Мы предлагаем обобщение опианных выше результатов на случай Обобщенной задачи коммивояжера (GTSP), в которой частичный порядок на множестве вершин определяется неявным образом линейным порядком на множестве кластеров. Введя понятие l-квазипирамидального маршрута, мы показываем, что потимальный квазипирамидальный маршрут может быть найден за полиномиальное время при каждом фиксированном значении параметра l. Кроме того, мы приводим описание нетривиального полиномиально разрешимого подкласса задачи GTSP и обосновываем разрешимость каждой его частной постановки в классе квазипирамидальных маршрутов.