Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 493, № 1, стр. 74-80

ПОСТАНОВКА ЗАДАЧИ

Задача CVRP описывает процедуру выбора экономически эффективного плана удовлетворения пользовательского спроса географически распределенной сети потребителей путем поставок однородной продукции с центрального склада парком (идентичных) транспортных средств заданной грузоподъемности.

Математическая постановка задачи CVRP определяется упорядоченной парой $(G,q)$, где q – натуральное число, верхняя оценка грузоподъемности транспортных средств, а $G = (Z,E,D,w)$ – полный взвешенный граф. Множество вершин графа G имеет вид $Z = X \cup \{ y\} $, где $X = \{ {{x}_{1}}, \ldots ,{{x}_{n}}\} $ – множество потребителей, y – выделенная вершина-склад. Весовые функции $D{\text{:}}\,X \to {{\mathbb{Z}}_{ + }}$ и w: $E \to {{\mathbb{R}}_{ + }}$ задают распределение потребительского спроса и удельные транспортные издержки соответственно.

Маршрутом называется упорядоченная пара $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$, в которой $\pi = y,{{x}_{{{{i}_{1}}}}}, \ldots ,{{x}_{{{{i}_{t}}}}}$, y – не обязательно простой цикл в графе G, а функция ${{S}_{\mathcal{R}}}{\kern 1pt} :\;X \to {{Z}_{ + }}$ определяет распределение потребительского спроса, удовлетворяемого в вершинах цикла π. Cтоимость (вес) маршрута $\mathcal{R}$ задается формулой

Маршрут $\mathcal{R}$ называется допустимым, если

Задача состоит в построении множества допустимых маршрутов $\mathfrak{S}{\kern 1pt} *$ минимальной суммарной стоимости, удовлетворяющих совокупный потребительский спрос, т.е.

Постановка задачи CVRP называется метрической, если весовая функция w удовлетворяет неравенству треугольника:

Мы ограничимся рассмотрением постановок CVRP, в которых $D(x) \equiv 1$ и $(Z,w)$ является конечным метрическим пространством фиксированной размерности удвоения d > 1. Как обычно (см., например, [11]), будем говорить, что метрическое пространство $(Z,w)$ обладает размерностью удвоения d, если для произвольного метрического шара $B({{z}_{0}},R) = \{ z \in Z{\text{:}}\,\,w({{z}_{0}},z) \leqslant R\} $ существует покрытие $B({{z}_{0}},R) \subseteq \bigcup\limits_{j = 1}^M {B\left( {{{z}_{j}},\frac{R}{2}} \right)} $ не более чем 2^d шарами половинного радиуса (с центрами в Z).

Основным результатом данной работы является квазиполиномиальная приближенная схема для рассматриваемой постановки задачи.

Определение 1. Квазиполиномиальной приближенной схемой (QPTAS) для комбинаторной задачи минимизации называется параметризованное семейство алгоритмов, содержащее для каждого фиксированного значения ε > 0 алгоритм, находящий для произвольной постановки задачи (1 + ε)-приближенное решение за время, ограниченное сверху квазиполиномом $O({{n}^{{{\text{poly}}\,log(n)}}})$ от размера записи ее условия¹¹.

Предлагаемый нами алгоритм в целом наследует структуру аппроксимационной схемы Дас–Матье [10] и состоит из следующих основных этапов: предварительной обработки и округления исходной постановки, рандомизированной иерархической кластеризации множества потребителей, ранжирования потребительского спроса, динамического программирования и дерандомизации, описанию которых посвящены последующие разделы статьи.

ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА И ОКРУГЛЕНИЕ

Зададимся произвольным значением ε > 0. Покажем, что любой постановке задачи CVRP может быть сопоставлена вспомогательная округленная постановка, произвольному (1 + ε)-приближенному решению которой соответствует $(1 + O(\varepsilon ))$-приближенное решение исходной задачи, причем все необходимые преобразования могут быть произведены за полиномиальное время.

Пусть $\Delta = {{\Delta }_{w}}(Z) = max\{ w(u,v){\text{:}}\,\,u,v \in Z\} $ – диаметр множества Z. Без ограничения общности полагаем $\Delta = n{\text{/}}\varepsilon $. Для дальнейших построений нам потребуется понятие δ-сети.

Определение 2. Подпространство $N \subseteq Z$ метрического пространства $(Z,w)$ называется δ‑сетью для заданного δ > 0, если:

