АППРОКСИМИРУЕМОСТЬ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОГРАНИЧЕННЫМ ЧИСЛОМ МАРШРУТОВ В МЕТРИЧЕСКИХ ПРОСТРАНСТВАХ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ УДВОЕНИЯ

Standard

АППРОКСИМИРУЕМОСТЬ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОГРАНИЧЕННЫМ ЧИСЛОМ МАРШРУТОВ В МЕТРИЧЕСКИХ ПРОСТРАНСТВАХ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ УДВОЕНИЯ. / Огородников, Юрий Юрьевич ; Хачай, Михаил Юрьевич.
в: Журнал вычислительной математики и математической физики, Том 61, № 7, 2021, стр. 1206-1219.

Результаты исследований: Вклад в журнал › Статья › Рецензирование

BibTeX

@article{256fe87b2be140af90bfc05b61d0d7b7,

title = "АППРОКСИМИРУЕМОСТЬ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОГРАНИЧЕННЫМ ЧИСЛОМ МАРШРУТОВ В МЕТРИЧЕСКИХ ПРОСТРАНСТВАХ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ УДВОЕНИЯ",

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

author = "Огородников, {Юрий Юрьевич} and Хачай, {Михаил Юрьевич}",

year = "2021",

doi = "10.31857/S0044466921070140",

language = "Русский",

volume = "61",

pages = "1206--1219",

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

issn = "0044-4669",

publisher = "Издательство {"}Наука{"}",

number = "7",

}

RIS

TY - JOUR

T1 - АППРОКСИМИРУЕМОСТЬ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОГРАНИЧЕННЫМ ЧИСЛОМ МАРШРУТОВ В МЕТРИЧЕСКИХ ПРОСТРАНСТВАХ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ УДВОЕНИЯ

AU - Огородников, Юрий Юрьевич

AU - Хачай, Михаил Юрьевич

PY - 2021

Y1 - 2021

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

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

UR - https://www.elibrary.ru/item.asp?id=46146281

U2 - 10.31857/S0044466921070140

DO - 10.31857/S0044466921070140

M3 - Статья

VL - 61

SP - 1206

EP - 1219

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

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

SN - 0044-4669

IS - 7

ER -

ID: 22843989