Аннотация результатов, полученных в 2022 году
В 2022 г. исследования по проекту были ориентированы на развитие революционных результатов, полученных О.Свенссоном и В.Трауб для асимметричной задачи коммивояжера (ATSP) с неравенством треугольника, на асимметричные постановки близких маршрутных задач комбинаторной оптимизации с целью построения для них первых приближенных полиномиальных алгоритмов с константными теоретическими оценками точности (факторами аппроксимации). При этом основное внимание в первую очередь уделялось тем случаям, когда аппроксимируемость в данном классе алгоритмов удавалось обосновать, опираясь на полиномиальное сведение исследуемой постановки к вспомогательной постановке задачи ATSP (с сохранением значения целевой функции) и поиск приближенного решения последней методом Свенссона-Трауб. Полученные результаты удобно представить в разрезе исследованных комбинаторных задач. Как и для ATSP, полагаем, что целевая функция каждой из них удовлетворяет неравенству треугольника. Задача о штейнеровском цикле (Steiner Cycle Problem, SCP): в реберно-взвешенном орграфе с заданным подмножеством T терминальных вершин требуется построить замкнутый (необязательно простой) маршрут минимального веса, посещающий каждую терминальную вершину. Аппроксимация данной задачи получается полиномиальным сведением с сохранением значения целевой функции к подходящей задаче ATSP на подграфе метрического замыкания исходного графа, индуцированном подмножеством T. Задача о сельском почтальоне (Rural Postman Problem, SCP): в реберно-взвешенном орграфе с заданным подмножеством R терминальных дуг требуется построить замкнутый (необязательно простой) маршрут минимального веса, проходящий по каждой терминальной дуге. Аппроксимация данной задачи может быть получена полиномиальным сведением к вспомогательной постановке задачи SCP. Постановка асимметричной задачи маршрутизации с ограничением на грузоподъемность транспортных средств и неоднородным неделимым потребительским спросом (Capacitated Vehicle Routing Problem with Unsplittable Customer Demand, CVRP-UCD) задается взвешенным орграфом, множество вершин которого наряду с вершинами - потребителями содержит выделенную вершину — депо, верхней границей D грузоподъёмности транспортных средств и двумя весовыми функциями. Первая функция задает потребительский спрос каждой вершины — потребителя, в то время как вторая сопоставляет каждой дуге соответствующую величину транспортных издержек. Задача состоит в построении семейства допустимых (с точки зрения грузоподъемности) маршрутов минимальной суммарной стоимости, удовлетворяющих совокупный потребительский спрос. Предлагаемый алгоритм опирается на полиномиальное сведение исходной задачи к подходящей постановке задачи SCP, множество терминальных вершин которой включает депо и всех потребителей с положительным объемом спроса. Далее, найденный на первом этапе приближенный штейнеровский цикл особым образом разбивается на маршруты, удовлетворяющие ограничению на грузоподъемность. Опираясь на известную лемму Холла для двудольных графов, устанавливаем изоморфное вложение построенного множества маршрутов во множество маршрутов произвольного оптимального решения исходной задачи. Как следствие, получаем верхнюю оценку точности, заявленную в Теореме 2 (п. 1.4) Аппроксимируемость задачи реберной маршрутизации на графах смешанного типа (Capacitated Arc Routing Problem, CARP) получается полиномиальным сведением исходной задачи к вспомогательной постановке задачи CVRP-UCD. В текущем году нами обоснована аппроксимируемость «упрощенной» версии известной задачи коммивояжера с призами (Prize-Collecting Traveling Salesman Problem, PCTSP), отличающейся от общей постановки задачи отсутствием рюкзачного ограничения. Условие этой постановки задается вершинно- и реберно-взвешенным орграфом, каждой вершине которого сопоставляется «штраф» за ее непосещение, а каждой дуге — величина соответствующей транспортной издержки. Требуется построить циклический маршрут, минимизирующий суммарные издержки, связанные с перемещением по дугам и пропуском вершин. Как показано в известной работе Bienstock, Goemans, Simchi-Levi, and Williamson (Mat. Prog., 1993), метрическая версия задачи обладает полиномиальным 5/2-приближенным алгоритмом, использующим в качестве «черного ящика» классический алгоритм Кристофидеса-Сердюкова для метрической задачи коммивояжера. В свою очередь, для рассматриваемой в данной работе асимметричной версии задачи до последнего момента были известны лишь алгоритмы с логарифмическими оценками точности. Опираясь на результаты Свенссона и Трауб, нами предложен первый приближенный алгоритм для данной постановки с константной оценкой точности 23+\epsilon (для произвольного значения \epsilon>0). Постановка обобщенной задачи коммивояжера (Generalized Traveling Salesman Problem, GTSP) задается реберно-взвешенным орграфом и заданным разбиением множества его вершин на кластеры. Как и в классической задаче коммивояжера, веса, задаваемые на дугах графа, имеют смысл транспортных издержек. Цель состоит в построении замкнутого маршрута, посещающего каждый кластер в точности в единственной вершине. Известно, что задача принадлежит классу FTP, будучи параметризованной числом кластеров k. Более того, адаптация классической схемы динамического программирования Хелда-Карпа является полиномиальным точным алгоритмом для общей постановки задачи всякий раз, когда k=O(log n). В 2022 г. нами обоснована аппроксимируемость асимметричной версии задачи в классе полиномиальных приближенных алгоритмов с константной оценкой точности при быстро растущем числе кластеров: k = n - O(log n). Наряду с описанными выше постановками асимметричных задач оптимальной маршрутизации, нами начато исследование задач, аппроксимируемость которых в классе алгоритмов с константными оценками точности не удается обосновать путем сведения к задаче ATSP. Семейство таких задач включает, например, общую постановку задачи PCATSP (с дополнительным «рюкзачным» ограничением), постановку обобщенной задачи коммивояжера при произвольном соотношении числа вершин и кластеров, задачу VRP с временными промежутками обслуживания и т. п. Для построения искомых полиномиальных алгоритмов для этих задач требуется обобщение самого подхода Свенссона-Трауб на новые классы MILP-моделей. В текущем году нами получены предварительные результаты в этом направлении, в области обобщения понятия сильно ламинарных постановок и хребтов (back-bones) для задачи GTSP. Основные результаты 2022 г. могут быть кратко резюмированы в следующей теореме. Tеорема. Для произвольного \alpha>=1 существование \alpha-приближенного алгоритма для задачи ATSP с неравенством треугольника влечет: 1) полиномиальную аппроксимируемость задач SCP, RPP и GTSP (при дополнительном ограничении на число кластеров n - O(log n)) с точностью \alpha; 2) существование полиномиального приближенного алгоритма для задач CVRP-UCD и CARP с фактором аппроксимации 3\alpha + 2. 3) полиномиальную аппроксимируемость упрощенной задачи PCATSP с гарантированной точностью \alpha + 1. Следствие. Для произвольного \epsilon>0 нами обосновано существование полиномиальных приближенных алгоритмов с точностью 22+\epsilon для задач SCP, RPP и GTSP, 23+\epsilon для упрощенной задачи PCATSP и 68+3\epsilon - для задач CVRP-UCD и CARP.