1) для произвольной точки $u \in Z$ найдется точка $v = v(u)$ ∈ N такая, что $w(u,v) \leqslant \delta $;

2) для любых ${{v}_{1}},{{v}_{2}} \in N$ условие ${{v}_{1}} \ne {{v}_{2}}$ влечет $w({{v}_{1}},{{v}_{2}}) > \delta $.

Задавшись произвольной 1-сетью N₁ = {ξ₁, ... ..., ${{\xi }_{J}}\} \subset Z$, сопоставим исходной постановке задачи CVRP округленную по следующим правилам:

1) произвольным образом разрешая возможную неоднозначность, зададим отображение ξ: $Z \to {{N}_{1}}$ так, чтобы $w(z,\xi (z)) \leqslant 1$ для произвольного $z \in Z$;

2) пусть далее $\eta = \xi (y)$; искомая округленная постановка задается парой $({{G}_{1}},q)$, в которой G₁ = = $G\langle {{N}_{1}}\rangle $ – подграф графа G, индуцированный подмножеством N₁ с выделенной вершиной-складом $\eta = \xi (y)$; весовая функция вершин подграфа ${{G}_{1}}$ задается соотношением

а весовая функция ребер является сужением метрики w на подпространство N₁.

Теорема 1. Произвольному (1 + ε)-приближенному решению полученной округленной постановки может быть сопоставлено $(1 + O(\varepsilon ))$-приближенное решение исходной задачи, причем данное преобразованием может быть произведено за полиномиальное время.

Всюду ниже без ограничения общности полагаем рассматриваемую постановку задачи CVRP округленной.

РАНДОМИЗИРОВАННАЯ ИЕРАРХИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ

Описанная в данном разделе процедура иерархической кластеризации развивает подход, предложенный в работе [12].

Задавшись произвольным $s \geqslant 6$, каждому $l \in \{ 0$, 1, ..., L + 1}, где $L = \left\lceil {lo{{g}_{s}}{{\Delta }_{w}}(Z)} \right\rceil $ = $O(logn$ – logε), сопоставим произвольную ${{s}^{{L - l}}}$-сеть N(l) пространства Z. Заметим, что сеть N(0) одноточечная, а $N(L + 1) = Z$ по построению. Без ограничения общности полагаем выполненным соотношение $N(l) \subset N(l + 1)$ для каждого $0 \leqslant l \leqslant L$.

Искомую рандомизированную иерархическую кластеризацию множества Z строим индукцией по l. При l = 0 вводим единственный кластер $C_{1}^{0}$ = Z. Допустим, кластеризация построена для всех $l{\kern 1pt} ' \leqslant l$ для некоторого $l \leqslant L$. Через Z = $C_{1}^{l}$ ∪ $C_{2}^{l}$ ... ∪ $C_{K}^{l}$ обозначим разбиение множества Z на кластеры на уровне l. Построим кластеризацию на уровне l + 1, для чего разобьем каждый кластер $C_{j}^{l}$ в отдельности следующим образом:

1) зададимся случайной перестановкой $\sigma $ элементов сети $N(l + 1)$;

2) каждому элементу ${{h}_{{\sigma (i)}}} \in N(l + 1)$ сопоставим число $\mu = {{\mu }_{i}}$, равномерно распределенное в промежутке $[1,2)$;

3) подкластер $C_{{ji}}^{{l + 1}} \subset C_{j}^{l}$ зададим соотношением

4) разбиение кластера $C_{j}^{l}$ составим из всех $C_{{ji}}^{{l + 1}} \ne \phi $, построенных по формуле (2). Результирующую кластеризацию множества Z на уровне l  + 1 получим объединением индивидуальных разбиений кластеров $C_{j}^{l}$ уровня l.

Приближенное решение исходной задачи будем искать в классе сетевых r-легких маршрутов [13], согласованных с построенной рандомизированной кластеризацией.

Маршрут $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$ называется сетевым по отношению к иерархии сетей $N(l)$, $l \in \{ 0$, ..., L + 1}, и заданному ε > 0, если для произвольного ребра $\{ u,v\} $ цикла π справедливо следующее

Условие 1. Неравенство

${{s}^{{L - l}}} \leqslant \varepsilon \cdot w(u,v)$ < s^{L – l + 1}

влечет принадлежность вершин $u$ и ${v}$ сети $N(l)$.

