name: Эффективные алгоритмы с гарантированными оценками точности для задачи маршрутизации транспорта ограниченной грузоподъемности
keyword_list: квазиполиномиальная приближенная схема полиномиальная приближенная схема метрические пространства произвольной фиксированной размерности удвоения алгоритмы с гарантироваыми оценками точности задача маршрутизации транспорта ограниченной грузоподъемности NP-трудная задача комбинаторная оптимизация
abstract: Диссертационная работа «Эффективные алгоритмы с гарантированными оценками точности для задачи маршрутизации транспорта ограниченной грузоподъемности» посвящена исследованию аппроксимации метрических постановок задачи маршрутизации транспорта ограниченной грузоподъемности (CVRP), известной NP-трудной задачи комбинаторной оптимизации. Содержательная постановка CVRP может быть задана в виде множества потребителей |X|=n, обладающих спросом на некоторую продукцию, хранящуюся в выделенной точке-складе y. Также в точке y базируются транспортные средства идентичный ограниченной грузоподъемности q, удовлетворяющие потребительский спрос. Задача состоит в построении множества циклических маршрутов, начинающихся и заканчивающихся в y, удовлетворяющих весь совокупный потребительский спрос, не превышающих грузоподъемность q и обладающих минимальными транспортными издержками. Как и многие NP-трудные задачи комбинаторной оптимизации, алгоритмический анализ CVRP можно представить в виде трех направлений. Методы первой группы основаны на сведении исходной постановке к подходящей постановке целочисленного или смешанного программирования с последущим применением метода ветвей и границ. К сожалению, ввиду NP-трудности исходной постановки, данные методы мыло подходят для решения практических примеров, имеющих большую размерность исходных данных. Основу второго направления составляет широкий спектр эвристик и метаэвристик, демонстрирующих прекрасную производительность при решении постановок, пришедших из различных областей индустрии. Однако, методы данной группы не имеют гарантированных оценок точности и трудоемкости. Наконец, третьей группой являются алгоритмы с гарантированными оценками точности, сопоставляющие произвольной постановке решение, отличающееся от оптимального не более чем в заданное количество раз. В диссертационной работе рассматриваются алгоритмы именно третьей группы.  
  По-видимому, задача CVRP впервые была сформулирована в работе Дж. Данцига и Г. Рамсера в 1959 году. В 1977 году Х. Пападимитриу показал, что задача CVRP является NP-трудной в сильном смысле даже для случая евклидовой плоскости. В 1985 году М. Хаймовичем и А. Ринной Каном была построена первая полиномиальная приближенная схема (PTAS) для постановок CVRP, заданных на евклидовой плоскости для дипазона значений грузоподъемности, оцениваемого как q=o(log log n). Впоследствии данная схема была улучшена в работах Т.Асано и А.Адамашек для более широких значений q. С другой стороны,развивая классический подход С.Ароры, позволяющий построить приближенное решение задачи коммивояжера (TSP), А.Дас и К.Матье была построена схема, обладающая квазиполиномиальной трудоемкостью (QPTAS) при произвольно растущем значении параметра q. Данный результат является наиболее общим для постановок CVRP, заданных в конечномерных евклидовых пространствах. 
  Данные результаты являются фундаментальными и были обобщены на некоторые расширенные постановки CVRP. В частности, были получены PTAS для постановок CVRP с несколькими складами, QPTAS для CVRP с временными промежутками обслуживания (CVRPTW), эффективная приближенная схема (EPTAS) для постановок CVRP в конечномерных евклидовых пространствах произвольной размерности. К сожалению, из результатов М. Хаймовича и А. Ринной Кана, а также Т. Асано следует, что CVRP является APX-полной, то есть, с одной стороны, для нее существует полиномиальный алгоритм с константной точностью. С другой стороны, при произвольной метрике для задачи CVRP не может быть построена PTAS при гипотезе несовпадения классов P  и NP. Тем не менее, по-прежнему вызывает интерес  вопрос существования пространств, существенно шире конечномерных евклидовых, в которых аппроксимация CVRP возможна. Недавние исследования показали, что для родственной задачи TSP существуют QPTAS К.Талвара и PTAS Я.Бартала в так называемых метрических пространствах произвольной фиксированной размерности удвоения. Данные резуьтаты оказались прорывными, и в последнее время появился ряд публикаций, касающихся аппроксимации ряда комбинаторных задач в подобных пространствах. Однако про аппроксимацию CVRP подобных результатов до недавнего времени ничего известно не было.
  С другой стороны, также ничего не было известно также в сфере эффективной аппроксимируемости некоторых обобщенных геометрических постановок CVRP.
  Вышеуказанные аспекты обуславливают мотивацию исследований, и формируют цели диссертации, которые заключаются в следующем:
  1. Исследование аппроксимации задачи CVRP в метрических пространствах произвольной фисированной размерности удвоения.
  2. Построение полиномиально приближенных и эффективно полиномиально приближенных схем для геометрических постановок CVRP, стесненных дополнительными ограничениями на временные промежутки обслуживания и неоднородность и делимость клиентского спроса.
  Основные результаты диссертации заключаются в следующем.
  1. Для постановок CVRP, заданных в метрических пространствах удвоения была установлена их аппроксимируемость. В частности:
  - была показано, что схема Хаймовича-Ринной Кана сохраняет свои аппроксимативные свойства при тех же ограничениях на грузоподъемность, при которых она была сформулирована для постановок CVRP на евклидовой плоскости;
  - развивая идеи К. Талвара и Я. Бартала, была предложена квазиполиномиальная приближенная схема при быстрорастущем значении параметра грузоподъемности q;
  - основываясь на идеях А. Дас и К. Матье, была получена QPTAS при медленнорастущем значении грузоподъемности.
  2. Для постановок CVRP, заданных на евклидовой плоскости, были получены следующие результаты:
  - впервые получены полиномиальная и эффективная полиномиальная приближенные схемы для постановок CVRP, стесненных дополнительными ограничениями на непересекающиеся временные промежутки обслуживания потребителей;
  - впервые получены полиномиальная приближенная и эффективная полиномиальная приближенная схемы для постановок CVRP, стесненных как дополнительным ограничением на временные промежутки обслуживания клиентов, так и на неоднородность потребительского спроса, который можно удовлетворять разными маршрутами.
  Результаты диссертации опубликованы в 5 статьях в журналах из перечня ВАК (среди которых одна статья из журнала первого квартиля), и в 8 трудах, индексированных базами данных Web of Science и/или Scopus.
