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

Задача маршрутизации транспорта с временными окнами (CVRPTW) является широко извстной задачей комбинаторной оптимизации имеющей огромное число приложений в исследовании операций. В отличие от классической постановки задачи CVRP, которая не учитывает временные промежутки обслуживания, аппроксимационные алгоритмы с гарантированными оценками точности для задачи CVRPTW до сих пор мало изучены, даже для случая евклидовой плоскости. В данной работе мы предлагаем, возможно, первую аппроксимационную схему для постановки задачи CVRPTWна плоскости с неединичным делимым спросом, сочетая хорошо известную схему декомпозиции задачи, разработанную A.Adamaszeketel., и квазиполиномиальную приближённую аппроксимационную схему (QPTAS), предложенную L.Songetal. Предложенная нами схема для любогоε∈(0,1)находит (1+ε)-приближённое решение задачи за полиномиальное время при условии, что трудоёмкость qи число временных промежутков обслуживания pне превосходит 2^(〖log〗^δ n)для некоторого δ=O(ε). Также, данная схема является эффективной полиномиальной (EPTAS) для любых фиксированных значений параметров pи qс субквадратичной трудоёмкостью.