В свою очередь, маршрут $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$ называется r-легким, если границы произвольного кластера C уровня l им пересекаются не более r раз, причем исключительно в точках сети $N(l + lo{{g}_{s}}M)$, именуемых порталами. Здесь $M$ – степень $s$, удовлетворяющая соотношению $\tfrac{M}{s} \leqslant \tfrac{{dL}}{\varepsilon } < M$. Нетрудно убедиться, что в произвольном кластере число выбранных таким образом порталов удовлетворяет соотношению $m = {\text{polylog}}(n)$.

Теорема 2. Пусть $d > 1$, $\varepsilon \in \left( {0,\frac{1}{8}} \right)$ и $r = m$. Произвольному допустимому решению $\mathfrak{S}$ задачи CVRP соответствует допустимое решение $\tilde {\mathfrak{S}}$, состоящее из сетевых r-легких маршрутов, так что $\mathbb{E}(w(\tilde {\mathfrak{S}})) = (1 + O(\varepsilon ))w(\mathfrak{S}),$ где усреднение производится по множеству случайных иерархических кластеризаций.

РАНЖИРОВАНИЕ СПРОСА И СТРУКТУРИРОВАННЫЕ РЕШЕНИЯ

Пусть $\mathcal{R}$ – произвольный сетевой r-легкий маршрут, пересекающий границы некоторого кластера C. Максимальный по включению фрагмент²²

маршрута $\mathcal{R}$, целиком принадлежащий кластеру C, назовем (пересекающим) сегментом маршрута $\mathcal{R}$.

Для ранжирования потребительского спроса зададим пороги округления t_i, i ∈ $\left\{ {_{{_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}}}} \right.$1, ... Λ = = $\left. {\left\lceil {{{{\log }}_{{1 + \varepsilon /(L + 1)}}}(q\varepsilon ) + \frac{1}{\varepsilon }} \right\rceil } \right\}$, определяемые соотношением

Каждой единице спроса произвольного потребителя x сопоставим целое число ${\mathbf{r}} \in [0,L + 1]$, именуемое рангом.

В зависимости от величины ранга и уровня кластера, содержащего конкретного потребителя $x$, единицы его спроса могут быть активными и неактивными. Произвольная единица спроса ранга r активна по отношению к любому кластеру уровня $l > {\mathbf{r}}$ и не активна в противном случае. По определению, единицы спроса ранга 0 активны на произвольном уровне кластеризации.

Сегмент $\sigma $, пересекающий границы кластера $C_{j}^{l}$, называется округленным, если он удовлетворяет в точности t единиц активного спроса, где t – одно из пороговых значений, определяемых формулой (4). В противном случае $\sigma $ называется неокругленным сегментом.

Определение 3. Множество $\mathfrak{S}$ сетевых r‑легких маршрутов, удовлетворяющее совокупный потребительский спрос, называется структурированным решением, если найдется подходящее ранжирование спроса, удовлетворяющее приведенным ниже условиям:

1) произвольный маршрут $\mathcal{R} \in \mathfrak{S}$ покрывает не более $q$ единиц спроса ранга 0;

2) если на уровне $l$ маршрут $\mathcal{R}$ удовлетворяет в точности $t$ единиц активного спроса, то на уровне l + 1 объем покрываемого им активного спроса не превосходит $t\left( {1 + \frac{\varepsilon }{{L + 1}}} \right)$ единиц;

3) если число сегментов произвольного маршрута $\mathcal{R} \in \mathfrak{S}$, пересекающих границы кластера $C$, не превышает порога

то каждый сегмент является неокругленным, в противном случае все сегменты маршрута $\mathcal{R}$ – округленные.

Через ${{\mathfrak{S}}_{{DP}}}$ обозначим произвольное структурированное решение, доставляющее минимум вспомогательной целевой функции

в которой $c(\mathcal{R},l)$ – число пересечений маршрутом $\mathcal{R}$ границ кластеров на уровне l. Приведенная ниже теорема характеризует аппроксимационные свойства решения ${{\mathfrak{S}}_{{DP}}}$.

Теорема 3. В условиях теоремы 2 справедливо равенство

в котором усреднение производится по всем случайным иерархическим кластеризациям.

Если структурированное решение ${{\mathfrak{S}}_{{DP}}}$ удовлетворяет ограничению на грузоподъемность, оно, очевидно, является искомым, по теореме 3.

