1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 61, № 7, 2021

Журнал вычислительной математики и математической физики, 2021, T. 61, № 7, стр. 1206-1219

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

Ю. Ю. Огородников 1, 2, *, М. Ю. Хачай 1, 2, 3, **

1 ФГБУ ИММ им. Н.Н. Красовского УрО РАН
620990 Екатеринбург, ул. Софьи Ковалевской, 16, Россия

2 Уральский федеральный ун-т
620075 Екатернбург, пр-т Ленина, 51, Россия

3 Омский гос. техн. ун-т
644050 Омск, пр-т Мира, 11, Россия

* E-mail: yogorodnikov@gmail.com
** E-mail: mkhachay@imm.uran.ru

Поступила в редакцию 26.11.2020
После доработки 26.11.2020
Принята к публикации 11.03.2021

Полный текст (PDF)

Аннотация

Задача маршрутизации транспорта ограниченной грузоподъемности (Capacitated Vehicle Routing Problem, CVRP) – одна из классических проблем комбинаторной оптимизации, обладающая широким спектром важных практических приложений в исследовании операций. Как и большинство известных комбинаторных задач, CVRP NP-трудна в сильном смысле и сохраняет труднорешаемость даже на евклидовой плоскости. В метрической постановке задача CVRP APX-полна, что исключает ее аппроксимацию с произвольной заданной точностью в классе алгоритмов полиномиальной трудоемкости (в рамках гипотезы $P \ne NP$). В то же время для случая конечномерных евклидовых пространств подход, опирающийся на работы С. Ароры, А. Дас и К. Матье, позволил обосновать аппроксимируемость задачи в классе квазиполиномиальных и даже полиномиальных приближенных схем. В данной работе впервые удалось распространить этот подход на существенно более широкий класс метрических пространств с фиксированной размерностью удвоения. Показано, что задача CVRP, сформулированная в таком пространстве, обладает квазиполиномиальной приближенной схемой каждый раз, когда число маршрутов в ее оптимальном решении ограничено сверху полиномом от логарифма длины записи условия задачи. Библ. 37.

Ключевые слова: задача маршрутизации транспорта с ограничением на грузоподъемность (CVRP), квазиполиномиальная приближенная схема (QPTAS), метрическое пространство, размерность удвоения.

ВВЕДЕНИЕ

Задача маршрутизации транспортных средств ограниченной грузоподъемности (Capacitated Vehicle Routing Problem, CVRP) является одной из наиболее известных и активно изучаемых комбинаторных задач, обладающей широким спектром значимых приложений в области исследования операций (см. [1]–[3]). По-видимому, впервые постановка задачи маршрутизации была сформулирована Г. Данцигом и Дж. Рамсером в классической работе [4], посвященной математическому моделированию процесса снабжением топливом сети заправочных станций.

Как и для большинства современных задач комбинаторной оптимизации, исследования в области алгоритмического анализа CVRP традиционно развиваются в рамках следующих основных направлений. Первое направление основано на редукции исходной задачи к подходящей постановке задачи целочисленного (смешанного) программирования с последующим поиском оптимального решения последней с помощью той или иной модификации метода ветвей и границ (см. обзор в [3]). К сожалению, несмотря на стремительные темпы развития вычислительной техники и очевидные успехи последних лет в области совершенствования алгоритмов (см., например, [5]–[8]), практическая применимость данного подхода по-прежнему ограничена постановками достаточно скромного размера ввиду известной NP-трудности задачи CVRP.

Широкий спектр современных эвристических алгоритмов и метаэвристик составляет основу второго направления. Наибольшего успеха в области эффективной аппроксимируемости задачи удалось достичь в классах методов локального поиска (см. [9], [10]), поиска с запретами (см. [11]), переменных окрестностей (VNS) (см. [12], [13]), методов машинного обучения (см. [14]), эволюционных (см. [15]) и биоинспирированных алгоритмов (см. [16], [17]), а также их комбинаций (см. [18], [19]). Нередко эвристические алгоритмы демонстрируют потрясающую производительность, эффективно находя близкие к оптимальным или даже оптимальные решения для отдельных постановок CVRP чрезвычайно большого размера. Тем не менее в отсутствие теоретически обоснованных гарантий применение этих алгоритмов сопряжено с дополнительными трудозатратами, связанными с численным оцениванием их точности и возможной дополнительной настройкой внутренних параметров при переходе к каждому новому классу постановок.

Перечисленные аргументы подтверждают актуальность третьего направления, связанного с аппроксимируемостью задачи в классе эффективных алгоритмов с теоретическими оценками точности и трудоемкости. Как известно, задача CVRP NP-трудна в сильном смысле, являясь обобщением классической задачи коммивояжера (TSP), и сохраняет труднорешаемость (при условии, что грузоподъемность $q$ является частью входа) даже на евклидовой плоскости (см. [20]). Задача не аппроксимируема в общем случае (при $P \ne NP$), APX-полна при произвольной метрике (см. [21], [22]) и остается APX-трудной при произвольной фиксированной грузоподъемности $q \geqslant 3$.

Наибольших успехов в области аппроксимируемости задачи CVRP удалось достичь в конечномерных числовых пространствах. Известные результаты в этой области восходят к классическим работам М. Хаймовича, А. Ринной Кана (см. [22]) и С. Ароры (см. [23]). На данный момент наиболее общим результатом для задачи CVRP на евклидовой плоскости является квазиполиномиальная приближенная схема (QPTAS) А. Дас и К. Матье (см. [24]). Вводя ограничение на рост грузоподъемности $q$, удается обосновать и полиномиальные приближенные схемы (PTAS), среди которых рекордным на данный момент является алгоритм (см. [25]), позволяющий за полиномиальное время найти $(1 + \varepsilon )$-приближенное решение задачи при условии $q \leqslant {{2}^{{lo{{g}^{{\delta (\varepsilon )}}}n}}}$. Подход, предложенный в [22], удалось распространить на модификации задачи в числовых пространствах произвольной фиксированной размерности (см. [26]–[28]), учитывающие дополнительные ограничения на временные промежутки обслуживания (см. [29], [30]) и неоднородность спроса (см. [31]).

Так или иначе до последнего времени полиномиальные и квазиполиномиальные приближенные схемы удавалось обосновать лишь для геометрических постановок задачи CVRP, за исключением, быть может, немногочисленных специальных случаев, описанных в [32], [33]. Долгое время до появления пионерских работ К. Талвара (см. [34]) и Я. Бартала и соавт. (см. [35]), аналогичным образом складывалась ситуация и с аппроксимируемостью близкой к CVRP задачи коммивояжера. Предложенный в этих работах подход позволил распространить классический результат С. Ароры (см. [23]) на существенно более широкий класс постановок задачи коммивояжера, задаваемых в метрических пространствах произвольной фиксированной размерности удвоения (o существовании полиномиальных приближенных схем (PTAS) для TSP в ${{\mathbb{R}}^{d}}$).

В данной статье в развитие близкого подхода к подходу А. Дас и К. Матье впервые обосновывается возможность построения квазиполиномиальной схемы для задачи CVRP, сформулированной в метрическом пространстве произвольной фиксированной размерности удвоения. Рассуждения проведены для частого случая задачи, стесненной дополнительным ограничением на число маршрутов в ее оптимальном решении.

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

Содержательная постановка задачи CVRP может быть задана следующим образом. Имеется множество потребителей $X$, каждый из которых обладает единичным спросом на однородную продукцию, хранящуюся на складе $y$. На складе базируются идентичные транспортные средства фиксированной грузоподъемности $q$, используемые для удовлетворения потребительского спроса. Задача состоит в построении набора циклических маршрутов, удовлетворяющего совокупный потребительский спрос и минимизирующего суммарные транспортные издержки так, чтобы каждый из маршрутов начинался и завершался на складе $y$ и удовлетворял ограничению нагрузоподъемность $q$.

Для последующих построений наряду с классической постановкой задачи CVRP нам потребуется ее обобщение, известное в литературе как задача маршрутизации транспорта с ограниченной грузоподъемностью и неоднородным разделяемым спросом (CVRP-SD).

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

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

Стоимость (вес) маршрута $\mathcal{R}$ определяется выражением

