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

Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного $\varepsilon>0$ за время $\mathrm {TIME}(\mathrm {TSP},\rho,n)+O(n^2)+ O\bigl( e^{O(q\,(\frac{q}{\varepsilon})^3(p\rho)^2 \log (p\rho))}\bigr)$ находит $(1+\varepsilon)$-приближенное решение задачи CVRPTW на евклидовой плоскости, где $q$ - верхняя оценка грузоподъемности транспортных средств, $p$ - число промежутков обслуживания (временных окон) и $\mathrm {TIME}(\mathrm {TSP},\rho,n)$ - трудоемкость поиска $\rho$-приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой $p^3q^4=O(\log n)$, и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения $p$ и $q$.