В противном случае произведем рандомизированное ранжирование спроса, применив алгоритм, предложенный в работе [10]. Далее, через ${{\mathfrak{S}}_{{black}}}$ обозначим частичное решение, полученное из ${{\mathfrak{S}}_{{DP}}}$ исключением из рассмотрения всех единиц спроса ранга r > 0.

Для удовлетворения исключенного спроса сформулируем вспомогательную постановку задачи CVRP, для поиска приближенного решения ${{\mathfrak{S}}_{{red}}}$ которой воспользуемся классическим алгоритмом итерированного разбиения маршрута (ITP) [3]. Объединение найденных частичных решений ${{\mathfrak{S}}_{{black}}}$ и ${{\mathfrak{S}}_{{red}}}$ является искомым $(1 + O(\varepsilon ))$-приближенным решением исходной задачи.

Теорема 4. Пусть исходная постановка CVRP задана в метрическом пространстве удвоения d > 1, $r = m$ и $\varepsilon \in \left( {0,\frac{1}{8}} \right)$. Решение ${{\mathfrak{S}}_{{black}}} \cup {{\mathfrak{S}}_{{red}}}$ допустимо и его стоимость удовлетворяет соотношению

в котором усреднение производится по всем случайным кластеризациям и ранжированиям спроса.

В следующем разделе мы опишем процедуру динамического программирования, обеспечивающую эффективное построение структурированного решения ${{\mathfrak{S}}_{{DP}}}$.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Сопоставим случайной реализации иерархической кластеризации таблицу динамического программирования, каждая ячейка которой индексируется упорядоченной парой $(C,\mathfrak{C})$, где C – произвольный кластер уровня $l \in \{ 0,L + 1\} $, а $\mathfrak{C}$ – конфигурация, описывающая структуру сегментов (3), пересекающих его границу, и хранит минимальное возможное для заданных C и $\mathfrak{C}$ частичное значение функции F.

Произвольный такой сегмент договоримся кодировать кортежем $({{p}^{{in}}},{{p}^{{out}}},{\mathbf{s}},{\mathbf{d}})$, где s обозначает объем удовлетворяемого сегментом активного пользовательского спроса, а d – индикатор посещения склада. В зависимости от числа характеризуемых сегментов договоримся различать округленные и неокругленные конфигурации.

Неокругленной конфигурацией называется конечная последовательность кортежей $((p_{\nu }^{{in}},p_{\nu }^{{out}}$, s_ν, d_ν): ν = 1, ..., k_u), каждый элемент которой описывает один из не более чем $\gamma $ неокругленных сегментов (см. соотношение (5)).

В свою очередь, округленная конфигурация – это множество упорядоченных пар $\{ ({{s}_{\nu }},{{m}_{\nu }}){\kern 1pt} $: ν = = 1, ..., k_r}, каждая из которых определяет общую структуру ${{s}_{\nu }} = (p_{\nu }^{{in}},p_{\nu }^{{out}},{{t}_{\nu }},{{{\mathbf{d}}}_{\nu }})$ в точности ${{m}_{\nu }}$ округленных сегментов.

Заполнение таблицы динамического программирования ведем в порядке убывания l, начиная с ячеек (L + 1)-го уровня, вычисляемых очевидным образом. Вычислим значение ячейки $(C,\mathfrak{C})$ для произвольного кластера C уровня $l \leqslant L$ и произвольной конфигурации $\mathfrak{C}$.

Пусть $C = C_{1}^{{l + 1}} \cup C_{2}^{{l + 1}} \cup \ldots \cup C_{K}^{{l + 1}}$. Согласно подходу, предложенному в [10], значение ячейки $(C,\mathfrak{C})$ вычисляется методом двухэтапной минимизации частичной функции F алгоритмом полного перебора:

1) перебрать все допустимые комбинации

вычисленных ранее ячеек, соответствующих подкластерам

2) для каждой комбинации (7) перебрать все способы “склейки” сегментов, описываемых дочерними конфигурациями, с целью построения совместимой с конфигурацией $\mathfrak{C}$ и оптимальной с точки зрения функции F совокупности сегментов, пересекающих границу кластера C, при необходимости дополненных целиком содержащимися в нем циклическими маршрутами.

Рекурсивная процедура завершается вычислением единственной ячейки 0-го уровня $(Z,{{\mathfrak{C}}_{0}})$ для пустой конфигурации ${{\mathfrak{C}}_{0}}$, значение которой совпадает со стоимостью $F({{\mathfrak{S}}_{{DP}}})$ искомого структурированного решения ${{\mathfrak{S}}_{{DP}}}$.

