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

Аннотация: доклад на данном расширенном заседании семинара посвящен описанию результатов кандидатской диссертации, которые состоят в следующем:
1. Обоснована аппроксимируемость постановок NP-трудной задачи CVRP в классах QPTAS и PTAS, заданных в метрических пространствах произвольной размерности удвоения. В частности:
a) показано, что схема Хаймовича-Ринной Кана сохраняет свои аппроксимативные свойства при тех же ограничениях на рост параметров, для которых она была сформулирована на евклидовой плоскости;
b) установлена аппроксимируемость в классе QPTAS для постановок CVRP, оптимальное решение которых состоит из не более, чем $polylog(n)$ маршрутов;
c) наиболее общий для конечномерных пространств результат Дас-Матье распространен на случай упоминаемых выше пространств при дополнительном условии на грузоподъемность $q=polylog(n).$
2. Для геометрических постановок CVRP:
a) впервые обоснована аппроксимируемость задачи CVRP с дополнительным ограничением на временные промежутки обслуживания (CVRPTW) в классах PTAS при $q=o(loglog n)$ и $p=o(loglog n),$ и EPTAS при произвольных фиксированных $q$ и $p;$
b) для постановок CVRP, стесненных ограничениями на временные промежутки обслуживания и неоднородность клиентского спроса, построена PTAS с рекордной верхней оценкой грузоподъемности $q <= 2^{log^\delta n},$ где $\delta=O(\varepsilon).$