$w(\mathcal{R}) = w(y,{{x}_{{{{i}_{1}}}}}) + w({{x}_{{{{i}_{1}}}}},{{x}_{{{{i}_{2}}}}}) + \cdots + w({{x}_{{{{i}_{{t - 1}}}}}},{{x}_{{{{i}_{t}}}}}) + w({{x}_{{{{i}_{t}}}}},y).$
Маршрут $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$ называется допустимым, если

${{S}_{\mathcal{R}}}(x)\left\{ \begin{gathered} \leqslant D(x),\quad x \in \{ {{x}_{{{{i}_{1}}}}}, \ldots ,{{x}_{{{{i}_{t}}}}}\} , \hfill \\ = 0,\quad {\text{в}}\;{\text{противном}}\;{\text{случае}}, \hfill \\ \end{gathered} \right.\quad {\text{и}}\quad \sum\limits_{x \in X} \,{{S}_{\mathcal{R}}}(x) \leqslant q.$

Задача CVRP-SD заключается в построении семейства $\mathfrak{S}$ допустимых маршрутов минимальной суммарной стоимости, удовлетворяющего совокупный потребительский спрос:

(1)
$\begin{gathered} w(\mathfrak{S}) \equiv \sum\limits_{\mathcal{R} \in \mathfrak{S}} \,w(\mathcal{R}) \to min, \\ \sum\limits_{\mathcal{R} \in \mathfrak{S}} \,{{S}_{\mathcal{R}}}(x) = D(x),\quad x \in X. \\ \end{gathered} $
Постановка классической задачи CVRP легко может быть получена из постановки (1) задачи CVRP-SD введением дополнительного ограничения $D(x) \equiv 1$.

Если функция $w$ удовлетворяет неравенству треугольника, т.е. для произвольного подмножества $\{ {{v}_{1}},{{v}_{2}},{{v}_{3}}\} \subset X \cup \{ y\} $ справедливо соотношение $w({{v}_{1}},{{v}_{2}}) \leqslant w({{v}_{1}},{{v}_{3}}) + w({{v}_{3}},{{v}_{2}})$, то вершины графа $G$ принято называть точками, величину $w(u,v)$ – расстоянием между точками $u$ и $v$, стоимость $w(\mathcal{R})$ произвольного маршрута $\mathcal{R}$ – его длиной, а соответствующую постановку задачи – метрической.

В данной работе мы ограничимся рассмотрением исключительно метрических постановок задачи CVRP. Более того, задавшись произвольным натуральным числом $d > 1$, мы потребуем, чтобы каждая рассматриваемая постановка обладала следующими свойствами:

1) пара $(Z,\rho )$, в которой $Z = X \cup \{ y\} $, а ${{\left. \rho \right|}_{E}} \equiv w$, является конечным метрическим пространством размерности удвоения $d$;

2) число маршрутов хотя бы одного из оптимальных решений задачи ограничено сверху величиной ${\text{polylog}}(n)$, являющейся полиномом от логарифма размера входных данных.

Всюду ниже мы договоримся не различать весовую функцию $w$ и порождаемую ей метрику $\rho $ и использовать обозначения ${\text{CVRP(}}Z,w,q)$ и ${\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q)$ для постановки задачи CVRP, задаваемой графом $G = (X \cup \{ y\} ,E,w)$ и грузоподъемностью $q$, и ее оптимального значения соответственно. Для задачи CVRP-SD вводим обозначения ${\text{CVRP - SD(}}Z,D,w,q)$ и ${\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} (Z,D,w,q)$ по аналогии.

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

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

2. МЕТРИЧЕСКИЕ ПРОСТРАНСТВА ФИКСИРОВАННОЙ РАЗМЕРНОСТИ УДВОЕНИЯ

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

Определение 2. Метрическим шаром с центром ${{z}_{0}} \in Z$ радиуса $R$ называется множество $B({{z}_{0}},R) = \{ z \in Z\,:\;\rho ({{z}_{0}},z) \leqslant R\} $.

Определение 3 (см., например, [36]). Говорят, что метрическое пространство $(Z,\rho )$ обладает размерностью удвоения $d$, если для произвольных ${{z}_{0}} \in Z$ и $R > 0$ найдется число $M \leqslant {{2}^{d}}$ и точки ${{z}_{1}}, \ldots ,{{z}_{M}} \in Z$ такие, что $B({{z}_{0}},R) \subseteq \bigcup\nolimits_{j = 1}^M \,B({{z}_{j}},R{\text{/}}2).$

Нетрудно убедиться, что произвольное пространство $l_{p}^{d}$ обладает размерностью удвоения $O(d)$. Однако известно, что класс метрических пространств конечной размерности существенно шире семейства конечномерных числовых пространств (см., например, [37]).

Пусть $Z{\kern 1pt} ' \subset Z$ произвольное подпространство пространства $Z$ размерности удвоения $d$. Через $\Delta = {{\Delta }_{\rho }}(Z{\kern 1pt} ') = \sup \{ \rho (u,v)\,:\;u,v \in Z{\kern 1pt} '\} $ и $\alpha = {{\alpha }_{\rho }}(Z{\kern 1pt} ') = \inf \{ \rho (u,v)\,:\;\{ u,v\} \subset Z{\kern 1pt} '\} $ обозначим верхнюю и нижнюю грань попарных расстояний между элементами $Z{\kern 1pt} '$.

Лемма 1 (см. [34]). Пусть $0 < \alpha \leqslant \Delta < \infty $. Подпространство $Z{\kern 1pt} '$ конечно,

${\text{|}}Z{\kern 1pt} '{\text{|}} \leqslant \mathop {\left( {\frac{{2\Delta }}{\alpha }} \right)}\nolimits^d .$
В данной статье мы ограничиваемся исключительно рассмотрением конечных метрических пространств $(Z,\rho )$, порождаемых полными взвешенными графами $G = (Z,E,w)$. Пусть $U \subseteq Z$ – произвольное непустое подмножество вершин графа $G$, ${\text{MST(}}U)$ – остовное дерево минимального веса подграфа $G\left\langle U \right\rangle $, индуцированного подмножеством $U$, и $R = R(U)$ – радиус минимального объемлющего $U$ метрического шара $B(z,R)$ с центром в подходящей точке $z \in Z$.

Нам потребуется следующая техническая лемма (см., например, [34]), которую для полноты изложения мы приводим с доказательством.

Лемма 1. Пусть $(Z,\rho )$ – конечное метрическое пространство размерности удвоения $d > 1$. Для произвольного непустого подмножества $U \subseteq Z$ радиуса $R$

(2)
$w({\text{MST(}}U)) \leqslant 12R{\kern 1pt} {\text{|}}U{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}}.$

Доказательство. Для произвольного $\emptyset \ne V \subseteq U$ обоснуем соотношение

