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

Задача об оптимальной маршрутизации с ограничением на грузоподъемность транспортных средств (CVRP) является одной из классических задач комбинаторной оптимизации и обладает широким спектром приложений в исследовании операций. Поскольку задача CVRP $NP$-трудна и сохраняет труднорешаемость, даже будучи сформулированной в конечномерном евклидовом пространстве, традиционно особое внимание уделяется вопросам ее аппроксимируемости. Большая часть известных результатов в области приближенных алгоритмов и полиномиальных приближенных схем для данной задачи получены для ее частной постановки на евклидовой плоскости. В данной работе показывается, что подход, предложенный М.Хаймовичем и А.Ринноем Каном в 1985 г. для разработки полиномиальных приближенных схем для планарной задачи с единственным складом, успешно может быть применен и в более общем случае, например, в пространствах произвольной фиксированной размерности и при произвольном числе складов.