Аннотация результатов, полученных в 2023 году
Тематика исследований данного проекта была связана с проектированием и анализом приближенных алгоритмов для асимметричных маршрутных задач комбинаторной оптимизации. Предложенные в 2022 г. алгоритмы базировались - на эффективном сведении постановок исследуемых задач к одной или нескольким постановкам асимметричной задачи коммивояжера (ATSP) с метрической функцией транспортных издержек, - последующем применении для аппроксимации индуцированных постановок задачи ATSP недавно обоснованного (22+\varepsilon)-приближенного алгоритма Свенссона-Трауб. 1. Продолжая исследования в этом направлении, в 2023 г. нами изучена аппроксимируемость общей постановки классической задачи маршрутизации транспортных средств (Capacitated Vehicle Routing Problem, CVRP) с неравенством треугольника. Показано, что комбинация адаптированной версии известного алгоритма Хаймовича — Ринной Кана и произвольного \alpha-приближенного алгоритма для ATSP порождает приближенный алгоритм для CVRP с фактором аппроксимации \alpha + 2 в общем случае и \alpha + 1 при условии строго подлинейного роста грузоподъемности транспортных средств D по отношению к числу n вершин заданного графа. Таким образом, показано, что комбинация известного алгоритма итеративного разбиения маршрута (Iterated Tour Partition, ITP) Хаймовича и Ринной Кана и алгоритма Свенссона-Трауб для ATSP индуцирует приближенный алгоритм с фактором аппроксимации 24 + \varepsilon (23 + \varepsilon при D=o(n)) для классической задачи CVRP. 2. Одновременно были выявлены задачи маршрутизации, аппроксимируемость которых в классе полиномиальных алгоритмов с константными оценками точности путем сведения к задаче коммивояжера обосновать не удается (по крайней мере, на данный момент). Для алгоритмического анализа этих задач нами проведено более глубокое обобщение аппроксимационного фреймворка Свенссона и Трауб: - введены новые понятия сильно ламинарной постановки задачи и S-хребта, обобщающие используемые в работах (Svensson, Tarnawski, Vegh - 2020) и (Traub, Vygen - 2022) на случай не обязательно связных ориентированных графов; - обоснованы достаточные условия существования приближенных решений задачи о покрытии подмаршрутами (Subtour Cover Problem, SCP) с заданными гарантиями точности; - расширены достаточные условия существования (\kappa, \eta)-алгоритма Свенссона, обеспечивающего достройку заготовки маршрута (хребта) до допустимого решения вспомогательной задачи коммивояжера; - обоснована расширенная версия (\kappa, \eta)-алгоритма, обеспечивающая достройку S-хребта до приближенного решения задачи о цикловом покрытии минимального веса. Полученные теоретические результаты легли в основу первых приближенных алгоритмов с константными факторами аппроксимации для задачи о покрытии графа минимального веса семейством циклов ограниченной мощности (Minimum-cost k-Size Cycle Cover Problem, Min-k-SCCP). Для произвольных фиксированных k>1 и \varepsilon>0 построены полиномиальные приближенные алгоритмы с константными факторами аппроксимации max{22+\varepsilon, 4 + k} и 24 + \varepsilion соответственно. 3. Отдельное внимание в 2023 г. было уделено оценке применимости асимметричных задач маршрутизации для решения прикладных задач исследования операций. Одно из таких актуальных приложений связано с проектированием устойчивых к сбоям производственных процессов и цепей поставок. Традиционный подход к анализу таких систем связан с привлечением стохастических моделей, характеризующих выбор оптимального сценария поведения из заданного (как правило конечного) семейства возможных. Несмотря на ряд преимуществ, применение данного подхода существенно затрудняется в случае возникновения неполадок неизвестной природы, ставящих под угрозу работоспособность всей моделируемой системы. Нами введена в рассмотрение минимаксная задача построения отказоустойчивых планов производства (Reliable Production Process Design Problem, RPPDP), цель которой состоит в обеспечении экономичного бесперебойного функционирования распределенной производственно-транспортной системы. С теоретической точки зрения введенная задача представляется близкой к классической задаче о гомеоморфном вложении графа (Subgraph Homeomorphism Problem, SHP), а также задачам, исследованным в рамках данного проекта в 2022 г. Постановка задачи RPPDP задается упорядоченной тройкой (G, П, k). Здесь G — реберно-взвешенный ориентированный граф, множество вершин которого содержит: - выделенные вершины, моделирующие начало и завершение каждого производственного плана; - однородные пункты производства, объединяемые в попарно дизъюнктные кластеры по принципу выполнения конкретной производственной операции; - транспортные хабы, характеризуемые стоимостью «открытия» и пропускной способностью. Ациклический орграф П определяет частичный порядок на множестве производственных кластеров. Задача состоит в построении семейства минимаксной стоимости, состоящего из k попарно вершинно-непересекающихся производственных планов - гомеоморфных вложений графа П в орграф G. Показано, что задача RPPDP NP-трудна в сильном смысле и сохраняет труднорешаемость в важных для приложений частных случаях. Предложены: модель целочисленного линейного программирования (MILP-модель), эвристика адаптивного поиска в больших окрестностях (Adaptive Large Neighborhood Search, ALNS) и опирающийся на них алгоритм ветвей и границ. Высокая релаксационная способность модели и эффективность реализованного метода ветвления обоснованы результатами численных экспериментов, проведенных на предложенной исполнителями проекта публичной библиотеке тестовых постановок, развивающих известную библиотеку PCGTSPLIB. Предложенная библиотека доступна по адресу https://github.com/yogorodnikov/RPPDP-instances.