$w({\text{MST(}}V)) \leqslant 12R(V)({\kern 1pt} {\text{|}}V{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 1).$(3)

Доказательство ведем индукцией по ${\text{|}}V{\text{|}}$.

База: ${\text{|}}V{\kern 1pt} {\text{|}} \leqslant 2$. При ${\text{|}}V{\kern 1pt} {\text{|}} = 1$ неравенство (3), очевидно, справедливо, так как

$R(V) = w({\text{MST(}}V)) = 0.$
Рассмотрим случай $V = \{ u,v\} $. Поскольку ${{2}^{{1 - 1/d}}} - 1 \geqslant \sqrt 2 - 1 > 0.4$ при произвольном $d \geqslant 2$,

$w({\text{MST(}}V)) = \rho (u,v) \leqslant 2R(V) < 4.8R(V) < 12R(V)({\kern 1pt} {\text{|}}V{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 1).$

Шаг индукции: Пусть ${\text{|}}V{\kern 1pt} {\text{|}} \geqslant 3$. По предположению индукции соотношение (3) верно для произвольного непустого подмножества $V{\kern 1pt} ' \subset U$, ${\text{|}}V{\kern 1pt} '{\text{|}} < {\text{|}}V{\kern 1pt} {\text{|}}$. Обоснуем справедливость неравенства (3) для подмножества $V$.

Пусть $B$ – минимальный метрический шар (радиуса $R(V)$), содержащий подмножество $V$. По условию для некоторого $l \leqslant {{2}^{d}}$ найдутся шары ${{B}_{1}}, \ldots ,{{B}_{l}} \subset Z$ радиуса $R(V){\text{/}}2$ такие, что $\bigcup\nolimits_{j = 1}^l \,{{B}_{j}} \supseteq B$. Введя обозначение ${{V}_{j}} = {{B}_{j}} \cap V$, без ограничения общности полагаем ${{V}_{i}} \ne \emptyset $ и ${{V}_{j}} \cap {{V}_{k}} = \emptyset $ для произвольных $i$ и $j \ne k$.

Кроме того, мы всегда можем полагать $l \geqslant 3$. В самом деле, $l > 1$ в силу минимальности шара $B$. Поскольку ${\text{|}}V{\kern 1pt} {\text{|}} \geqslant 3$, при $l = 2$ хотя бы одно из подмножеств ${{V}_{1}}$ или ${{V}_{2}}$, например, ${{V}_{1}}$ не является синглетоном и может быть дополнительно разбито на два непустых подмножества.

Таким образом, построено разбиение множества $V$ не менее чем на три непустых дизъюнктных подмножества ${{V}_{1}}, \ldots ,{{V}_{l}}$. По построению для каждого элемента разбиения ${{V}_{j}}$ справедливо неравенство $R({{V}_{j}}) \leqslant R(V){\text{/}}2$. Следовательно,

$w({\text{MST(}}{{V}_{j}})) \leqslant 12R({{V}_{j}})({\kern 1pt} {\text{|}}{{V}_{j}}{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 1) \leqslant 6R(V)({\kern 1pt} {\text{|}}{{V}_{j}}{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 1)$
по предположению индукции.

Зафиксируем произвольную систему представителей $H = \{ {{v}_{j}} \in {{V}_{j}}:j \in \{ 1,2, \ldots ,l\} \} $ и рассмотрим дерево

$T = {\text{MST(}}H) \cup \bigcup\limits_{j = 1}^l \,{\text{MST(}}{{V}_{j}}).$
По построению $w({\text{MST(}}H)) \leqslant 2R(V)(l - 1)$, поскольку $\Delta (V) \leqslant 2R(V)$. Объединяя оценки, имеем
$\begin{gathered} w(T) = \sum\limits_{j = 1}^l \,w({\text{MST(}}{{V}_{j}})) + w({\text{MST(}}H)) < 6R(V)\sum\limits_{j = 1}^l \,({\kern 1pt} {\text{|}}{{V}_{j}}{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 1) + 2lR(V) \leqslant 6R(V)\sum\limits_{j = 1}^l \,{\text{|}}{{V}_{j}}{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - \\ \, - 4lR(V) \leqslant 6R(V)\sum\limits_{j = 1}^l \,\mathop {\left( {\frac{{{\text{|}}V{\kern 1pt} {\text{|}}}}{l}} \right)}\nolimits^{1 - 1/d} - 4lR(V) = 6R(V){{l}^{{1/d}}}{\kern 1pt} {\text{|}}V{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 4lR(V) \leqslant 12R(V){\kern 1pt} {\text{|}}V{\kern 1pt} {{{\text{|}}}^{{1 - 1/d}}} - 12R(V). \\ \end{gathered} $
Последнее неравенство следует из условий $l \leqslant {{2}^{d}}$ и $l \geqslant 3$. Индуктивный переход обоснован. Для завершения доказательства леммы достаточно рассмотреть случай $V = U$.

3. АППРОКСИМАЦИОННАЯ СХЕМА ДЛЯ CVRP

Приведенные в данном разделе рассуждения развивают известный подход С. Ароры (см. [23]) к построению PTAS для евклидовой задачи коммивояжера и его обобщение (см. [35], [34]) на случай метрических пространств фиксированной размерности удвоения. Структура предлагаемой аппроксимационной схемы состоит из нескольких стадий и представима в виде приведенной ниже последовательности.

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

2. Стадия рандомизированной иерархической кластеризации, в рамках которой для заданных случайных значений параметров строится совокупность вложенных друг в друга разбиений множества $X \cup \{ y\} $. В кластере произвольного уровня выбирается подмножество специальных точек-порталов. Далее, следуя подходу [35], мы показываем, что для поиска искомого приближенного решения округленной задачи достаточно ограничиться семействами так называемых сетевых маршрутов, пересекающих границу произвольного кластера ограниченное число раз, причем исключительно в порталах.

3. Стадия поиска семейства сетевых маршрутов минимального веса. Методом динамического программирования построенной случайной реализации иерархической кластеризации сопоставляется допустимое решение, состоящее из сетевых маршрутов минимальной суммарной стоимости.

4. Стадия дерандомизации. Показывается, что по аналогии со схемой К. Талвара (см. [34]), предложенный рандомизированный алгоритм может быть эффективно дерандомизирован.

3.1. Предварительная обработка и округление

Первая стадия алгоритма развивает подход к преобразованию исходной задачи, впервые реализованный С. Аророй при построении PTAS для евклидовой задачи коммивояжера (см. [23]), и состоит из двух этапов.

Пусть как и ранее $\Delta = {{\Delta }_{w}}(Z) = \max \{ w(u,v)\,:\;u,v \in Z = X \cup \{ y\} \} $ – диаметр множества $Z$. Без ограничения общности полагаем выполненным соотношение $\Delta = n{\text{/}}\varepsilon $, поскольку в противном случае исходной задаче ${\text{CVRP(}}Z,E,w)$ всегда может быть сопоставлена эквивалентная (с точки зрения совпадения оптимальных множеств) постановка ${\text{CVRP(}}Z,E,w{\kern 1pt} ')$ с весовой функцией

$w{\kern 1pt} '(u,v) = w(u,v)\frac{n}{{\varepsilon \cdot \Delta }},$
обладающая этим свойством.

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

Определение 4. Пусть $Z{\kern 1pt} '$ – произвольное непустое подпространство метрического пространства $(Z,\rho )$. Для заданного $\delta > 0$ подмножество $N \subseteq Z{\kern 1pt} '$ называется $\delta $-сетью подпространства $Z{\kern 1pt} '$, если

1) для произвольного $u \in Z{\kern 1pt} '$ найдется такой элемент $v = v(u) \in N$, что $\rho (u,v) \leqslant \delta $;

2) для произвольного подмножества $\{ {{v}_{1}},{{v}_{2}}\} \subset N$ расстояние $\rho ({{v}_{1}},{{v}_{2}}) > \delta $.

Пусть $N_{1}^{'} = \{ {{\xi }_{1}}, \ldots ,{{\xi }_{J}}\} $ – 1-сеть множества $X$. Положив ${{N}_{1}} = N_{1}^{'} \cup \{ y\} $, сопоставим исходной задаче ${\text{CVRP(}}Z,w,q)$ округленную постановку ${\text{CVRP - SD(}}{{N}_{1}},D,{{w}_{1}},q)$ по следующему правилу:

1) произвольным образом разрешая возможную неоднозначность, построим отображение $\xi {\kern 1pt} :\;X \to N_{1}^{'}$ так, чтобы неравенство $w(x,\xi (x)) \leqslant 1$ выполнялось для произвольного $x \in X$;

2) спрос произвольного узла сети ${{\xi }_{j}} \in N_{1}^{'}$ определим соотношением $D({{\xi }_{j}}) = {\text{|}}{{\xi }^{{ - 1}}}({{\xi }_{j}}){\kern 1pt} {\text{|}}$;

3) в качестве весовой функции ${{w}_{1}}$ выберем сужение функции $w$ на сеть ${{N}_{1}}$.

Справедливы следующие соотношения, связывающие оптимальные значения рассматриваемых задач.

Лемма 2.

${\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) - 2n \leqslant {\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} ({{N}_{1}},D,{{w}_{1}},q) \leqslant {\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) + 2n.$

Доказательство. 1. Для обоснования верхней оценки рассмотрим произвольное оптимальное решение $\mathfrak{S} = \{ \mathcal{R}\} $ задачи ${\text{CVRP(}}Z,w,q)$. Каждому маршруту $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}}) \in \mathfrak{S}$, $\pi = y,{{x}_{{{{i}_{1}}}}}, \ldots ,{{x}_{{{{i}_{t}}}}},y$, сопоставим маршрут $\bar {\mathcal{R}} = (\bar {\pi },{{S}_{{\bar {\mathcal{R}}}}})$, в котором $\bar {\pi } = y,\xi ({{x}_{{{{i}_{1}}}}}), \ldots ,\xi ({{x}_{{{{i}_{t}}}}}),y$, а распределение ${{S}_{{\bar {\mathcal{R}}}}}\,:\;N_{1}^{'} \to {{\mathbb{Z}}_{ + }}$ определяется соотношением

${{S}_{{\bar {\mathcal{R}}}}}({{\xi }_{j}}) = \sum\limits_{\xi (x) = {{\xi }_{j}}} \,{{S}_{\mathcal{R}}}(x).$

Полученное в результате семейство маршрутов $\bar {\mathfrak{S}} = \{ \bar {\mathcal{R}}\} $, очевидно, является допустимым решением округленной задачи ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$. Оценим его вес ${{w}_{1}}(\bar {\mathfrak{S}}) = \sum\nolimits_{\bar {\mathcal{R}} \in \bar {\mathfrak{S}}} \,{{w}_{1}}(\bar {\mathcal{R}})$. По выбору отображений ${{w}_{1}}$, $\xi $ и неравенству треугольника

$\begin{gathered} {{w}_{1}}(\bar {\mathcal{R}}) = {{w}_{1}}(y,\xi ({{x}_{{{{i}_{1}}}}})) + \sum\limits_{j = 1}^t \,{{w}_{1}}(\xi ({{x}_{{{{i}_{j}}}}}),\xi ({{x}_{{{{i}_{{j + 1}}}}}})) + {{w}_{1}}(\xi ({{x}_{{{{i}_{t}}}}}),y) \leqslant \\ \, \leqslant w(y,{{x}_{{{{i}_{1}}}}}) + \sum\limits_{j = 1}^t \,w({{x}_{{{{i}_{j}}}}},{{x}_{{{{i}_{{j + 1}}}}}}) + w({{x}_{{{{i}_{t}}}}},y) + 2\sum\limits_{j = 1}^t \,w({{x}_{{{{i}_{j}}}}},\xi ({{x}_{{{{i}_{j}}}}})) \leqslant w(\mathcal{R}) + 2t. \\ \end{gathered} $
Следовательно,
$\begin{gathered} {\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} ({{N}_{1}},D,{{w}_{1}},q) \leqslant {{w}_{1}}(\bar {\mathfrak{S}}) = \sum {{{w}_{1}}(\bar {\mathcal{R}})} \leqslant \sum {w(\mathcal{R}) + 2n} = \\ \, = w(\mathfrak{S}) + 2n = {\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) + 2n, \\ \end{gathered} $
поскольку произвольный потребитель $x \in X$ посещается в точности одним из маршрутов $\mathcal{R}$ оптимального решения $\mathfrak{S}$.

2. Обоснование нижней оценки проведем по аналогии. Зафиксируем произвольное оптимальное решение $\bar {\mathfrak{S}} = \{ {{\bar {\mathcal{R}}}_{1}}, \ldots ,{{\bar {\mathcal{R}}}_{K}}\} $ задачи ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$. По определению объем спроса, удовлетворяемый маршрутом $\bar {\mathcal{R}} = (\bar {\pi },{{S}_{\mathcal{R}}}) \in \bar {\mathfrak{S}}$ в произвольном узле $\xi $ сети $N_{1}^{'}$, определяется соотношением ${{S}_{{\bar {\mathcal{R}}}}}(\xi )$ так, что

$\sum\limits_{\xi \in N_{1}^{'}} \,{{S}_{{\bar {\mathcal{R}}}}}(\xi ) \leqslant q.$
Произвольному $j \in \{ 1,2, \ldots ,J\} $ сопоставим отображение ${{\eta }_{j}}\,:\;{{X}_{j}} \to \bar {\mathfrak{S}}$ так, что
$\left| {\eta _{j}^{{ - 1}}(\bar {\mathcal{R}})} \right| = {{S}_{{\bar {\mathcal{R}}}}}({{\xi }_{j}}),\quad 1 \leqslant j \leqslant J,\quad \bar {\mathcal{R}} \in \bar {\mathfrak{S}}.$
Далее, произвольному маршруту $\bar {\mathcal{R}} = (\bar {\pi },{{S}_{{\bar {\mathcal{R}}}}}) \in \bar {\mathfrak{S}}$, $\bar {\pi } = y,{{\xi }_{{{{j}_{1}}}}}, \ldots ,{{\xi }_{{{{j}_{t}}}}},y$, сопоставим маршрут $\mathcal{R} = \mathcal{R}(\bar {\mathcal{R}})$, начинающийся (и заканчивающийся) на складе $y$ и последовательно обходящий вершины подмножеств $\eta _{{{{j}_{1}}}}^{{ - 1}}(\bar {\mathcal{R}}), \ldots ,\eta _{{{{j}_{t}}}}^{{ - 1}}(\bar {\mathcal{R}})$. Полученное в результате семейство маршрутов $\mathfrak{S} = \{ {{\mathcal{R}}_{1}}, \ldots ,{{\mathcal{R}}_{K}}\} $, очевидно, является допустимым решением задачи ${\text{CVRP(}}Z,w,b)$. Оценим его стоимость. По построению сети $N_{1}^{'}$ и в силу неравенства треугольника
$w({{\mathcal{R}}_{k}}) \leqslant {{w}_{1}}({{\bar {\mathcal{R}}}_{k}}) + 2\sum\limits_{i = 1}^t \,{{S}_{{\mathop {\bar {\mathcal{R}}}\nolimits_k }}}({{\xi }_{{{{j}_{i}}}}}),$
следовательно,
(4)
$w(\mathfrak{S}) = \sum\limits_{k = 1}^K \,w(\mathcal{R}) \leqslant \sum\limits_{k = 1}^K \,{{w}_{1}}({{\bar {\mathcal{R}}}_{k}}) + \sum\limits_{k = 1}^K \,\sum\limits_{j = 1}^J \,{{S}_{{\mathop {\bar {\mathcal{R}}}\nolimits_k }}}({{\xi }_{j}}) = {{w}_{1}}(\bar {\mathfrak{S}}) + 2n,$
откуда
${\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) \leqslant w(\mathfrak{S}) \leqslant {\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} ({{N}_{1}},D,{{w}_{1}},q) + 2n.$
Лемма доказана.

Заметим, что процедуры построения сети $N_{1}^{'}$, сопоставления исходной задаче ${\text{CVRP(}}Z,w,q)$ округленной постановки ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$, а также восстановления решения $\mathfrak{S}$, соответствующего решению $\bar {\mathfrak{S}}$, очевидно, могут быть проведены за время, ограниченное сверху полиномом от $n$.

В качестве простого следствия убедимся в том, что произвольное приближенное решение задачи ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$ соответствует подходящему приближенному решению исходной задачи ${\text{CVRP(}}Z,w,q)$. В самом деле, пусть $\bar {\mathfrak{S}}$ – произвольное $(1 + \varepsilon )$-приближенное решение задачи ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$. Применяя подход, описанный в доказательстве п. 2 леммы 3, сопоставим решению $\bar {\mathfrak{S}}$ семейство маршрутов $\mathfrak{S}$.

Следствие 1. Семейство $\mathfrak{S}$ является $(1 + O(\varepsilon ))$-приближенным решением ${\text{CVRP(}}Z,w,q)$.

Доказательство. По построению $\mathfrak{S}$ – допустимое решение задачи ${\text{CVRP(}}Z,w,q)$, стоимость $w(\mathfrak{S})$ которого определяется соотношением (4). Учитывая

${{w}_{1}}(\bar {\mathfrak{S}}) \leqslant (1 + \varepsilon ){\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} ({{N}_{1}},D,{{w}_{1}},q)\quad {\text{и}}\quad {{\Delta }_{w}}(Z) = n{\text{/}}\varepsilon ,$
имеем
$\begin{gathered} w(\mathfrak{S}) \leqslant (1 + \varepsilon ){\text{CVRP - SD}}{\kern 1pt} *{\kern 1pt} ({{N}_{1}},D,{{w}_{1}},q) + 2n \leqslant (1 + \varepsilon )({\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) + 2n) + 2n \leqslant \\ \, \leqslant (1 + \varepsilon ){\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) + 2{{\Delta }_{w}}(Z)\varepsilon (2 + \varepsilon ) = (1 + O(\varepsilon )){\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q), \\ \end{gathered} $
так как неравенство треугольника, очевидно, влечет $2{{\Delta }_{w}}(Z) \leqslant {\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q)$.

Результаты данного раздела свидетельствуют о том, что при поиске $(1 + O(\varepsilon ))$-приближенного решения метрической задачи CVRP без ограничения общности можно полагать, что диаметр ${{\Delta }_{w}}(Z) = n{\text{/}}\varepsilon $, расстояние между произвольными попарно различными потребителями $u$ и $v$ удовлетворяет соотношению $w(u,v) = \rho (u,v) > 1$, а объем спроса произвольного потребителя измеряется подходящим натуральным числом.

3.2. Рандомизированная иерархическая кластеризация

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

Следуя подходу, предложенному в [34], последовательно строим рандомизированную иерархическую кластеризацию множества $Z$ индукцией по $l = 0,1, \ldots ,L + 1$. На уровне $l = 0$ имеем единственный кластер $C_{1}^{0}$.

Пусть кластеризация реализована на всех уровнях, включая $l \leqslant L$, и, в частности, на уровне $l$ разбиение $Z$ имеет вид $Z = C_{1}^{l} \cup \ldots \cup C_{K}^{l}$. Кластеризацию на уровне $l + 1$ строим путем разбиения каждого кластера $C_{j}^{l}$ в отдельности. Задавшись на множестве $\{ {{h}_{1}}, \ldots ,{{h}_{{{{t}_{{l + 1}}}}}}\} $ элементов ${{s}^{{L - l - 1}}}$-сети $N(l + 1)$ случайным порядком $\sigma $, произвольному ${{h}_{{\sigma (i)}}} \in N(l + 1)$ сопоставляем подмножество

$C_{{ji}}^{{l + 1}} = B({{h}_{{\sigma (i)}}},\mu \cdot {{s}^{{L - l - 1}}}) \cap C_{j}^{l}{\kern 1pt} {{\backslash }}{\kern 1pt} \bigcup\limits_{k = 1}^{i - 1} \,C_{{jk}}^{{l + 1}},$
где $\mu $ – случайная величина, равномерно распределенная на $[1,2)$, после чего формируем искомую кластеризацию $Z$ на уровне $l + 1$ из непустых подмножеств $C_{{ji}}^{{l + 1}}$.

В силу нашего допущения кластеры уровня $L + 1$ – одноэлементные, а общее число кластеров на всех уровнях не превосходит $(n + 1)(L + 1) = O(nlogn)$ (при произвольном фиксированном $\varepsilon > 0$).

Как будет показано ниже, при поиске $(1 + \varepsilon )$-приближенного решения исследуемой задачи можно ограничиться решениями, состоящими из так называемых сетевых маршрутов, пересекающих границу произвольного кластера не слишком часто, причем исключительно в специально заданных точках, именуемых порталами. Нам понадобится несколько определений и вспомогательных утверждений, доказательства которых легко могут быть получены из результатов [35].

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

${{s}^{{L - l}}} \leqslant \varepsilon \cdot \rho (u,{v}) < {{s}^{{L - l + 1}}}$
влечет принадлежность обеих вершин $u$ и ${v}$ сети $N(l)$.

Определение 6. Пусть $M$ – степень $s$, удовлетворяющая соотношению

(5)
$\frac{M}{s} \leqslant \frac{{dL}}{\varepsilon } < M.$
Порталом кластера $C_{j}^{l}$ называется произвольная принадлежащая ему точка – представитель ${{s}^{{L - l}}}{\text{/}}M$-сети.

Пусть $C_{j}^{l}$ – произвольный кластер уровня $l > 0$. Будем говорить, что маршрут $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$ пересекает границу кластера $C_{j}^{l}$, если цикл $\pi $ содержит ребро $\{ u,{v}\} $ такое, что ${\text{|}}{\kern 1pt} \{ u,v\} \cap C_{j}^{l}{\kern 1pt} {\text{|}} = 1$.

Определение 7. Маршрут $\mathcal{R}$ называется $r$-легким, если для произвольного кластера $C_{j}^{l}$ уровня $l > 0$ число пересечений его границы маршрутом $\mathcal{R}$ не превосходит $r$.

Лемма 3. Пусть $\varepsilon \in (0,1{\text{/}}8)$. Произвольному маршруту $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$ может быть сопоставлен подходящий сетевой маршрут $\tilde {\mathcal{R}} = (\tilde {\pi },{{S}_{{\tilde {\mathcal{R}}}}})$, ${{S}_{{\tilde {\mathcal{R}}}}} = {{S}_{\mathcal{R}}}$, стоимость которого удовлетворяет соотношению

(6)
$w(\tilde {\mathcal{R}}) \leqslant (1 + 16\varepsilon )w(\mathcal{R}).$
Лемма 4 позволяет произвольному допустимому решению исходной задачи сопоставить близкое по стоимости решение, целиком состоящее из сетевых маршрутов. Из утверждения следующей леммы следует, что для произвольного $r \geqslant 2$ без ограничения общности можно полагать, что все маршруты полученного в результате решения являются $r$-легкими.

Лемма 4. Пусть $r \geqslant 2$ и $C{\kern 1pt} ' \subset C_{j}^{l}$, ${\text{|}}C{\kern 1pt} '{\text{|}} > \bar {r} > r$, – множество точек пересечения границы кластера $C_{j}^{l}$ некоторым маршрутом $\mathcal{R} = (\pi ,{{S}_{\mathcal{R}}})$. Найдется сетевой маршрут $\tilde {\mathcal{R}} = (\tilde {\pi },{{S}_{{\tilde {\mathcal{R}}}}})$, ${{S}_{{\tilde {\mathcal{R}}}}} = {{S}_{\mathcal{R}}}$, пересекающий границу кластера $C_{j}^{l}$ дважды, стоимость которого

(7)
$w(\tilde {\mathcal{R}}) \leqslant w(\mathcal{R}) + 4w({\text{MST(}}C{\kern 1pt} ')).$

Заметим, что утверждения лемм 4 и 5 справедливы, вообще говоря, для произвольной метрики. В пространствах размерности удвоения $d > 1$ оценка (7) может быть приведена в более конкретной форме. В самом деле, по построению кластер $C_{j}^{l}$ лежит в некотором метрическом шаре, радиус которого не превосходит $2{{s}^{{L - l}}}$. Оценивая сверху $w({\text{MST(}}C{\kern 1pt} '))$ по лемме 2, получаем

(8)
$w(\tilde {\mathcal{R}}) = w(\mathcal{R}) + O\left( {{{s}^{{L - l}}}{{{\bar {r}}}^{{(1 - 1/d)}}}} \right).$

Рассуждая по аналогии, оценим число порталов $m$ в произвольном кластере $C_{j}^{l}$. Действительно, по определению, порталами в кластере $C_{j}^{l}$ являются представители ${{s}^{{L - l}}}{\text{/}}M$-сети, следовательно, по лемме 1

$m < \mathop {\left( {2\frac{{4{{s}^{{L - l}}}}}{{{{s}^{{L - l}}}{\text{/}}M}}} \right)}\nolimits^d = {{(8M)}^{d}} = O\left( {\mathop {\left( {\frac{{d(logn - log\varepsilon )}}{\varepsilon }} \right)}\nolimits^d } \right)$
в пространстве произвольной размерности удвоения $d > 1$ при произвольном фиксированном $\varepsilon > 0$.

Пусть далее $\mathfrak{S}$ – произвольное допустимое решение задачи ${\text{CVRP - SD}}({{N}_{1}},D,{{w}_{1}},q)$, а $\bar {\mathfrak{S}}$ – соответствующее ему решение, состоящее из сетевых $r$-легких маршрутов, полученных из маршрутов $\mathfrak{S}$ последовательным применением лемм 4 и 5. Приведенная ниже структурная теорема позволяет оценить среднее (относительно случайной иерархической кластеризации) значение стоимости полученного решения.

Теорема 1 (структурная). Пусть $0 < \varepsilon < 1{\text{/}}8$, $d > 1$ и $r = m$.

$E(w(\bar {\mathfrak{S}})) = (1 + O(\varepsilon ))w(\mathfrak{S}).$

Доказательство. Без ограничения общности полагаем, что исходное решение $\mathfrak{S}$ состоит из сетевых маршрутов, так как в противном случае последовательное применение леммы 4 к каждому из несетевых маршрутов решения $\mathfrak{S}$ позволяет сопоставить ему допустимое решение $\tilde {\mathfrak{S}}$ стоимости $w(\tilde {\mathfrak{S}}) = (1 + O(\varepsilon ))w(\mathfrak{S})$, обладающее этим свойством. Предположим, что не все маршруты решения $\mathfrak{S}$ являются $r$-легкими. Пусть $\bar {r} > r$ – число пересечений одного из таких маршрутов $\mathcal{R} \in \mathfrak{S}$ границы произвольного кластера $C_{j}^{l}$ на уровне $l > 0$. По лемме 5 (в силу соотношения (8)) маршруту $\mathcal{R}$ можно сопоставить сетевой маршрут $\bar {\mathcal{R}}$, стоимость которого превышает стоимость исходного маршрута на $O\left( {{{s}^{{L - l}}}{{{\bar {r}}}^{{(1 - 1/d)}}}} \right)$. Таким образом, прирост стоимости, приходящийся на одно из $\bar {r} > r = m$ ребер, пересекающих границу $C_{j}^{l}$, составит

$O\left( {\frac{{{{s}^{{L - l}}}{{{\bar {r}}}^{{(1 - 1/d)}}}}}{{\bar {r}}}} \right) = O\left( {\frac{{{{s}^{{L - l}}}}}{{{{r}^{{1/d}}}}}} \right) = O\left( {\frac{{{{s}^{{L - l}}}}}{M}} \right) = O\left( {\frac{{{{s}^{{L - l}}}\varepsilon }}{{dL}}} \right),$
где последнее равенство следует непосредственно из соотношения (5).

В свою очередь, из результатов (см. [34]) следует, что вероятность пересечения произвольным ребром $\{ u,v\} $ границы кластера на уровне $l$ не превосходит $O(d{\text{/}}{{s}^{{L - l}}})\rho (u,v)$. Следовательно, математическое ожидание прироста стоимости сетевого маршрута на уровне $l$, порождаемого его произвольным ребром $\{ u,v\} $, составит $O\left( \varepsilon \right)\rho (u,v){\text{/}}L$. Суммируя по $l = 1,2, \ldots ,L + 1$ и пользуясь линейностью математического ожидания, завершаем доказательство теоремы.

Как и в [23], [35], [24] доказанная выше структурная теорема играет ключевую роль в обосновании аппроксимационных свойств предлагаемого алгоритма. В самом деле, применяя утверждение теоремы 1 к произвольному оптимальному решению $\mathfrak{S}$ исследуемой задачи, получаем соотношение

${\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q) \leqslant E(w(\bar {\mathfrak{S}})) \leqslant (1 + O(\varepsilon )){\text{CVRP}}{\kern 1pt} *{\kern 1pt} (Z,w,q).$

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

3.3. Динамическое программирование

Зададимся случайной иерархической кластеризацией. Методом динамического программирования построим допустимое решение задачи, состоящее из сетевых $r$-легких маршрутов, обладающих минимальной суммарной стоимостью. Для описания структуры таблицы динамического программирования нам потребуется несколько вспомогательных понятий и определений.

Пусть маршрут $\mathcal{R}$ пересекает границу кластера $C$ уровня $l > 0$ в (необязательно различных) порталах ${{p}^{{{\text{in}}}}}$ и ${{p}^{{{\text{out}}}}}$ так, что его связный фрагмент

(9)
${{p}^{{{\text{in}}}}},\;{{x}_{{{{i}_{1}}}}},\; \ldots ,\;{{x}_{{{{i}_{t}}}}},\;{{p}^{{{\text{out}}}}}$
полностью содержится в данном кластере. Произвольный максимальный по включению фрагмент (9) договоримся называть сегментом маршрута $\mathcal{R}$, пересекающим кластер $C$ (или просто пересекающим сегментом). С точки зрения кластеризации более высокого уровня $l - 1$, произвольный сегмент, пересекающий кластер $C$, однозначно определяется кортежем
$({{p}^{{{\text{in}}}}},{{p}^{{{\text{out}}}}},Sup,Dep),$
где ${{p}^{{{\text{in}}}}}$ и ${{p}^{{{\text{out}}}}}$ – упомянутые выше порталы “входа” и “выхода”, $0 \leqslant Sup \leqslant q$ – объем спроса, удовлетворяемый данным сегментом внутри кластера $C$, а $Dep \in \{ 0,1\} $ – индикатор, указывающий посещение им склада.

Конфигурацией, ассоциируемой с заданным кластером $C$ произвольного уровня $l \geqslant 0$, назовем конечную последовательность

(10)
$\mathfrak{C} = ((p_{i}^{{{\text{in}}}},p_{i}^{{{\text{out}}}},Su{{p}_{i}},De{{p}_{i}}),\;i = 1,2, \ldots ,{{T}_{\mathfrak{C}}}),$
каждый элемент которой определяет сегмент какого-либо сетевого $r$-легкого маршрута, пересекающий кластер $C$. Длина ${{T}_{\mathfrak{C}}}$ конфигурации $\mathfrak{C}$ – неотрицательное целое число, не превосходящее ${\text{|}}\mathfrak{S}{\kern 1pt} *{\kern 1pt} {\text{|}}r$, где ${\text{|}}\mathfrak{S}{\kern 1pt} *{\kern 1pt} {\text{|}}$ – размер (число маршрутов) произвольного оптимального решения $\mathfrak{S}{\kern 1pt} *$ задачи. Верхняя граница следует из определения $r$-легкого маршрута, который не может пересекать границу произвольного кластера более $r$ раз. В случае ${{T}_{\mathfrak{C}}} = 0$ конфигурация $\mathfrak{C}$, называется пустой и описывает ситуацию, при которой ни один из маршрутов не пересекает границ ассоциированного кластера (cоответствующую, например, кластеру наивысшего уровня l = 0).

Конфигурация $\mathfrak{C}$ называется допустимой для кластера $C$, если найдется подходящее семейство $\tilde {\mathfrak{S}} = \tilde {\mathfrak{S}}(C,\mathfrak{C})$ допустимых сетевых $r$-легких маршрутов (возможно, включающее маршруты, целиком содержащиеся в кластере $C$), удовлетворяющих совокупный спрос потребителей из $C$, такое, что сегменты маршрутов, пересекающие кластер $C$, взаимно однозначно соответствуют элементам конфигурации $\mathfrak{C}$.

Внутренней стоимостью семейства маршрутов $\tilde {\mathfrak{S}}$ (относительно кластера $C$) назовем суммарный вес сегментов входящих в него маршрутов, пересекающих кластер $C$, дополненный весом маршрутов, внутренних относительно данного кластера.

Ячейка таблицы динамического программирования индексируется упорядоченной парой $(C,\mathfrak{C})$, в которой $C$ – кластер произвольного уровня $l$, а $\mathfrak{C}$ – произвольная допустимая конфигурация. Значение ячейки $(C,\mathfrak{C})$ – минимальная внутренняя стоимость подходящего семейства маршрутов.

Заполнение таблицы динамического программирования производится рекурсивно в порядке убывания $l$. Ячейки базового $(L + 1)$-уровня, соответствующие одноэлементным кластерам, заполняются очевидным образом. Предполагая заполненными все ячейки, соответствующие кластерам, расположенным на уровнях $l + 1, \ldots ,L + 1$, опишем вычисление произвольной ячейки $(C_{j}^{l},\mathfrak{C})$, порождаемой кластером $C_{j}^{l}$ уровня $l$.

В самом деле, пусть $C_{j}^{l} = C_{{j1}}^{{l + 1}} \cup \ldots \cup C_{{jk}}^{{l + 1}}$ разбиение кластера $C_{j}^{l}$, построенное на этапе иерархической кластеризации. Через

(11)
$Ch = (C_{{j1}}^{{l + 1}},{{\mathfrak{C}}_{1}}),\; \ldots ,\;(C_{{jk}}^{{l + 1}},{{\mathfrak{C}}_{k}})$
обозначим произвольный набор порождаемых ими ячеек таблицы.

Для описания совместимости набора ячеек $Ch$ с вычисляемой ячейкой $(C_{j}^{l},\mathfrak{C})$ и последующей склейки сегментов нам потребуется несколько дополнительных понятий.

Профилем конкатенации, описывающим порядок склейки (сегмента) маршрута, назовем конечную последовательность $\varphi = ((p_{t}^{1},p_{t}^{2},su{{p}_{t}},de{{p}_{t}})\,:\;t = 1,2, \ldots ,{{\theta }_{\varphi }}),$ в которой $p_{t}^{1},p_{t}^{2} \in C_{j}^{l} \cap N(l + 1)$, а остальные компоненты кортежей имеют тот же смысл, что и в определении конфигурации.

Получающийся в результате склейки сегмент $r$-легкого маршрута может пересекать границы кластеров $C_{{j1}}^{{l + 1}}, \ldots ,C_{{jk}}^{{l + 1}}$, поэтому ${{\theta }_{\varphi }} \leqslant kr$ для произвольного профиля $\varphi $.

Интерфейсом назовем произвольную конечную совокупность (не обязательно попарно различных) профилей конкатенации $\Im = ({{\varphi }_{1}}, \ldots ,{{\varphi }_{\nu }}).$

Будем говорить, что интерфейс $\Im $ согласован с вычисляемой ячейкой $(C_{j}^{l},\mathfrak{C})$ и набором $Ch$, если выполнены следующие условия:

1) каждый кортеж произвольной конфигурации ${{\mathfrak{C}}_{i}}$ встречается в профилях интерфейса $\Im $ в точности один раз;

2) для произвольного профиля конкатенации $\varphi $, входящего в интерфейс $\Im $,

$\sum\limits_{t = 1}^{{{\theta }_{\varphi }}} \,su{{p}_{t}} \leqslant q;$

3) суммарное значение удовлетворяемого спроса $su{{p}_{j}}$ всеми профилями конкатенации, входящими в интерфейс $\Im $, совпадает с совокупным объемом спроса потребителей кластера $C_{j}^{l}$:

$\sum\limits_{\tau = 1}^\nu \,\sum\limits_{t = 1}^{{{\theta }_{{{{\phi }_{\tau }}}}}} \,su{{p}_{t}} = \sum\limits_{x \in C_{j}^{l}} \,D(x);$

4) произвольному кортежу $(p_{i}^{{{\text{in}}}},p_{i}^{{{\text{out}}}},Su{{p}_{i}},De{{p}_{i}})$ конфигурации $\mathfrak{C}$ однозначно соответствует содержащийся в интерфейсе $\Im $ профиль конкатенации $\varphi = \varphi (i)$ такой, что

$p_{1}^{1} = p_{i}^{{{\text{in}}}},\quad p_{{{{\theta }_{\varphi }}}}^{2} = p_{i}^{{{\text{out}}}},\quad \sum\limits_{t = 1}^{{{\theta }_{\varphi }}} \,su{{p}_{t}} = Su{{p}_{i}},\quad \mathop \vee \limits_{t = 1}^{{{\theta }_{\varphi }}} \,de{{p}_{t}} = De{{p}_{i}};$

5) если профиль конкатенации $\varphi $ не соответствует никакому кортежу конфигурации $\mathfrak{C}$, то $ \vee _{{t = 1}}^{{{{\theta }_{\varphi }}}}\,de{{p}_{t}} = 1$.

По определению для совместимости набора ячеек $Ch$ c ячейкой $(C_{j}^{l},\mathfrak{C})$ необходимо и достаточно существование хотя бы одного согласованного интерфейса $\Im $.

Пусть далее $w(\Im )$ – суммарная стоимость (сегментов) маршрутов, получаемых в процессе склейки в соответствии с профилями конкатенации, входящими в согласованный интерфейс $\Im $. Сопоставив произвольному набору ячеек $Ch$ стоимость

$w(Ch) = min\left\{ {w(\Im )\,:\;\Im \;{\text{согласован}}\;{\text{с}}\;{\text{набором}}\;Ch\;{\text{и}}\;{\text{ячейкой}}\;(C_{j}^{l},\mathfrak{C})} \right\},$
значение, сохраняемое в ячейке $(C_{j}^{l},\mathfrak{C})$, определим по формуле
$w(C_{j}^{l},\mathfrak{C}) = min\{ w(Ch)\,:\;{\text{набор}}\;Ch\;{\text{совместим}}\;{\text{с}}\;{\text{ячейкой}}\;(C_{j}^{l},\mathfrak{C})\} .$
В случае, если ни один из наборов (11) не совместим с ячейкой $(C_{j}^{l},\mathfrak{C})$, она исключается из рассмотрения, а конфигурация $\mathfrak{C}$ называется недопустимой для кластера $C_{j}^{l}$.

Минимизация по всем допустимым конфигурациям кластера $C_{1}^{0}$, расположенного на верхнем уровне рекурсии,

$\min \{ w(C_{1}^{0},\mathfrak{C})\,:\;\mathfrak{C} - {\text{допустима}}\} $
и последующее восстановление маршрутов методом обратной прогонки завершают поиск искомого сетевого $r$-легкого решения исходной задачи, соответствующего заданной случайной реализации иерархической кластеризации.

3.4. Дерандомизация

Следуя схеме доказательства, проведенного в [34], нетрудно убедиться, что для построения рандомизированной иерархической кластеризации (п. 3.2) достаточно $O(log(n + d)loglogn) + {{2}^{{O(d)}}}$ случайных бит. Таким образом, наивная дерандомизация описанного в п. 3.3 алгоритма, основанная на полном переборе всех элементарных исходов, обладает полиномиальной трудоемкостью, как и в случае с классической схемой С. Ароры (см. [23]).

4. ВЕРХНЯЯ ОЦЕНКА ТРУДОЕМКОСТИ

Очевидно, что операция сопоставления исходной задаче округленной постановки (описанная в п. 3.1), может быть проведена за время $O(n)$. Случайная реализация иерархической кластеризации исходной постановки также обладает не более чем полиномиальной трудоемкостью. Оценим трудоемкость алгоритма динамического программирования.

В процессе построения иерархической кластеризации может быть построено до $O(nlogn)$ кластеров, с каждом из которых может быть ассоциировано до ${{(2{{m}^{2}}q)}^{{|\mathfrak{S}{\kern 1pt} *| \cdot r}}}$ конфигураций, где $\mathfrak{S}{\kern 1pt} *$ – произвольное оптимальное решение исследуемой задачи. В самом деле, по определению каждая конфигурация $\mathfrak{C}$ определяется соотношением (10), в котором произвольный кортеж $(p_{i}^{{in}},p_{i}^{{out}},Su{{p}_{i}},De{{p}_{i}})$ может быть выбран не более чем $2{{m}^{2}}q$ способами.

Учитывая естественное ограничение $q \leqslant n$, получаем верхнюю оценку размера таблицы динамического программирования:

$O(nlogn)\mathop {(2{{m}^{2}}n)}\nolimits^{|\mathfrak{S}*|r} .$
По построению вычисление каждой ячейки $(C_{j}^{l},\mathfrak{C})$ таблицы сопряжено с полным перебором произвольных наборов дочерних ячеек (11), число которых не превосходит
$\mathop {({{m}^{2}}n)}\nolimits^{|\mathfrak{S}*|r \cdot {{2}^{{O(d)}}}} .$
Обработка произвольного набора (11) связана с перебором всевозможных интерфейсов $\Im $, число которых, в свою очередь, ограничено сверху:
$\mathop {({{m}^{2}}n)}\nolimits^{|\mathfrak{S}*|r(r + 1){{2}^{{O(d)}}}} .$
Проверка согласованности произвольного интерфейса $\Im $, очевидно, может быть произведена за время, органиченное сверху его размером, т.е.
$O({\kern 1pt} {\text{|}}\mathfrak{S}{\kern 1pt} *{\kern 1pt} {\text{|}}{\kern 1pt} \, \cdot (r + 1) \cdot {{2}^{{O(d)}}} \cdot r) = {\text{poly}}(n),$
где ${\text{poly}}(n)$ обозначает некоторый полином от размера входных данных.

Соответственно, общая трудоемкость схемы с учетом выполнения условий $r = m$ и ${\text{|}}\mathfrak{S}{\kern 1pt} *{\text{|}} = {\text{polylog}}n$ составит

${\text{poly}}(n) \cdot {{({{m}^{2}}n)}^{{\operatorname{polylog} n \cdot {{m}^{2}} \cdot {{2}^{{O(d)}}}}}},\quad {\text{где}}\quad m = O\left( {\mathop {\left( {\frac{{d(logn - log\varepsilon )}}{\varepsilon }} \right)}\nolimits^d } \right).$
Таким образом, нами обоснован основной результат данной статьи.

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

5. ЗАКЛЮЧЕНИЕ

В данной работе обосновывается аппроксимационная схема для метрической постановки классической задачи CVRP. Показано, что описанный в статье алгоритм реализует квазиполиномиальную приближенную схему (QPTAS) при условии, что задача сформулирована в метрическом пространстве произвольной фиксированной размерности удвоения $d > 1$ и обладает оптимальным решением, число маршрутов которого не превосходит $\operatorname{polylog} n$. Второе условие выполнено всякий раз, когда грузоподъемность $q = \Omega (n{\text{/}}{\kern 1pt} \operatorname{polylog} n)$. Отметим, что конечной размерностью удвоения обладает широкий класс метрик, порождаемых большими графами, возникающими, в том числе, в процессе описания современных социальных сетей. Поэтому применимость полученных в статье результатов не ограничивается исключительно транспортными задачами.

Тем не менее вопрос об аппроксимируемости общих постановок задачи CVRP, не стесненных дополнительными ограничениями на рост грузоподъемности, сформулированных в метрических пространствах такого типа, в классе квазиполиномиальных приближенных схем до сих пор остается открытым. Авторы планируют вернуться к нему в одной из ближайших работ.

Список литературы

  1. Demir E., Huckle K., Syntetos A., Lahy A., Wilson M. Vehicle routing problem: past and puture, Cham: Springer Inter. Publ., 2019. P. 97–117.

  2. Laporte G. Fifty years of vehicle routing // Transport. Sci. 2009. V. 43. P. 408–416.

  3. Toth P., Vigo D. Vehicle routing: problems, methods and applications, 2nd Ed. MOS-Siam Ser. on Optimizat. SIAM, 2014. P. 53–85.

  4. Dantzig G., Ramser J. The truck dispatching problem // Management Sci. 1959. V. 6. Iss. 1. P. 80–91.

  5. Drexl M. Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments // Networks. 2014. V. 63. № 1. P. 119–133.

  6. Hokama P., Miyazawa F.K., Xavier E.C. A branch-and-cut approach for the vehicle routing problem with loading constraints // Expert Systems with Appl. 2016. V. 47. P. 1–13.

  7. Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing // Math. Program. Comp. 2017. V. 9. № 1. P. 61–100.

  8. Pessoa A.A., Sadykov R., Uchoa E. Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems // Europ. J. of Operat. Res. 2018. V. 270. № 2. P. 530–543.

  9. Arnold F., Sorensen K. Knowledge-guided local search for the vehicle routing problem // Comput. Operat. Res. 2019. V. 105. P. 32–46.

  10. Avdoshin S., Beresneva E. Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study // Proceed. Inst. for System Program. of RAS. 2019. V. 331. P. 121–138.

  11. Qiu M., Fu Zh., Eglese R., Tang Q. A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups // Comp. Operat. Res. 2018. V. 100. P. 102–116.

  12. Frifita S., Masmoudi M. VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties // Inter. Transact. in Operat. Res. 2020. V. 27. № 1. P. 291–313.

  13. Polat O. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups // Comp. Operat. Res. 2017. V. 85. P. 71–86.

  14. Nazari M., Oroojlooy A., Takac M., Snyder L.V. Reinforcement learning for solving the vehicle routing problem. Proceed. of the 32nd Inter. Conf. on Neural Inform. Process. Syst., Curran Associates Inc., Red Hook, NY, USA, 2018. P. 9861–9871.

  15. Vidal Th., Crainic T.G., Gendreau M., Prins Ch. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows // Comput. Oper. Res. 2013. V. 40. № 1. P. 475–489.

  16. Necula R., Breaban M., Raschip M. Tackling dynamic vehicle routing problem with time windows by means of ant colony system // 2017 IEEE Congress on Evolutionary Comput. (CEC), 2017. P. 2480–2487.

  17. Su-Ping Y., Wei-Wei M. An improved ant colony optimization for VRP with time windows // Inter. J. of Signal Proc., Image Proc. and Pattern Recognit. 2016. V. 9. P. 327–334.

  18. Chen, Gui, Ding, Zhou. Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on tabu search // Sustainability. 2019. V. 11.

  19. Nalepa J., Blocho M. Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows // Soft Comput. 2016. V. 20. № 6. P. 2309–2327.

  20. Papadimitriou Ch. Euclidean TSP is NP-complete // Theor. Comput. Sci. 1977. V. 4. Iss. 3. P. 237–244.

  21. Asano T., Katoh N., Tamaki H., Tokuyama T. Covering points in the plane by K-tours: towards a polynomial time approximation scheme for general K // Proceed. of the Twenty-ninth Ann. ACM Symp. on Theory of Comput., STOC '97, ACM, El Paso, Texas, USA, 2017. P. 275–283.

  22. Haimovich M., Rinnooy Kan A.H.G. Bounds and heuristics for capacitated routing problems // Math. of Operat. Res. 1985. V. 10. № 4. P. 527–542.

  23. Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems // J. of the ACM. 1998. V. 45. Iss. 5. P. 753–782.

  24. Das A., Mathieu C. A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing // Algorithmica. 2015. V. 73. P. 115–142.

  25. Adamaszek A., Czumaj A., Lingas A. PTAS for k-tour cover problem on the plane rof moderately large values of k // Inter. J. of Foundat. of Comp. Sci. 2010. V. 21. № 6. P. 893–904.

  26. Khachai M.Yu., Dubinin R.D. Approximability of the vehicle routing problem in finite-dimensional euclidean spaces // Proceed. of the Steklov Instit. of Math. 2017. V. 297. № 1. P. 117–128.

  27. Khachay M., Dubinin R. PTAS for the Euclidean capacitated vehicle routing problem in Rd // LNCS, V. 9869, Discrete Opt. and Operat. Res.: 9th Inter. Conf., DOOR 2016, Vladivostok, Russia, September 19–23, 2016. P. 193–205.

  28. Khachay M., Zaytseva H. Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem // LNCS, V. 9486. Combinatorial Opt. and Appl.: 9th Inter. Conf., COCOA 2015, Houston, TX, USA, December 18–20, 2015. P. 178–190.

  29. Khachay M., Zaytseva H. Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem // LNCS, V. 9486. Combinatorial Opt. and Appl.: 9th Inter. Conf., COCOA 2015, Houston, TX, USA, December 18–20, 2015. P. 178–190.

  30. Khachay M.Yu., Ogorodnikov Yu.Yu. Efficient PTAS for the Euclidean CVRP with time windows // LNCS, V. 11179. Anal. of Images, Social Networks and Texts – 7th Inter. Conf., AIST 2018. Springer Inter. Publ., 2018. P. 318–328.

  31. Khachay M.Yu., Ogorodnikov Yu.Yu. Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand // LNCS, V. 11548. Math. Optimizat. Theory and Operations Res. 18th Inter. Conf. (MOTOR 2019). Springer Inter. Publ., 2019. P. 309–327.

  32. Becker A., Klein P.N., Schild A. A PTAS for bounded-capacity vehicle routing in planar graphs // Algorithms and Data Structures. Springer Inter. Publ., 2019. P. 99–111.

  33. Khachai M.Y., Ogorodnikov Y.Y. Haimovich–Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension // Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2019. V. 25. Iss. 4. P. 235–248.

  34. Talwar K. Bypassing the embedding: algorithms for low dimensional metrics // Proceed. of the Thirty-Sixth Ann. ACM Symp. on Theory of Comp. Associat. for Comp. Machinery, New York, NY, USA, 2004. P. 281–290.

  35. Bartal Y., Gottlieb L.A., Krauthgamer R. The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme // SIAM J. on Comp. 2016. V. 45. № 4. P. 1563–1581.

  36. Abraham I., Bartal Y., Neiman O. Advances in metric embedding theory // Adv. in Math. 2011. V. 228. № 6. P. 3026–3126.

  37. Gupta A., Krauthgamer R., Lee J.R. Bounded geometries, fractals, and low-distortion embeddings // 44th Ann. IEEE Symp. on Foundat. of Comp. Sci., 2003. P. 534–543.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал