Эффективные алгоритмы с гарантированными оценками точности для задачи маршрутизации транспорта ограниченной грузоподъемности тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Огородников Юрий Юрьевич

• Огородников Юрий Юрьевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Огородников Юрий Юрьевич

3.2.1 Основная идея

3.2.2 Предварительные сведения

3.2.3 Аппроксимационная схема

Заключение

Публикации автора по теме диссертации

Благодарности

Литература

ВВЕДЕНИЕ

Предметом исследования данной диссертационной работы является аппроксимация метрических постановок задачи маршрутизации транспортных средств ограниченной грузоподъемности (Capacitated Vehicle Routing Problem, CVRP) в классе алгоритмов с гарантированными оценками точности.

Актуальность темы

Задача CVRP является одной из наиболее известных задач комбинаторной оптимизации, имеющей огромное число значимых приложений в области исследования операций [136, 101, 129]. По всей видимости, данная задача была впервые введена в знаменитой работе Г.Данцига и Дж.Рамсера [43], посвященной математическому моделированию процесса снабжением топливом сети заправочных станций и может быть сформулирована следующим образом.

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

Как и для большинства современных задач комбинаторной оптимизации (см. напр. [63, 143, 106, 147, 121]), исследования в области алгоритмического анализа CVRP традиционно развиваются в рамках следующих основных направлений. Первое направление основано на редукции исходной задачи к подходящей постановке задачи целочисленного (смешанного) программирования с последующим поиском оптимального решения последней с помощью той или иной модификации метода ветвей и границ (см. обзор в [129]). К сожалению, несмотря на стремительные темпы развития вычислительной техники и очевидные успехи последних лет в области совершенствования алгоритмов (см., напр. [76, 116, 71]) практическая применимость данного подхода

по-прежнему ограничена постановками достаточно скромного размера ввиду известной КР-трудности задачи СУЯР.

Широкий спектр современных эвристических алгоритмов и метаэвристик составляет основу второго направления. Наибольшего успеха в области эффективной аппроксимируемости задачи удалось достичь в классах методов локального поиска [12, 17], поиска с запретами [127], переменных окрестностей (УКБ) [117, 54], методов машинного обучения [119], эволюционных [75] и биоинспирированных алгоритмов [108, 125], а также их комбинаций [107, 111]. Нередко эвристические алгоритмы демонстрируют потрясающую производительность, эффективно находя близкие к оптимальным или даже оптимальные решения для отдельных постановок СУЯР чрезвычайно большого размера. Тем не менее, в отсутствие теоретически обоснованных гарантий применение этих алгоритмов сопряжено с дополнительными трудозатратами, связанными с численным оцениванием их точности и возможной дополнительной настройкой внутренних параметров при переходе к каждому новому классу постановок.

Перечисленные аргументы подтверждают актуальность третьего направления, связанного с аппроксимируемостью задачи в классе эффективных алгоритмов с теоретическими оценками точности и трудоемкости (см., напр., [129, 143]). Как известно, задача СУЯР КР-трудна в сильном смысле, являясь обобщением классической задачи коммивояжера (ТБР), и сохраняет труднорешаемость (при условии, что грузоподъемность д является частью входа) даже на евклидовой плоскости [114]. Задача не аппроксимируема в общем случае (при Р = ЖР), АРХ-полна при произвольной метрике [65, 40] и остается АРХ-трудной при произвольной фиксированной грузоподъемности д >

Наибольших успехов в области аппроксимируемости задачи СУЯР удалось достичь в конечномерных числовых пространствах. Известные результаты в этой области восходят к классическим работам М. Хаймовича, А. Ринной Кана [65] и С. Ароры [13]. На данный момент, наиболее общим результатом для геометрической постановки СУЯР является квазиполиномиальная приближенная схема ^РТАБ) А.Дас и К.Матье [45]. Вводя ограничение на рост грузоподъемности д, удается обосновать полиномиальные (РТАБ) и даже эффективные (ЕРТАБ) приближенные схемы, среди которых рекордным на дан-

ный момент является алгоритм [2], позволяющий за полиномиальное время найти (1 + е)-приближенное решение задачи при условии q < 2log (} n.

Так или иначе до последнего времени полиномиальные и квазиполиномиальные приближенные схемы удавалось обосновать лишь для геометрических постановок задачи CVRP, за исключением, быть может, немногочисленных специальных случаев [23]. Долгое время, до появления пионерских работ К.Талвара [128] и Я.Бартала и коллег [20], аналогичным образом складывалась ситуация и с аппроксимируемостью близкой к CVRP задачи коммивояжера. Предложенный в этих работах подход позволил распространить классический результат С.Ароры [13], заключающийся в существовании полиномиальных приближенных схем (PTAS) для TSP в Rd, на существенно более широкий класс постановок задачи коммивояжера, задаваемых в метрических пространствах произвольной фиксированной размерности удвоения. Впоследствии аналогичные результаты были получены для ряда близких комбинаторных задач, в том числе для задачи коммивояжера со сбором призов (Prize Collecting Traveling Salesman Problem, PCTSP) [30], задачи коммивояжера с окрестностями [31] и задачи о k-медианах [36]. Тем не менее, для CVRP до последнего момента подобные результаты получить не удавалось.

Заметим, что абсолютное большинство известных результатов в области эффективной аппроксимируемости геометрической задачи CVRP, было получено лишь для ее базовой постановки, не принимающей в расчет целый ряд дополнительных ограничений, представляющих практический интерес (см. например, обзор [129]). Среди немногих известных результатов в этой области отметим PTAS и EPTAS для постановок CVRP, заданных в R3 [99] и Rd, при произвольной фиксированной размерности d > 1 [85, 84]. Для постановок CVRP, стесненных дополнительными ограничениями, известны PTAS для задачи CVRP с несколькими складами (Multiple-Depot Capacitated Vehicle Routing Problem, MDCVRP), разработанная С.Кардоном и коллегами [113] на основе классического подхода Хаймовича-Ринной Кана, и впоследствии распространенная на случай пространства Rd [85]. Также известна QPTAS, предложенная Л.Сонгом [123] для постановок задачи CVRP с временными промежутками обслуживания клиентов (Capacitated Vehicle Routing Problem with Time Windows, CVRPTW), заданная в конечномерном числовом пространстве. Тем не менее, до недавнего времени для CVRPTW не удавалось

разработать схемы, являющиеся PTAS и EPTAS, даже при дополнительных ограничениях на рост грузоподъемности.

Пожалуй, наиболее слабо изученными с точки зрения построения алгоритмов с гарантированными оценками точности до недавнего времени являлись геометрические постановки CVRP с неоднородностью клиентского спроса, который, в свою очередь, может быть как разделяемым (Capacitated Vehicle Routing with Splittable Demand, CVRP-SD) и обслужен несколькими маршрутами, так и неразделяемым (Capacitated Vehicle Routing with Non-Splittable Demand, CVRP-NSD), который должен быть удовлетворен при единократном посещении.

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

Цель работы

Данная работа преследует следующие две цели:

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

(b) построение PTAS и EPTAS для геометрических постановок CVRP, стесненных дополнительными ограничениями на временные промежутки обслуживания и неоднородность клиентского спроса.

Основные результаты

1. Обоснована аппроксимируемость постановок NP-трудной задачи CVRP в классах QPTAS и PTAS, заданных в метрических пространствах произвольной размерности удвоения. В частности:

(a) показано, что схема Хаймовича-Ринной Кана сохраняет свои аппроксимативные свойства при тех же ограничениях на рост параметров, для которых она была сформулирована на евклидовой плоскости;

(b) установлена аппроксимируемость в классе QPTAS для постановок CVRP, оптимальное решение которых состоит из не более, чем polylog n маршрутов;

(c) наиболее общий для конечномерных пространств результат Дас-Матье распространен на случай упоминаемых выше пространств при дополнительном условии q = polylog n.

2. Для геометрических постановок СУЯР: (а) впервые обоснована аппроксимируемость задачи СУЯР с дополнительным ограничением на временные промежутки обслуживания (СУЯРТ'^ в классах РТАБ при д = п) и р = п), и ЕРТАБ при произвольных фик-

сированных д и р;

(Ь) для постановок СУЯР, стесненных ограничениями на временные промежутки обслуживания и неоднородность клиентского спроса, построена РТАБ с рекордной верхней оценкой грузоподъемности д < 210^п, 6 = О(е).

Научная новизна

В данной работе, носящей теоретический характер, впервые обоснована аппроксимируемость в классах квазиполиномиальных и полиномиальных приближенных схем постановок СУЯР, заданных в метрических пространствах произвольной фиксированной размерности удвоения. В частности, установлено, что классический подход Хаймовича-Ринной Кана реализует РТАБ при тех же дополнительных ограничениях (на рост грузоподъемности), что и на евклидовой плоскости (для которой он был первоначально предложен), то есть при д = п). Развитие подхода для постановок задачи коммивояжера в метрических пространствах произвольной фиксированной размерности удвоения, рассмотренного в работах К.Талвара [128] и Я.Бартала и коллег [20], и идей А.Дас и К.Матье [45] для СУЯР в конечномерных числовых пространствах позволило обосновать существования квазиполиномиальных приближенных схем для д = O(polylog (п)) и д = и (п/ро1у^ (п)), соответственно.

Впервые обоснованы полиномиальные приближенные схемы для нескольких геометрических постановок СУЯР с дополнительными ограничениями на временные промежутки обслуживания клиентов и неоднородным потребительским спросом.

Методы исследований

При обобщении схемы Хаймовича-Ринной Кана использовались современные результаты в области метрических пространств произвольной фиксированной размерности удвоения, в том числе обобщение классической теоремы Ассуада [1], гарантирующее вложение с константным искажением таких про-

странств в числовые пространства фиксированной размерности. При построении квазиполиномиальных приближенных схем для CVRP в метрических пространствах произвольной фиксированной размерности удвоения применялись методы рандомизированной иерархической кластеризации [20], опирающиеся на структурную теорему К.Талвара [128] и развивающие классический подход С. Ароры [13] к эффективной аппроксимируемости геометрической задачи коммивояжера.

Для построения приближенных алгоритмов с гарантированными оценками точности для CVRPTW и CVRPTW-SD использовались методы комбинаторики и теории графов, а также принципы декомпозиции, сводящие исходную задачу к ряду подзадач меньшей размерности [2].

На защиту выносится

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

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях: 7 и 8 Международной конференции по анализу изображений, сетей и текстов AIST (Москва, 2018; Казань, 2019); 9 и 10 Международной конференции 'Optimization and Applications' OPTIMA (Черногория, Петровац, 2018,

2019); 9 IFAC Conference on Manufacturing Modelling, Management, and Control MIM 2019 (Германия, Берлин, 2019); 18 и 19 Международной конференции по математической теории оптимизации и исследованию операций MOTOR (Екатеринбург, 2019; Новосибирск, 2020); 13 and 14 Conference on Learning and Intelligent Optimization LION (Греция, Ханья, 2019; Греция, Афины,

2020); 19 Всероссийской конференции с международным участием «Математические методы распознавания образов» ММРО (Москва, 2019), 12 между-

народной конференции «Интеллектуализация обработки информации» IDP (Италия, Гаэта, 2018), 51 Международной молодежной школе-конференции «Современные проблемы математики и ее приложений» SOPROMAT (Екатеринбург, 2020), Общероссийском семинаре «Информатика, управление и системный анализ» (МГУ, Москва, 2020), а также семинарах отдела математического программирования Института математики и механики им. Н.Н.Красовского УрО РАН.

Публикации

Основные результаты по теме диссертации изложены в 13 статьях, 5 из которых опубликованы в журналах, рекомендованных ВАК. Все публикации индексируются в базах данных Web Of Science и/или Scopus.

Личный вклад

Личный вклад состоит в непосредственном получении всех результатов и подготовке публикаций по теме диссертации. В работах [98, 93, 97, 96] соискателю принадлежит доказательство корректности аппроксимационной схемы, а также построение алгоритма динамического программирования. В работах [98, 97] соавтору Д.М.Хачаю принадлежит идея реализации структуры данных, используемой в алгоритме. В работе [83] диссертантом была обоснована оценка относительной погрешности схемы Хаймовича-Ринной Кана для постановок CVRP, заданных в метрических пространствах произвольной фиксированной размерности удвоения.

Для полиномиальных и эффективных полиномиальных приближенных схем, разработанных для геометрических постановок задачи CVRPTW [82, 92, 94, 91, 88], диссертантом были получены оценки точности и трудоемкости, а также была предложена идея алгоритма по выбору «промежуточных» клиентов. Для геометрических постановок задачи CVRP, стесненных как ограничениями на временные промежутки обслуживания, так и на неоднородность клиентского спроса [89, 95, 90] соискателем были выдвинуты идея «слотов», соответствующих одинаковым временным окнам, и предложение обслуживать часть единиц клиентского спроса тривиальными маршрутами. Помимо этого, диссертанту принадлежат доказательства всех утверждений и теорем, предложенных научным руководителем, а также обоснование точности и тру-

доемкости совместно построенных алгоритмов.

Структура и объем работы

Диссертация изложена на 140 страницах, содержит введение, три главы, заключение и список публикаций автора по теме диссертации, благодарности и список литературы, состоящий из 147 источников.

Содержание работы

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

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

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

Раздел 1.2 посвящен описанию постановки СУЯР в ее базовой формулировке.

В разделе 1.3 содержится обзор задач, имеющих близкое отношение к СУЯР: задача коммивояжера (ТБР), задача о т коммивояжерах (т-ТБР); задача о цикловом покрытии (ССР).

Раздел 1.4 посвящен формулировке классической постановки задачи СУЯР и обсуждению ее вычислительного статуса; проведена классификация подходов к построению решения СУЯР, согласно которой методы делятся на точные, эвристические и алгоритмы с гарантированными оценками точности. Для последних описаны наиболее значимые результаты.

Раздел 1.5 содержит описание наиболее часто рассматриваемых расширений задачи СУЯР, полученных введением временных промежутков обслуживания, неоднородности спроса, а также их сочетания.

Вторая глава работы целиком посвящена описанию аппроксимационных схем для постановок СУЯР, заданных в метрических пространствах произвольной фиксированной размерности удвоения. Так, в разделе 2.2 показывается, что схема Хаймовича-Ринной Кана реализует РТАБ (ЕРТАБ) при тех же условиях, что и в конечномерных числовых пространствах.

В разделе 2.3 приведена приближенная схема, являющаяся QPTAS при ограничении д = и (п/ро!у^ (п)), развивающая подход К.Талвара [128] к

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

В разделе 2.4 показано, как можно расширить область применения схемы Дас-Матье на рассматриваемые пространства. Показано, что исходная схема полностью сохраняет свои аппроксимативные свойства при q = polylog (n).

В третье главе приводится описание приближенных схем для некоторых расширенных постановок CVRP.

В разделе 3.1 содержится описание двух аппроксимационных схем, разработанных для задачи CVRPTW, первая из которых является PTAS при q = o(loglog n) и p = o(loglog n), где p — число временных промежутков обслуживания и EPTAS при фиксированных q и p. Вторая же схема является PTAS при существенно более широких значениях параметрах p и q, связанных соотношением p3q4 = 0(log n).

В разделе 3.2 приведена аппроксимационная схема для расширенной постановки задачи маршрутизации транспорта на евклидовой плоскости, сочетающей в себе как ограничения на временные интервалы обслуживания, так и неоднородный разделяемый спрос, являющаяся PTAS при q < 2log n, S = O(E).

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