Трудоемкость описанного выше алгоритма динамического программирования определяется трудоемкостью ${{(nr)}^{{{{{(logn)}}^{{\Theta (r)}}}}}}$ второго этапа. Данная оценка, очевидно, квазиполиномиальна при произвольном фиксированном r, что, вследствие известной структурной теоремы С. Ароры [14], влечет квазиполиномиальность временной сложности оригинальной схемы Дас–Матье [10] в произвольном конечномерном евклидовом пространстве.

Однако в метрических пространствах фиксированной размерности удвоения теорема Ароры, вообще говоря, перестает быть верной. Утверждение заменяющей ее теоремы 2 верно лишь при условии $r = {\text{polylog}}(n)$, при котором данный алгоритм становится экспоненциальным даже в случае произвольной фиксированной грузоподъемности q > 2, для которого обоснована [5] аппроксимируемость в классе полиномиальных приближенных схем (PTAS).

В следующем разделе приведен усовершенствованный вариант описанного выше алгоритма, обладающий квазиполиномиальной трудоемкостью, в котором полный перебор на шаге 2 заменен вспомогательной схемой динамического программирования.

ЭФФЕКТИВНАЯ ПРОЦЕДУРА СЛИЯНИЯ СЕГМЕНТОВ

Для краткости изложения рассмотрим случай, когда кластер $C$ уровня $l$ не содержит склада, а конфигурации $\mathfrak{C} = \{ ({{s}_{i}},{{m}_{i}}){\text{:}}\,\,i = 1,...,{{k}_{\mathfrak{C}}}\} $, ${{s}_{{{{i}_{1}}}}} \ne {{s}_{{{{i}_{2}}}}}$ и $\mathfrak{C}_{u}^{{l + 1}}$ = $\{ (s_{k}^{u},m_{k}^{u}){\text{:}}\,\,k = 1,...,{{k}_{u}}\} $, $s_{{{{k}_{1}}}}^{u} \ne s_{{{{k}_{2}}}}^{u}$, $u = 1,...,K$ являются округленными.

Нам потребуется несколько дополнительных обозначений. Введем в рассмотрение множество

где ${{\sigma }_{0}}$ – пустой кортеж, используемый для выравнивания длины строящихся сегментов.

Профилем конкатенации будем называть произвольную последовательность φ = $({{\sigma }_{{{{i}_{1}}}}}, \ldots ,{{\sigma }_{{{{i}_{{\bar {r}}}}}}}) \in {{\bar {S}}^{{\bar {r}}}}$, где $\bar {r} = K \cdot r$, удовлетворяющую условию

По определению, произвольный профиль φ задает способ слияния (конкатенации) сегментов, соответствующих дочерним конфигурациям. По смыслу задачи, каждой паре $({{s}_{i}},{{m}_{i}}) \in \mathfrak{C}$ должно быть сопоставлено семейство Φ_i = $({{\varphi }_{{i,1}}}, \ldots ,{{\varphi }_{{i,{{m}_{i}}}}})$ не обязательно различных профилей конкатенации, согласованное с конфигурациями ${{\mathfrak{C}}_{1}}, \ldots ,{{\mathfrak{C}}_{K}}$ и доставляющее минимум целевой функции F.

Ресурсной матрицей назовем трехиндексную таблицу A размера $[{{k}_{\mathfrak{C}}} \times (\mathcal{K} + 1) \times \bar {r}]$, элемент $a_{{i,\nu }}^{p}$ которой определяет кратность использования кортежа ${{\sigma }_{\nu }} \in \bar {S}$ на p-й позиции строящихся профилей конкатенации, элементов семейства Φ_i. Наш алгоритм основан на переборе ресурсных матриц, число которых, в отличие от числа вариантов слияния дочерних сегментов, перебираемых на шаге 2) алгоритма Дас–Матье, остается квазиполиномиальным даже в рассматриваемых метрических пространствах. Кроме того, фиксация произвольной ресурсной матрицы A обеспечивает естественную декомпозицию задачи, допуская независимое (параллельное) построение оптимальных семейств ${{\Phi }_{i}}$, $i = 1,...,{{k}_{\mathfrak{C}}}$.

