Актуальность темы. Предмет исследования диссертационной работы составляют труднорешаемые оптимизационные задачи, являющиеся обобщениями классической задачи коммивояжера (Traveling Salesman
Problem, TSP). В работе исследуются: задача о цикловом покрытии
фиксированной мощности k минимального веса (Minimum-weight k-Size
Cycle Cover Problem, Min-k-SCCP), обобщенная задача коммивояжера
(Generalized Traveling Salesman Problem, GTSP) и её геометрическая постановка евклидова обобщенная задача коммивояжера на сетке (Euclidean
Generalized Traveling Salesman Problem in k Grid Clusters, EGTSP-k-GC).
Результаты для близких постановок маршрутных задач были получены в работах Э.Х. Гимади, А.А. Агеева, Б. Манти, А.Г. Ченцова,
А. Григорьева и др.
Задача о цикловом покрытии графа фиксированного размера k минимального веса — это задача комбинаторной оптимизации, заключающаяся
в поиске оптимального покрытия полного взвешенного графа k вершиннонепересекающимися циклами. На содержательном уровне каждый цикл в
покрытии может трактоваться как маршрут для некоторого транспортного средства, посещающего соответствующее множество клиентов. С этой
точки зрения задача о цикловом покрытии близка к известной задаче
маршрутизации транспорта (Vehicle Routing Problem, VRP). С другой
стороны, при фиксированной единичной мощности циклового покрытия
задача совпадает с классической задачей коммивояжера. Кроме того, задача о цикловом покрытии мощности k занимает промежуточное положение в сложностной иерархии между эффективно разрешимой задачей
о назначениях и труднорешаемой задачей коммивояжера, что индуцирует дополнительный теоретический интерес к исследованию сложности и
аппроксимируемости Min-k-SCCP.
Постановка обобщенной задачи коммивояжера (Generalized Traveling
Salesman Problem, GTSP), известной в отечественной литературе под названием «задача обхода мегаполисов», задается полным взвешенным графом, множество вершин которого разбито на k непересекающихся кластеров, и заключается в поиске цикла минимального веса посещающего
каждый кластер.