ГЛАВА 1

ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТА И ЕЕ

ОБОБЩЕНИЯ

1.1 Основные определения

Задачей комбинаторной оптимизации I называется множество упорядоченных пар I = (X/, W/), называемых также индивидуальными задачами (англ. instances), где X/ является множеством допустимых решений, на котором определена целевая функция W/ : X/ ^ R+, значение W/(x) которой часто имеет смысл стоимости (или веса) объекта x. В зависимости от критерия оптимизации цель задачи состоит в нахождении оптимального значения

OPT* = min(max){W/(x) : x £ X/}

и соответствующего ему оптимального решения x*, для которого W/(x*) = Орт*. в данной работе мы ограничимся рассмотрением комбинаторных задач минимизации.

Особенностью большинства задач комбинаторной оптимизации является то, что при каждом I множество X/ является конечным, а целевая функция W/ вычислимой [77], что делает возможным нахождение оптимального значения OPT* за конечное время, в том числе путем полного перебора всех допустимых решений. Как правило постановки задачи I [55] задаются в терминах графов или сетей и могут быть закодированы тем или иным стандартным образом. Один из способов кодировки связан с известной [39] RAM-моделью вычислений, в которой произвольная элементарная математическая операция над любыми числовыми параметрами предполагается выполнимой за константное время. В этом случае длина записи Len(1) условия I может быть выражена исключительно в терминах размера соответствующего графа. Далее будем предполагать, что все рассматриваемые нами постановки основаны на RAM-модели и использовать стандартное обозначение n = Len(1) для длины записи постановки I.

Под алгоритмом будем понимать произвольную вычислимую функцию A, сопоставляющую индивидуальной задаче I некоторый объект А(1) £ X/, называемый допустимым решением задачи I. Алгоритм A, сопоставляющий произвольной постановке I задачи I ее оптимальное решение, принято назы-

вать точным.

Пусть C: N ^ R+. Алгоритм A называется C(n)-приближенным, если для произвольной постановки I £ I длины n вес допустимого решения Wj(A(I)) отличается от оптимального OPT* не более, чем в C(n) раз. Число C(n) называется фактором аппроксимации (или гарантированной оценкой точности).

Трудоемкостью алгоритма A будем называть функцию T: N ^ R+, ограничивающую сверху число операций, необходимых при нахождении A(I) для произвольной I £ I длины n. Алгоритм называется полиномиальным, если его трудоемкость T(n) ограничена полиномом poly(n) некоторой функции. Традиционно алгоритмы с полиномиальной оценкой трудоемкости принято называть эффективными [55].

В некоторых случаях для NP-трудных задач удается построить приближенную схему. Говорят, что задача I обладает полиномиальной приближенной схемой (PTAS), если для произвольного £ > 0 существует (1 + е)-приближенный алгоритм Ae, трудоемкость которого удовлетворяет соотношению T(n) = polye(n) для некоторого полинома polye(n).

В том случае, если polye(n) = f (1/е) • nc для некоторой константы c > 1 и произвольной вычислимой функции f, то PTAS называется эффективной полиномиальной приближенной схемой (EPTAS). Если T (n) = poly (1 ,nj, то схема называется вполне полиномиальной (FPTAS).

Трудоемкость T(n) приближенной схемы не всегда удается оценить сверху полиномом от размера входных данных. В частности, если T(n) = npolye(logn), то приближенная схема называется квазиполиномиальной (QPTAS).

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

1.2 Постановка задачи CVRP

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

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

Для последующих построений наряду с классической постановкой задачи СУЯР нам потребуется ее обобщение, известное в литературе как задача маршрутизации транспорта с ограниченной грузоподъемностью и неоднородным делимым спросом (СУЯР-БЭ) [47] .

Задача CVRP-SD. Пусть заданы полный вершинно- реберно- взвешенный граф О = (X и {у},Е,О,и) и натуральное число д. Здесь X = {ж1..., жп} — множество потребителей, у — склад, неотрицательная весовая функция О: X ^ Ъ+ задает объем спроса каждого из потребителей, симметричная весовая функция и: Е ^ сопоставляет произвольной паре вершин {м,^} С X и {у} транспортные издержки и(м,^), связанные с непосредственной перевозкой по ребру {м, V} £ Е, а д — верхняя оценка грузоподъемности используемых транспортных средств.

Маршрутом называется упорядоченная пара — = (п,£—), в которой п = у,ж^,... , ж^,у — (не обязательно простой) цикл в графе О, а функция

: X ^ Ъ+ задает распределение спроса потребителей, удовлетворяемого данным маршрутом.

Стоимость (вес) маршрута — определяется выражением

и(Я) = и(у,Жг1) + и(жг1 ,жг2) +-----Ъ Цж^ ,Жг4) + Цж», ,у).

Маршрут — = (п, £—) называется допустимым, если