Внутреннее динамическое программирование. Предполагая ресурсную матрицу A и номер $i \in \{ 1,{{k}_{\mathfrak{C}}}\} $ заданными, опишем процедуру построения оптимального семейства профилей конкатенации ${{\Phi }_{i}}$, соответствующего подматрице ${{A}_{i}} = {\text{||}}a_{{i,\nu }}^{p}{\text{||}},$ $p = 1,\,\,...{\text{,}}\,\bar {r},$ $\nu = 0,...,\mathcal{K}$. Произвольная ячейка таблицы предлагаемой дополнительной схемы динамического программирования индексируется упорядоченной парой $(p,{{H}_{p}})$, в которой матрица ${{H}_{p}} = {\text{||}}h_{{\nu ,c}}^{p}{\text{||}}$, $\nu = 0,...,\mathcal{K}$, $c = 0,...,q$ описывает структуру семейства $\Phi _{i}^{{(p)}}$ частичных профилей конкатенации длины p: элемент $h_{{\nu ,c}}^{p}$ равен числу профилей, каждый из которых оканчивается кортежем ${{\sigma }_{\nu }}$ и удовлетворяет в точности c единиц активного спроса.

Значение ячейки $(p,{{H}_{p}})$ задается соотношением

Здесь целевая функция $\bar {F}(\Phi _{i}^{{(p)}}) = \sum\limits_{j = 1}^{{{m}_{i}}} {\overline {{\text{cost}}} (\varphi _{{i,j}}^{{(p)}})} ,$ в которой

для произвольного частичного профиля φ^(p) = = $({{\sigma }_{{{{i}_{1}}}}}, \ldots ,{{\sigma }_{{{{i}_{p}}}}})$ и получена естественной редукцией функции F. В случае $\bar {D}(p,{{H}_{p}}) = \infty $ ячейка $(p,{{H}_{p}})$ полагается недопустимой и исключается из рассмотрения.

Заполнение таблицы динамического программирования проводится в порядке возрастания $p$. Значение единственной ячейки $(1,{{H}_{1}})$ однозначно определяется подматрицей ${{A}_{i}}$. Предполагая далее все ячейки $(p{\kern 1pt} ',{{H}_{{p{\kern 1pt} '}}})$ для произвольного $p{\kern 1pt} ' < p$ заполненными, вычислим значение ячейки $(p,{{H}_{p}})$ для произвольной матрицы H_p, совместимой с A_i, рекурсивно, пользуясь уравнением Беллмана

Здесь элемент $x_{{{{\nu }_{1}},{{\nu }_{2}}}}^{c}$ трехиндексной матрицы перехода X между состояниями $(p - 1,{{H}_{{p - 1}}}(X))$ и $(p,{{H}_{p}})$ определяет число частичных профилей конкатенации, завершающихся кортежами ${{\sigma }_{{{{\nu }_{1}}}}}$ и ${{\sigma }_{{{{\nu }_{2}}}}}$ и удовлетворяющих в точности c единиц активного спроса, а минимизация ограничена матрицами X, для которых ячейка $(p - 1,{{H}_{{p - 1}}}(X))$ является допустимой.

Стоимость искомого семейства профилей конкатенации ${{\Phi }_{i}}$ содержится в ячейке $(\bar {r},H_{{\bar {r}}}^{*})$ = = $argmin\{ \bar {D}(\bar {r},{{H}_{{\bar {r}}}})\} $, при этом значение $(\bar {r},H_{{\bar {r}}}^{*})\, = \,\infty $ свидетельствует о том, что для подматрицы A_i (а значит, и для всей ресурсной матрицы A) решение отсутствует.

ОСНОВНОЙ РЕЗУЛЬТАТ

В следующей теореме сформулированы свойства описанной выше аппроксимационной схемы.

Теорема 5. Для постановки CVRP в метрическом пространстве фиксированной размерности удвоения d > 1 $(1 + O(\varepsilon ))$-приближенное решение может быть найдено рандомизированным приближенным алгоритмом за время ${\text{poly}}(n) \cdot {{n}^{{O({{m}^{4}}{{L}^{2}}qlo{{g}^{2}}q)}}}$, где $m = O\left( {\mathop {\left( {\tfrac{{d(logn - log\varepsilon )}}{\varepsilon }} \right)}\nolimits^d } \right)$ и $L = O(logn - log\varepsilon )$. Алгоритм допускает эффективную дерандомизацию.

Из условий теоремы 5 следует, что предложенная схема является рандомизированной QPTAS при $q = O({\text{polylog}}(n))$. Для эффективной дерандомизации схемы может быть применен известный подход, опирающийся на результаты [10] и [12].