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

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