( < О(ж), ж £ {ж^,..., ж^} 5-(ж) < и 5-(ж) < д.

[ = 0, в противном случае х€Х

Задача СУЯР-БЭ заключается в построении семейства & допустимых маршрутов минимальной суммарной стоимости, удовлетворяющего совокупный потребительский спрос:

(6) = и(—) ^ шт

(1.1)

и,

Ие6

^^—(ж) = О(ж) (ж £ X). —£6

Постановка классической задачи CVRP легко может быть получена из постановки (1.1) задачи CVRP-SD введением дополнительного ограничения D(x) = 1. Также, всюду далее мы будем обозначать через CVRP*(X) значение оптимального решения постановки задачи, заданной на множестве клиентов X.

Если функция w удовлетворяет неравенству треугольника, т.е. для произвольного подмножества {v1,v2,v3} С X U {y} справедливо соотношение w(vi,v2) < w(vi,v3) + w(v3, v2), то вершины графа G принято называть точками, величину w(u, v) — расстоянием между точками u и v, стоимость w(R) произвольного маршрута R - его длиной, а соответствующую постановку задачи - метрической. В данной диссертационной работе мы будем рассматривать исключительно метрические постановки задач.

1.3 Обзор задач, близких к CVRP

Одной из наиболее известных и близких к CVRP задач является задача коммивояжера (Traveling Salesman Problem, TSP), математическая постановка которой впервые была приведена в работе К.Менгера 1932 года [104]. Данная задача имеет широкий спектр приложений в области исследования операций (см., напр., [132]). Базовая постановка TSP связана с поиском в полном взвешенном графе G гамильтонова цикла (простого цикла, посещающего все вершины графа) минимального веса.

В 1954 году Дж.Данциг, Д.Фалкерсон и С.Джонсон сформулировали TSP в виде задачи дискретной оптимизации на графах и применили для ее решения метод ветвей и границ на примере частной постановки с 49 городами [42]. В последующие годы был получен ряд результатов по построению точных алгоритмов, одними из самых знаменитых среди которых являются методы динамического программирования Р.Беллмана [24] и М.Хелда и Р.Карпа [69], а также алгоритм Бьорклунда [26] с трудоемкостями 0(n22n) и 0(1.657n) соответственно. К сожалению, эти алгоритмы, как и все известные на данный момент точные методы (см., напр., [139, 63, 132]), не являются эффективными в силу их экспоненциальной трудоемкости и, в частности, с трудом применимы с практической точки зрения. В свою очередь, для решения постановок большого размера широко используется различные эвристики и метаэвристи-ки, среди которых хорошо зарекомендовали себя методы локального поиска

[48], метод переменных окрестностей [74], генетические алгоритмы [78], подробный обзор которых может быть найден, к примеру, в работе [63].

Наряду с разработкой вычислительно эффективных алгоритмов проводилась работа и в области исследования вычислительной сложности задач комбинаторной оптимизации. В 1971 году вышла знаменитая работа С.Кука [38], в которой были определены классы сложности P и NP, а также доказана NP-полнота задачи о выполнимости булевых формул. В следующем году Р.Карп обосновал NP-полноту для 21 задачи, среди которых была и TSP, путем сведения к ним проблемы выполнимости булевых формул [79]. Наконец, в конце 70-х годов Х.Пападимитриу показал, что даже евклидова постановка TSP является NP-трудной [114]. Таким образом, при P = NP точное решение вряд ли возможно получить эффективными методами даже для евклидовой TSP.

Тем не менее, для некоторых частных постановок TSP известны полиномиальные алгоритмы. Целью одной из таких постановок является поиск оптимального решения, состоящего из так называемых пирамидальных маршрутов вида (1 = vi,..., Угг = n, ,..., угп), где уг. < vlj+l при 1 < j < r - 1 и Vj > vij+1 при r + 1 < j < n — 1. Известно [138], что для постановок задач коммивояжера, матрицы расстояний которых задаются определенным образом, существует оптимальный пирамидальный маршрут, который может быть найден за полиномиальное время. В 90-х годах Х.Еномото, Я.Ода и К.Ота ввели классы маршрутов [50, 110, 109], являющихся обобщением пирамидальных, для которых задача поиска оптимального гамильтонова цикла полиномиальна разрешима.

Среди других частных случаев следует выделить постановку TSP, заданную графами с весами ребер 1 и 2. В 1993 году Х.Пападимитриу и М.Янакакис построили для данной постановки полиномиальный алгоритм с гарантированной оценкой точности 7/6. В 2006 году данная оценка была улучшена до 8/7 [25].

Широкое распространение имеют также эффективные алгоритмы с гарантированными оценками точности. В 1976 году С.Сани и Т.Гонзалез обосновали NP-трудность построения приближенного решения с произвольной точностью, меньшей 2n для общей постановки TSP [120]. Позднее было показано, что задача коммивояжера APX-трудна в произвольной метрике [115], а

также является NP-трудной даже в случае евклидовой плоскости [133].

Несмотря на это, для некоторых частных постановок задачи коммивояжера известен ряд алгоритмов с гарантированными оценками точности, одним из самых известных среди которых является 3/2-приближенный алгоритм Н.Кристофидеса и А.И.Сердюкова [33, 146], предложенный ими для метрической TSP. Для евклидовых постановок TSP на плоскости и в пространстве произвольной фиксированной размерности Ж.Митчелл [105] и С.Арора [13] практически одновременно и независимо разработали полиномиальные приближенные схемы. В последующей работе С.Рао и У.Смита [118] был представлен улучшенный вариант данной схемы с более низкой трудоемкостью (0(nlogn) против 0(n logn)O(1/e), где £ > 0).

Долго время результаты С.Ароры и их улучшения являлись рекордными с точки зрения аппроксимации TSP в конечномерных пространствах. В 2004 году К.Талвару удалось распространить схему С.Ароры [128] на существенно более широкий (по сравнению с конечномерным) класс пространств, обладающих фиксированной размерностью удвоения [1]. Позднее для постановок TSP, заданных в тех же самых пространствах, Я.Барталом и коллегами была разработана полиномиальная приближенная схема [20].

Еще одним вариантом эффективных алгоритмов с гарантированными оценками точности являются асимптотически точные алгоритмы, разрабатывающиеся новосибирской научной школой (Э.Х.Гимади, А.Н.Глебов, А.А.Агеев, В.В.Шенмайер). Для описания данных результатов нам понадобится следующия определения.

Будем говорить, что алгоритм A имеет оценки относительной погрешности £n и вероятности несрабатывания Sn в классе Kn задач размерности n, если для каждого n и входа I выполнено неравенство

где Р{•} — вероятность несрабатывания алгоритма.

Алгоритм называется асимптотически точным в классе задач К =

Одним из первых результатов, полученных в этом направлении, является асимптотически точный алгоритм для задачи коммивояжера на случайных входных данных, разработанный Э.Х.Гимади и В.А.Перепелицей в 1974 году

{Kn|n =1, 2,...}, если для него существуют оценки £

[142]. Позднее данный подход был распространен на ряд задач, родственных TSP, среди которых стоит отметить задачу нескольких коммивояжеров (m-Peripatetic Salesman Problem, m-PSP) [10, 141, 59, 60], целью которой является поиск нескольких реберно-непересекающихся гамильтоновых циклов, оптимизирующих суммарный вес, максимум весов или иной интегральный критерий. Другими важными результатами являются полиномиальные приближенные схемы для постановок задачи коммивояжера на максимум, полученных для ряда специальных случаев

Вышеприведенные результаты справедливы для постановок задачи коммивояжера, заданных на неориентированных графах. В случае, когда граф является ориентированным, постановка TSP является асимметричной (Asymmetric Traveling Salesman Problem, ATSP). Для ATSP, также как и для TSP, существует широкий спектр прекрасно зарекомендовавших себя эвристик [145, 134], однако результаты в области построения эффективных алгоритмов с гарантированными оценками точности существенно более скудны. В частности, в 1982 году А.Фриз [53] построил первый приближенный алгоритм для ATSP с оценкой log2(n). В последующие годы вышел ряд работ, улучшающих данную оценку до 0.99log2(n) [27], 0.842 log2(n) [8] и | log2(n) [51]. Существенным прорывом стал 506-приближенный алгоритм, предложенный О.Свенссоном и коллегами [126] в 2018 году. В следующем году В.Трауб и Дж.Виген [130, 131] улучшили данный подход, получив 22 + £-приближенный алгоритм, что является наилучшим результатом в области построения ап-проксимационных схем для ATSP на текущий момент.

Другим важным расширением TSP является задача о цикловом покрытии графа (Cycles Cover Problem, CCP), заключающаяся в поиске оптимального покрытия графа вершинно-непересекающимися циклами [120]. В случае, когда требуется построить ровно k циклов минимального суммарного веса, говорят о задаче Minimum-weight k-Size Cycle Cover Problem (Min-k-SCCP), являющейся частным случаем CCP. На содержательном уровне Min-k-SCCP может трактоваться как поиск k маршрутов, выполняемых транспортных средством, посещающим соответствующее множество клиентов. С данной точки зрения Min-k-SCCP близка к задаче маршрутизации транспортных средств и играет важную роль при разработке приближенных схем для VRP [67].

Очевидно, что при k = 1 Min-k-SCCP совпадает с задачей коммивояжера.

Более того, при k > 1 задача Min-k-SCCP обладает теми же аппроксимативными свойствами, что и TSP [80, 86], являясь, в частности, NP-трудной задачей в сильном смысле даже в евклидовой постановке. Тем не менее, в результате недавних исследований был получен 2-приближенный алгоритмом для Min-k-SCCP с асимптотически достижимой оценкой точности [86, 80]. Также известны полиномиальные приближенные схемы для постановок Min-k-SCCP, заданных на евклидовой плоскости при k = 2, [81], и в евклидовом пространстве произвольной фиксированной размерности d при k = O(log n) [87]. Кроме того, для евклидовой Max-k-SCCP Э.Х.Гимади и И.А.Рыков предложили асимптотически точные алгоритмы с кубической трудоемкостью в пространстве произвольной фиксированной размерности при k = o(n) [58], а для задачи Min-k-SCCP на случайных входных данных при мощности цикловых покрытий k < n1/3/ ln n [57].

Наконец, еще одним важной родственной CVRP задачей является задача о размещении производств (Facility Location Problem, FLP), по-видимому впервые сформулированная М.Балински в 1965 году [18]. Базовая постановка FLP задается потенциальным множеством точек размещения L, где могут быть открыты предприятия, производящие продукцию, и точек D, в которых находятся объекты, подлежащие обслуживанию. Целью является поиск подмножества F С L такого, что сумма расстояний от каждой точки обслуживания до ближайшего обслуживающего предприятия и стоимости размещения предприятий F минимальны.

Список литературы диссертационного исследования кандидат наук Огородников Юрий Юрьевич, 2021 год

ЛИТЕРАТУРА

1. Abraham Ittai, Bartal Yair, Neiman Ofer. Advances in metric embedding theory // Advances in Mathematics. — 2011. — Vol. 228, no. 6. — Pp. 3026 - 3126.

2. Adamaszek Anna, Czumaj Artur, Lingas Andrzej. PTAS for k-Tour Cover Problem on the Plane rof Moderately Large Values of k // International Journal of Foundations of Computer Science. — 2010. — Vol. 21, no. 06. — Pp. 893-904. https://doi.org/10.1142/S0129054110007623.

3. Adamaszek C., Czumaj A., Lingas A. PTAS for k-tour cover problem on the plane for moderately large values of k // Manuscript. — 2009. — Vol. 1.

4. Aggarwal Divya, Kumar Vijay. Performance evaluation of distance metrics on Firefly Algorithm for VRP with time windows // International Journal of Information Technology. — 2019. — Nov.

5. Altinkemer Kemal, Gavish Bezalel. Heuristics for unequal weight delivery problems with a fixed error guarantee // Operations Research Letters. — 1987. — Vol. 6, no. 4. — Pp. 149 - 158.

6. Altinkemer Kemal, Gavish Bezalel. Heuristics for Delivery Problems with Constant Error Guarantees // Transportation Science. — 1990. — Vol. 24, no. 4. — Pp. 294-297.

7. Andrews George E., Eriksson Kimmo. Integer Partitions. — 2nd edition. — Cambridge University Press, 2004.

8. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs / Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko. — Vol. 52. — 2003. — 11. — Pp. 56 - 65.

9. Approximation algorithms for deadline-TSP and vehicle routing with timewindows / N. Bansal, A. Blum, S. Chawla, A. Meyerson // STOC '04. — 2004.

10. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 / A. Baburin, Federico Della Croce, E. Gimadi et al. // Discrete Applied Mathematics. — 2009. — 05. — Vol. 157. — Pp. 1988-1992.

11. Archetti C., Speranza M.Grazia. The Split Delivery Vehicle Routing Problem: A Survey. — 2008. — 01. — Vol. 43. — Pp. 103-122.

12. Arnold Florian, Sorensen Kenneth. Knowledge-guided local search for the vehicle routing problem // Computers & Operations Research. — 2019. — Vol. 105. — Pp. 32-46.

13. Arora S. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other geometric problems // Journal of the ACM. — 1998. — Vol. 45. — Pp. 753-782.

14. Arora S., Safra S. Probabilistic checking of proofs: a new characterization of NP // Journal of the ACM. — 1998. — 1. — Vol. 45. — Pp. 70-122.

15. Asano Tetsuo, Katoh Naoki, Kawashima Kazuhiro. A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree // Journal of Combinatorial Optimization. — 2001. — 06. — Vol. 5. — Pp. 213-231.

16. Assouad Patrice. Plongements lipschitziens dans Rn // Bulletin de la Societe Mathematique de France. — 1983. — Vol. 111. — Pp. 429-448.

http://eudml.org/doc/87452.

17. Avdoshin Sergey, Beresneva Ekaterina. Local search metaheuristics for Capacitated Vehicle Routing Problem: a comparative study // Proceedings of the Institute for System Programming of RAS. — 2019. — Vol. 31. — Pp. 121-138.

18. Balinski Michel. Integer Programming: Methods, Uses, Computations // Management Science. — 1965. — 11. — Vol. 12. — Pp. 253-313.

19. Bansal Manisha, Garg Naveen, Gupta Neelima. A 5-Approximation for Capacitated Facility Location // Algorithms - ESA 2012 / Ed. by Leah Epstein, Paolo Ferragina. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. — Pp. 133-144.

20. Bartal Yair., Gottlieb Lee-Ad., Krauthgamer Robert. The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme // SIAM Journal on Computing. — 2016. — Vol. 45, no. 4. — Pp. 1563-1581.

21. Baluch H., Lingas A. An Inclusion-Exclusion Algorithm for the k-tour Problem. — 2011.

22. Becker Amariah, Klein Philip N., Saulpic David. A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs // 25th Annual European Symposium on Algorithms (ESA

2017) / Ed. by Kirk Pruhs, Christian Sohler. — Vol. 87 of Leibniz International Proceedings in Informatics (LIPIcs). — Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. — Pp. 12:1-12:15. http://drops.dagstuhl.de/opus/volltexte/2017/7878.

23. Becker Amariah, Klein Philip N., Schild Aaron. A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs // Algorithms and Data Structures / Ed. by Zachary Friggstad, Jorg-Rüdiger Sack, Mohammad R Salavatipour. — Cham: Springer International Publishing, 2019.

— Pp. 99-111.

24. Bellman Richard. Dynamic Programming Treatment of the Travelling Salesman Problem //J. ACM. — 1962. — Vol. 9, no. 1. — Pp. 61-63.

25. Berman Piotr, Karpinski Marek. 8/7-Approximation Algorithm for (1,2)-TSP. — 2006. — 01. — Pp. 641-648.

26. Bjorklund Andreas. Determinant Sums for Undirected Hamiltonicity // SIAM Journal on Computing. — 2014. — Vol. 43, no. 1. — Pp. 280-299.

27. Blaser Markus. A New Approximation Algorithm for the Asymmetric TSP with Triangle Inequality // ACM Transactions on Algorithms. — 2008. — 08. — Vol. 4.

28. Bompadre Agustin, Dror Moshe, Orlin James B. Improved bounds for vehicle routing solutions // Discrete Optimization. — 2006. — Vol. 3, no. 4.

— Pp. 299 - 316.

29. Braekers Kris, Ramaekers Katrien, Van Nieuwenhuyse Inneke. The vehicle routing problem: State of the art classification and review // Computers & Industrial Engineering. — 2016. — Vol. 99. — Pp. 300 - 313.

30. Chan T.-H, Jiang Haotian, Jiang Shaofeng. A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics // ACM Transactions on Algorithms. — 2017. — 10. — Vol. 16.

31. Chan T.-H. Hubert, Jiang Shaofeng H.-C. Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics // ACM Trans. Algorithms. — 2018. — jan. — Vol. 14, no. 1. — 18 pp.

32. Chiang Wan Chen, Cheng Chen Yang. Considering the Performance Bonus Balance in the Vehicle Routing Problem with Soft Time Windows // Procedia Manufacturing. — 2017. — Vol. 11. — Pp. 2156 - 2163. — 27th

International Conference on Flexible Automation and Intelligent Manufacturing, FAIM2017, 27-30 June 2017, Modena, Italy.

33. Christofides N. Worst-case analysis of a new heuristic for the Traveling Salesman Problem // Symposium on New Directions and Recent Results in Algorithms and Complexity. — 1975. — P. 441.

34. Christofides N., Eilon S. An Algorithm for the Vehicle-Dispatching Problem // OR. — 1969. — Vol. 20, no. 3. — Pp. 309-318. http://www.jstor.org/stable/3008733.

35. Christofides Nicos, Mingozzi A., Toth P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations // Mathematical Programming. — 1981. — Vol. 20. — Pp. 255-282.

36. Cohen-Addad Vincent, Feldmann Andreas, Saulpic David. Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. — 2018. — 12.

37. A Comprehensive Study of Vehicle Routing Problem With Time Windows Using Ant Colony Optimization Techniques / Avirup Neogi, Singamred-dy Mounika, Salagrama Kalyani, S.A. Sai // International Journal of Engineering and Technology(UAE). — 2018. — 05. — Vol. 7. — Pp. 80-85.

38. Cook Stephen A. The Complexity of Theorem-Proving Procedures // Proceedings of the Third Annual ACM Symposium on Theory of Computing. — STOC '71. — New York, NY, USA: Association for Computing Machinery, 1971. — P. 151-158.

39. Cook Stephen A., Reckhow Robert A. Time bounded random access machines // Journal of Computer and System Sciences. — 1973. — Vol. 7, no. 4. — Pp. 354 - 375.

40. Covering Points in the Plane by K-tours: Towards a Polynomial Time Approximation Scheme for General K / Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama // Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. — STOC '97. — New York, NY, USA: ACM, 1997. — Pp. 275-283.

41. Covering points in the plane by k-tours: a polynomial time approximation scheme for fixed k / T. Asano, N. Katoh, H. Tamaki, T. Tokuyama // IBM Tokyo Research. — 1996.

42. Dantzig G., Fulkerson R., Johnson S. Solution of a Large-Scale Traveling-Salesman Problem // Journal of the Operations Research Society of America. — 1954. — Vol. 2, no. 4. — Pp. 393-410. http://www.jstor.org/stable/166695.

43. Dantzig George B, Ramser John H. The truck dispatching problem // Management science. — 1959. — Vol. 6, no. 1. — Pp. 80-91.

44. Das Aparna, Mathieu Claire. A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing // Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. — SODA '10. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2010. — Pp. 390-403.

45. Das Aparna, Mathieu Claire. A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing // Algorithmica. — 2015. — Vol. 73. — Pp. 115-142.

46. Distributed Solving of the VRPTW with Coefficient Weighted Time Distance and Lambda Local Search Heuristics / A Galic, B Sc, Tonci Caric et al. — 2006. — 01.

47. Dror Moshe, Trudeau Pierre. Savings by Split Delivery Routing // Transportation Science. — 1989. — 05. — Vol. 23. — Pp. 141-145.

48. El Krari Mehdi, Ahiod Belaid, el Benani Youssef B. Breakout Local Search for the Travelling Salesman Problem // Computing and Informatics. — 2018. — 01. — Vol. 37. — Pp. 656-672.

49. El-Sherbeny Nasser A. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods // Journal of King Saud University - Science. — 2010. — Vol. 22, no. 3. — Pp. 123 - 131.

50. Enomoto Hikoe, Oda Yoshiaki, Ota Katsuhiro. Pyramidal Tours with Stepbacks and the Asymmetric Traveling Salesman Problem // Discrete Appl. Math. — 1998. — oct. — Vol. 87, no. 1-3. — Pp. 57-65.

51. Feige Uriel, Singh Mohit. Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. — Vol. 4627. — 2007. — 01. — Pp. 104-118.

52. Fowler Robert J., Paterson Michael S., Tanimoto Steven L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. — 1981. — Vol. 12, no. 3. — Pp. 133-137.

53. Frieze Alan, Galbiati G., Maffioli F. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem // Networks. — 1982. — 03. — Vol. 12. — Pp. 23 - 39.

54. Frifita Sana, Masmoudi Malek. VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties // International Transactions in Operational Research. — 2020. — Vol. 27, no. 1. — Pp. 291-313.

55. Garey Michael R., Johnson David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York, NY, USA: W. H. Freeman & Co., 1979.

56. Gimadi E., Kurochkin A. The capacitated facility location problem with random input data // Journal of Mathematical Sciences. — 2014. — 10. — Vol. 188.

57. Gimadi E., Rykov Ivan. Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles // Proceedings of the Steklov Institute of Mathematics. — 2016. — 12.

— Vol. 295. — Pp. 57-67.

58. Gimadi E., Rykov Ivan. On the Asymptotic Optimality of a Solution of the Euclidean Problem of Covering a Graph by m Nonadjacent Cycles of Maximum Total Weight // Doclady Mathematics. — 2016. — 01. — Vol. 93.

— Pp. 117-120.

59. Gimadi E., Tsidulko Oxana. An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution // Journal of Applied and Industrial Mathematics. — 2017. — 07. — Vol. 11. — Pp. 354-361.

60. Gimadi E., Tsidulko Oxana. Asymptotically Optimal Algorithm for the Maximum m-Peripatetic Salesman Problem in a Normed Space: 12th International Conference, LION 12, Kalamata, Greece, June 10-15, 2018, Revised Selected Papers. — 2019. — 01. — Pp. 402-410.

61. Golden Bruce, Raghavan Saahitya, Wasil Edward. The Vehicle Routing Problem: Latest Advances and New Challenges. — 2008. — 01. — Vol. 43.

62. Gupta A., Krauthgamer R., Lee J. R. Bounded geometries, fractals, and low-distortion embeddings // 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. — 2003. — Pp. 534-543.

63. Gutin Gregory, Punnen Abraham P. The Traveling Salesman Problem and Its Variations. — Boston, MA: Springer US, 2007.

64. Haimovich M., Kan R., Stougie L. Analysis of heuristics for vehicle routing problems. — 1988. — 02.

65. Haimovich M., Rinnooy Kan A. H. G. Bounds and Heuristics for Capacitated Routing Problems // Mathematics of Operations Research. — 1985.

— Vol. 10, no. 4. — Pp. 527-542.

66. Hamaguchi Shin-ya, Katoh Naoki. A Capacitated Vehicle Routing Problem on a Tree // Algorithms and Computation / Ed. by Kyung-Yong Chwa, Oscar H. Ibarra. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. — Pp. 399-407.

67. Hassin R., Rubinstein S. On the complexity of the k-customer vehicle routing problem // Operations Research Letters. — 2010. — Vol. 33. — Pp. 7176.

68. He Qie, Irnich Stefan, Song Yongjia. Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs // Transportation Science. — 2019. — 08. — Vol. 53.

69. Held Michael, Karp Richard M. A Dynamic Programming Approach to Sequencing Problems // Proceedings of the 1961 16th ACM National Meeting.

— ACM '61. — New York, NY, USA: ACM, 1961. — Pp. 71.201-71.204.

70. Hochbaum Dorit. Heuristics for the fixed cost median problem // Mathematical Programming. — 1982. — 12. — Vol. 22. — Pp. 148-162.

71. Hokama Pedro, Miyazawa Flavio K., Xavier Eduardo C. A branch-and-cut approach for the vehicle routing problem with loading constraints // Expert Systems with Applications. — 2016. — Vol. 47. — Pp. 1-13.

72. Hollis B.L., Green P.J. Real-life vehicle routing with time windows for visual attractiveness and operational robustness // Asia-Pacific Journal of Operational Research. — 2012. — 08. — Vol. 29.

73. Hoorn Jelke Jeroen van. Dynamic programming for routing and scheduling: Optimizing sequences of decisions: Ph.D. thesis. — 2016. — Pp. 67-83.

74. Hore Samrat, Chatterjee Aditya, Dewanji Anup. Improving variable neighborhood search to solve the traveling salesman problem // Applied Soft Computing. — 2018. — Vol. 68. — Pp. 83-91.

75. A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-windows / Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Christian Prins // Comput. Oper. Res. - 2013. - Vol. 40, no. 1. - Pp. 475-489.

76. Improved branch-cut-and-price for capacitated vehicle routing / Diego Pecin, Artur Pessoa, Marcus Poggi, Eduardo Uchoa // Mathematical Programming Computation. — 2017. — Vol. 9, no. 1. — Pp. 61-100.

77. Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. — 3ed. edition. — MIT, 2009.

78. Kaabi Jihene, Harrath Youssef. Permutation rules and genetic algorithm to solve the traveling salesman problem // Arab Journal of Basic and Applied Sciences. — 2019. — Vol. 26, no. 1. — Pp. 283-291.

79. Karp Richard M. Reducibility among Combinatorial Problems // Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department / Ed. by Raymond E. Miller, James W. Thatcher, Jean D. Bohlinger. — Boston, MA: Springer US, 1972. — Pp. 85-103.

80. Khachai M.Yu., Neznakhina E.D. Approximability of the problem about a minimum-weight cycle cover of a graph // Doklady Mathematics. — 2015. — Vol. 91, no. 2. — Pp. 240-245.

81. Khachai M.Yu., Neznakhina E.D. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph // Proceedings of the Steklov Institute of Mathematics. — 2015. — Vol. 289, no. 1. — Pp. 111-125. https://doi.org/10.1134/S0081543815050107.

82. Khachai M.Y., Ogorodnikov Y.Y. Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows // Trudy instituta matematiki i mekhaniki UrO RAN. — 2018. — Vol. 24, no. 3. — Pp. 233-246.

83. 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. — Vol. 25, no. 4. — Pp. 235-248.

84. Khachai M. Yu., Dubinin R. D. Approximability of the Vehicle Routing Problem in finite-dimensional Euclidean spaces // Proceedings of the Steklov Institute of Mathematics. — 2017. — Vol. 297, no. 1. — Pp. 117-128.

85. Khachay Michael, Dubinin Roman. PTAS for the Euclidean Capacitated Vehicle Routing Problem in Rd // Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings / Ed. by et al. Kochetov. — Cham: Springer International Publishing, 2016. — Vol. 9869 of LNCS. — Pp. 193205.

86. Khachay Michael, Neznakhina Katherine. Approximability of the minimum-weight k-size cycle cover problem // Journal of Global Optimization. — 2016. — 09. — Vol. 66. — Pp. 65-82.

87. Khachay Michael, Neznakhina Katherine. Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension // IFAC-PapersOnLine. — 2016. — 08. — Vol. 49. — Pp. 6-10.

88. Khachay M., Ogorodnikov Y. Efficient PTAS for the Euclidean CVRP with Time Windows // Analysis of Images, Social Networks and Texts - 7th International Conference, AIST 2018. — Vol. 11179 of LNCS. — Cham: Springer International Publishing, 2018. — Pp. 318-328. https://doi.org/10.1007/978-3-030-11027-7_30.

89. Khachay M., Ogorodnikov Y. Approximation scheme for the Capacitated Vehicle Routing Problem with Time Windows and non-uniform demand // Mathematical Optimization Theory and Operations Research -18th International conference (MOTOR 2019). Proceedings. — Vol. 11548 of LNCS. — Springer International Publishing, 2019. — Pp. 309-327. https://doi.org/10.1007/978-3-030-22629-9_22.

90. Khachay Michael, Ogorodnikov Yuri. Efficient PTAS for the euclidean capacitated vehicle routing problem with non-uniform non-splittable demand // Analysis of Images, Social Networks and Texts - 8th International

Conference, AIST 2019, Revised Selected Papers / edited byWil M.P. van der Aalst, Vladimir Batagelj, Dmitry I. Ignatov at al. — Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — Germany: Springer Verlag, 2019. — jan. — Pp. 388-398. — 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019 ; Conference date: 17-07-2019 Through 19-07-2019.

91. Khachay M., Ogorodnikov Y. Improved Polynomial Time Approximation Scheme for Capacitated Vehicle Routing Problem with Time Windows // Optimization and Applications. OPTIMA 2018. — Vol. 974 of Communications in Computer and Information Science. — Cham: Springer International Publishing, 2019. — Pp. 155-169. https://doi.org/10.1007/978-3-030-10934-9_12.

92. Khachay Michael, Ogorodnikov Yuri. Towards an efficient approximability for the Euclidean Capacitated Vehicle Routing Problem with Time Windows and multiple depots // Ifac papersonline. — 2019. — Vol. 52, no. 13. — Pp. 2644-2649. — 9th IFAC/IFIP/IFORS/IISE/INFORMS Conference on Manufacturing Modelling, Management and Control (IFAC MIM) ; Conference date: 28-08-2019 Through 30-08-2019.

93. Khachay M. Yu, Ogorodnikov Yu Yu. Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dimension // Doklady Mathematics. — 2020. — jul. — Vol. 102, no. 1. — Pp. 324-329.

94. Khachay Michael, Ogorodnikov Yuri. PTAS for the Euclidean Capacitated Vehicle Routing Problem with Time Windows // Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers / edited byNikolaos F. Matsatsinis, Yannis Marinakis, Panos Parda-los. — Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — Germany: Springer Verlag, 2020. — jan. — Pp. 224-230. — 13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019.

95. Khachay Michael, Ogorodnikov Yuri. Polynomial Capacity Guarantees PTAS for the Euclidean Capacitated Vehicle Routing Problem Even for Non-uniform Non-splittable Demand // Optimization and Applications

- 10th International Conference, OPTIMA 2019, Revised Selected Papers / edited byMilojica JaCimoviC, Michael Khachay, Vlasta Malkova, Mikhail Posypkin. — Communications in Computer and Information Science. — Germany: Springer, 2020. — jan. — Pp. 415-426. — 10th International Conference on Optimization and Applications, OPTIMA 2019 ; Conference date: 30-09-2019 Through 04-10-2019.

96. Khachay Michael, Ogorodnikov Yuri. Qptas for the cvrp with a moderate number of routes in a metric space of any fixed doubling dimension // Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers / edited byIlias S. Kotsireas, Panos M. Pardalos. — Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — Germany: Springer, 2020. — jan. — Pp. 27-32. — 14th International Conference on Learning and Intelligent Optimization, LION 2020 ; Conference date: 24-05-2020 Through 28-05-2020.

97. Khachay M., Ogorodnikov Y., Khachay D. An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension (accepted) // Mathematical Optimization Theory and Operations Research - 19th International conference (MOTOR 2020). Proceedings. — Vol. 12095 of LNCS. — Springer International Publishing, 2020.

98. Khachay Michael, Ogorodnikov Yuri, Khachay Daniel. Efficient approximation of the metric CVRP in spaces of fixed doubling dimension // Journal of Global Optimization. — 2021. — 01.

99. Khachay Michael, Zaytseva Helen. Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem // Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings / Ed. by Zaixin Lu, Donghyun Kim, Weili Wu et al. — Cham: Springer International Publishing, 2015. — Vol. 9486 of LNCS. — Pp. 178-190.

100. Kumar S., Panneerselvam R. A Survey on the Vehicle Routing Problem and Its Variants // Intelligent Information Management. — 2012. — Vol. 4. — Pp. 66-74.

101. Laporte Gilbert. Fifty Years of Vehicle Routing // Transportation Science.

— 2009. — Vol. 43. — Pp. 408-416.

102. Laporte Gilbert, Ropke Stefan, Vidal Thibaut. Chapter 4: Heuristics for the Vehicle Routing Problem. — 2014. — 11. — Pp. 87-116.

103. Li Shi. A 1.488 approximation algorithm for the uncapacitated facility location problem // Information and Computation. — 2013. — Vol. 222. — Pp. 45 - 58. — 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).

104. Menger K. Das Botenproblem // Ergebnisse eines Mathematischen Kolloquiums 2. — 1932. — 01. — Vol. 2. — Pp. 11-12.

105. Mitchell Joseph S.B. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems // SIAM Journal on Computing. — 1999. — Vol. 28, no. 4. — Pp. 1298-1309. https://doi.org/10.1137/S0097539796309764.

106. Model of megalopolises in the tool path optimisation for CNC plate cutting machines / A.G. Chentsov, P.A. Chentsov, A.A. Petunin, A.N. Sesekin // International Journal of Production Research. — 2018. — Vol. 56, no. 14.

— Pp. 4819-4830. — cited By 13.

107. Nalepa Jakub, Blocho Miroslaw. Adaptive memetic algorithm for minimizing distance in the Vehicle Routing Problem with Time Windows // Soft Computing. — 2016. — Vol. 20, no. 6. — Pp. 2309-2327.

108. 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 Computation (CEC). — 2017. — Pp. 2480-2487.

109. Oda Yoshiaki. An asymmetric analogue of van der Veen conditions and the traveling salesman problem // Discrete Applied Mathematics. — 2001. — Vol. 109, no. 3. — Pp. 279 - 292.

110. Oda Yoshiaki, Ota Katsuhiro. Algorithmic Aspects of Pyramidal Tours with Restricted Jump-Backs // Interdisciplinary Information Sciences. — 2001.

— Vol. 7, no. 1. — Pp. 123-133.

111. Optimization of Transportation Routing Problem for Fresh Food by Improved Ant Colony Algorithm Based on Tabu Search / Chen, Gui, Ding, Zhou // Sustainability. — 2019. — Vol. 11.

112. Ozbaygin Gizem, Karasan Oya, Yaman Hande. New exact solution approaches for the split delivery vehicle routing problem // EURO Journal on Computational Optimization. — 2017. — 09. — Vol. 6.

113. A PTAS for the multiple depot vehicle routing problem / S. Cardon, S. Dom-mers, C. Eksin et al. SPOR-Report: reports in statistics, probability and operations research. — Technische Universiteit Eindhoven, 2008.

114. Papadimitriou Christos. Euclidean TSP is NP-complete // Theoret. Com-put. Sci. — 1977. — Vol. 4. — Pp. 237-244.

115. Papadimitriou Christos H., Yannakakis Mihalis. The Traveling Salesman Problem with Distances One and Two // Mathematics of Operations Research. — 1993. — Vol. 18, no. 1. — Pp. 1-11.

116. Pessoa Artur Alves, Sadykov Ruslan, Uchoa Eduardo. Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems // European Journal of Operational Research. — 2018. — Vol. 270, no. 2. — Pp. 530-543.

117. Polat Olcay. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups // Computers & Operations Research. — 2017. — Vol. 85. — Pp. 71-86.

118. Rao Satish, Smith Warren. Approximating Geometrical Graphs Via Spanners and Banyans // Conference Proceedings of the Annual ACM Symposium on Theory of Computing. — 1998. — 06.

119. Reinforcement Learning for Solving the Vehicle Routing Problem / Moham-madreza Nazari, Afshin Oroojlooy, Martin Takac, Lawrence V. Snyder // Proceedings of the 32nd International Conference on Neural Information Processing Systems. — NIPS'18. — Red Hook, NY, USA: Curran Associates Inc., 2018. — P. 9861-9871.

120. Sahni S., Gonzales T. P-complete approximation problems // Journal of the ACM. — 1976. — Vol. 23. — Pp. 555-565.

121. Simanchev R. Yu., Urazova I. V., Kochetov Yu. A. Polyhedral Attack on the Graph Approximation Problem // Mathematical Optimization Theory and Operations Research. — 2019. — Pp. 255-265.

122. Smid Michiel. On some combinatorial problems in metricspaces of bounded doubling dimension. — 2010. — Accessed Dec. 6, 2020.

https://people.scs.carleton.ca/ michiel/mst-ann-doubling.pdf.

123. Song Liang, Huang Hejiao, Du Hongwei. Approximation schemes for Euclidean vehicle routing problems with time windows // Journal of Combinatorial Optimization. — 2016. — Vol. 32, no. 4. — Pp. 1217-1231.

124. Stougie L., Haimovich M., Rinnooy Kan A.H.G. Analysis of heuristics for vehicle routing problems // Vehicle routing : methods and studies / edited byB.L. Golden, A.A. Assad. — Studies in Management Science and Systems; 16. North-Holland, 1988. — Pp. 47-61. — 0653.90031.

125. Su-Ping Yu, Wei-Wei Mao. An Improved Ant Colony Optimization for VRP with Time Windows // International Journal of Signal Processing, Image Processing and Pattern Recognition. — 2016. — 10. — Vol. 9. — Pp. 327-334.

126. Svensson Ola, Tarnawski Jakub, Vegh Laszlo. Constant factor approximation for ATSP with two edge weights // Mathematical Programming. — 2017. — 09. — Vol. 172. — Pp. 1-27.

127. A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups / Meng Qiu, Zhuo Fu, Richard Eglese, Qiong Tang // Computers & Operations Research. — 2018. — Vol. 100. — Pp. 102-116.

128. Talwar Kunal. Bypassing the Embedding: Algorithms for Low Dimensional Metrics // Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. — STOC '04. — New York, NY, USA: Association for Computing Machinery, 2004. — P. 281-290.

129. Toth Paolo, Vigo Daniele. Vehicle Routing: Problems, Methods, and Applications, Second Edition. MOS-Siam Series on Optimization. — 2 edition. — SIAM, 2014. — Pp. 53-85.

130. Traub Vera, Vygen Jens. An improved approximation algorithm for ATSP.

— 2019. — 12.

131. Traub Vera, Vygen Jens. An improved approximation algorithm for ATSP.

— 2020. — 06. — Pp. 1-13.

132. Traveling Salesman Problem Methods of Solution Survey / Warif Yahia, Ghassan Arif, Mohammed Al-Neama, Ali Hasan Ali // International Journal of Psychosocial Rehabilitation. — 2020. — 05. — Vol. 24. — Pp. 85658581.

133. Trevisan Luca. When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree // SIAM Journal on Computing. — 1999. — 03. — Vol. 30.

134. Ulyanov M., Fomichev M. Comparative Analysis of the Branch and Bound Method Combinations with Metaheuristic Algorithms for Solving the Asymmetric Traveling Salesman Problem // INFORMACIONNYE TEHNOLOGII. - 2019. - 10. - Vol. 25. - Pp. 590-595.

135. Van Hoorn Jelke. A note on the worst case complexity for the capacitated vehicle routing problem. - 2020. - 12.

136. Vehicle Routing Problem: Past and Future / Emrah Demir, Katy Huckle, Aris Syntetos et al. // Contemporary Operations and Logistics: Achieving Excellence in Turbulent Times / Ed. by Peter Wells. — Cham: Springer International Publishing, 2019. — Pp. 97-117.

137. Vehicle Routing Problem with Time Windows / Brian Kallehauge, Jes-per Larsen, Oli Madsen, Marius Solomon. — 2006. — 03. — Pp. 67-98.

138. Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey / Rainer E. Burkard, Vladimir G. Deineko, Rene van Dal et al. // SIAM Rev. — 1998. — sep. — Vol. 40, no. 3. — Pp. 496-546.

139. Woeginger Gerhard J. Exact Algorithms for NP-Hard Problems: A Survey // Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5-9, 2001 Revised Papers / Ed. by Michael Jünger, Gerhard Reinelt, Giovanni Rinaldi. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. — Pp. 185-207.

140. A split delivery vehicle routing problem / Hiroaki Mohri, Mikio Kubo, Masao Mori, Yasutoshi Yajima // Journal of the Operations Research Society of Japan. — 1996. — 01. — Vol. 39.

141. Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху / Э.Х. Гимади, А.М. Истомин, И.А. Рыков, О.Ю. Цидулко // Тр. ИММ УрО РАН. — 2014. — 01. — Vol. 20. — Pp. 88-98.

142. Гимади Э.Х., Перепелица В.А. Асимптотический подход к решению задачи коммивояжера // Управляемые системы. — 1974. — 01. — Pp. 3545.

143. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. — Издательство УМЦ УПИ, 2016. — 12. — P. 220.

144. Гимади Э.Х., Цидулко О.Ю. О некоторых эффективно разрешимых классах сетевой задачи размещения с ограничениями на пропускные способности коммуникаций // Тр. ИММ УрО РАН. — 2020. — 01. — Vol. 26. — Pp. 108-124.

145. Жукова Г.Н., Ульянов М.В., Фомичев М.И. Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности // Автоматика и телемеханика. — 2019. — Vol. 11. — Pp. 155-172.

146. Сердюков А.И. О некоторых экстремальных обходах в графах // Управляемые системы. — 1978. — Vol. 17. — Pp. 76 — 79.

147. Симанчев Р.Ю., Соловьева П.В., Уразова И.В. Аффинная оболочка многогранника расписаний обслуживания идентичных требований параллельными приборами // Дискретный анализ и исследование операций. — 2021. — Т. 28, № 1. — С. 48-67.