КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 22-21-00672

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

Руководитель Хачай Михаил Юрьевич, Доктор физико-математических наук

Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт математики и механики им.Н.Н.Красовского Уральского отделения Российской академии наук , Свердловская обл

Конкурс №64 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-203 - Теория оптимизации и исследование операций

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

Код ГРНТИ27.47.19

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Объектом исследования данного проекта является фундаментальная проблема проектирования, обоснования и численного тестирования полиномиальных алгоритмов с теоретическими оценками точности и трудоемкости для труднорешаемых экстремальных задач оптимальной маршрутизации, являющихся обобщениями классических задач коммивояжера (TSP), маршрутизации транспорта (VRP) и оптимального ориентирования (OP). Основное внимание предполагается уделить вопросам обоснования аппроксимируемости асимметричных постановок исследуемых задач в классе полиномиальных приближенных алгоритмов с фиксированным фактором аппроксимации. Абсолютное большинство известных результатов в области вычислительной сложности и аппроксимируемости в классе алгоритмов с оценками для исследуемых комбинаторных задач укладываются в одну общую схему. За редким исключением все перечисленные задачи: - NP-трудны в сильном смысле, как в общем случае, так в чрезвычайно специфических постановках, например, на евклидовой плоскости; - вообще говоря не аппроксимируемы, т.к. построение полиномиальных приближенных алгоритмов для общих постановок этих задач со сколько-нибудь приемлемой точностью влечет равенство классов P и NP; - в метрической постановке задачи APX-полны; - обладают полиномиальными или квазиполиномиальными приближенными схемами в метрических пространствах произвольной фиксированной размерности удвоения (в том числе, в конечномерных числовых пространствах). Так или иначе, все перечисленные выше алгоритмические результаты, включая классические алгоритмы Кристофидеса-Сердюкова и Хаймовича-Ринной Кана, а также активно развиваемый подход Ароры-Бартала к проектированию полиномиальных и квазиполиномиальных аппроксимационных схем, существенно опираются на метрические свойства исследуемых постановок. До последнего момента в тех редких случаях, когда существование приближенных алгоритмов с полиномиальной трудоемкостью для асимметричных постановок маршрутных задач и удавалось обосновать, речь шла в лучшем случае об алгоритмах с логарифмическими оценками факторов аппроксимации. Как следствие, эти результаты могли представлять разве что теоретический интерес, в то время как численный анализ практических примеров данных задач, важных с точки зрения актуальных приложений, оставался прерогативой эвристических подходов. В этом смысле недавние пионерские результаты [O.Svensson, J.Tarnawski, I.Vegh (2018)] и [V.Traub, J.Vygen (2020)], представленные на конференции STOC, в которых впервые обоснована полиномиальная аппроксимируемость асимметричной задачи коммивояжера (ATSP) с неравенством треугольника в классе алгоритмов с фиксированными оценками точности, представляются бесспорным прорывом, открывающим возможность существенного продвижения в области проектирования алгоритмов с оценками для асимметричных комбинаторных задач. Цель настоящего проекта состоит в верификации гипотезы об аппроксимируемости в классе полиномиальных алгоритмов с константными оценками точности для более широкого класса маршрутных задач, включающих асимметричные постановки с неравенством треугольника: - задачи об оптимальной маршрутизации транспортных средств (VRP) при дополнительных ограничениях на их грузоподъемность, временные промежутки обслуживания, множественность складов и неоднородность потребительского спроса; - обобщенной задачи коммивояжера (GTSP); - задачи коммивояжера с призами (PCTSP); - задачи о кратчайших путях с заданными множествами обязательных для посещения вершин (SSPP-MPN) и задачи ориентирования (OP).

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---