chairman_dissertation_council.name: Виталий
chairman_dissertation_council.surname: Бердышев
chairman_dissertation_council.patronymic: Иванович
chairman_dissertation_council.position: Главный научный сотрудник
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Академик
chairman_dissertation_council.wos_research_id: Q-1761-2017
chairman_dissertation_council.scopus_author_id: 55980665600
chairman_dissertation_council.rinc_id: 3668
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Николай
organization_supervisor.surname: Лукоянов
organization_supervisor.patronymic: Юрьевич
organization_supervisor.position: Директор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.47.19
rubrics.name: Исследование операций
rubrics.code: 27.45.15
rubrics.name: Общая теория комбинаторного анализа
rubrics.code: 27.41.41
rubrics.name: Алгоритмы решения задач вычислительной и дискретной математики
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Хачай М.Ю.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Симанчев Р.Ю.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
opponents.fio: Ульянов М.В.
opponents.scientific_degree: Доктор технических наук
opponents.speciality_code: Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
opponents.responsible_type: Оппонент
protection_organization.short_name: ИММ УРО РАН
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.Н. КРАСОВСКОГО УРАЛЬСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК
protection_organization.ogrn: 1026604965177
protection_organization.supervisor_name: НИКОЛАЙ
protection_organization.supervisor_surname: ЛУКОЯНОВ
protection_organization.supervisor_patronymic: ЮРЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: ИММ УРО РАН
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.Н. КРАСОВСКОГО УРАЛЬСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК
author_organization.ogrn: 1026604965177
author_organization.supervisor_name: НИКОЛАЙ
author_organization.supervisor_surname: ЛУКОЯНОВ
author_organization.supervisor_patronymic: ЮРЬЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения