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

Задача маршрутизации транспорта ограниченной грузоподъемности (Capacitated Vehicle Routing Problem, CVRP) – одна из классических проблем комбинаторной оптимизации, обладающая широким спектром важных практических приложений в исследовании операций. Как и большинство известных комбинаторных задач, CVRP NP-трудна в сильном смысле и сохраняет труднорешаемость даже на евклидовой плоскости. В метрической постановке задача CVRP APX-полна, что исключает ее аппроксимацию с произвольной заданной точностью в классе алгоритмов полиномиальной трудоемкости (в рамках гипотезы $P\ne NP$ ). В то же время для случая конечномерных евклидовых пространств подход, опирающийся на работы С. Ароры, А. Дас и К. Матье, позволил обосновать аппроксимируемость задачи в классе квазиполиномиальных и даже полиномиальных приближенных схем. В данной работе впервые удалось распространить этот подход на существенно более широкий класс метрических пространств с фиксированной размерностью удвоения. Показано, что задача CVRP, сформулированная в таком пространстве, обладает квазиполиномиальной приближенной схемой каждый раз, когда число маршрутов в ее оптимальном решении ограничено сверху полиномом от логарифма длины записи условия задачи.
Библ. 37.