TY - JOUR

T1 - Устойчивость коалиций в кооперативной игре маршрутизации и управления запасами

AU - Широких, Вячеслав Андреевич

AU - Лежнина, Елена Александровна

PY - 2018

Y1 - 2018

N2 - В работе исследуется вопрос устойчивости коалиций перевозчиков в кооперативной игре маршрутизации запасов (Cooperative inventory routing game, CIRG). Сложностью данной задачи является не только вычислительная трудность класса задач маршрутизации, но и вопрос построения характеристической функции, т.~к. эвристические решения, обычно используемые в задачах маршрутизации, в общем случае не могут гарантировать свойство субаддитивности. В свою очередь, нарушение субаддитивности может привести к неустойчивости коалиции, т.~к. игрок сможет получить большую выгоду в другой коалиции или индивидуально. Для решения задач маршрутизации в работе используются алгоритм адаптивного поиска в большой окрестности (Adaptive large neighborhood search, ALNS) и его модификация методом динамической адаптации (DALNS). Специальный алгоритм прямого построения коалиций (Direct coalition induction algorithm, DCIA) использован для построения субаддитивной характеристической функции, а также исследованы 4 различных концепции решения кооперативной игры. Анализ обширных вычислительных экспериментов позволяет проиллюстрировать в статье зависимость устойчивости максимальной коалиции игроков от таких факторов, как алгоритм решения задач маршрутизации, алгоритм построения характеристической функции и концепция решения кооперативной игры.

AB - В работе исследуется вопрос устойчивости коалиций перевозчиков в кооперативной игре маршрутизации запасов (Cooperative inventory routing game, CIRG). Сложностью данной задачи является не только вычислительная трудность класса задач маршрутизации, но и вопрос построения характеристической функции, т.~к. эвристические решения, обычно используемые в задачах маршрутизации, в общем случае не могут гарантировать свойство субаддитивности. В свою очередь, нарушение субаддитивности может привести к неустойчивости коалиции, т.~к. игрок сможет получить большую выгоду в другой коалиции или индивидуально. Для решения задач маршрутизации в работе используются алгоритм адаптивного поиска в большой окрестности (Adaptive large neighborhood search, ALNS) и его модификация методом динамической адаптации (DALNS). Специальный алгоритм прямого построения коалиций (Direct coalition induction algorithm, DCIA) использован для построения субаддитивной характеристической функции, а также исследованы 4 различных концепции решения кооперативной игры. Анализ обширных вычислительных экспериментов позволяет проиллюстрировать в статье зависимость устойчивости максимальной коалиции игроков от таких факторов, как алгоритм решения задач маршрутизации, алгоритм построения характеристической функции и концепция решения кооперативной игры.

KW - задача управления запасами

KW - кооперативная игра

KW - характеристическая функция

KW - эвристический алгоритм

KW - inventory routing problem (IRP)

KW - cooperative inventory-routing game (CIRG)

KW - characteristic function

KW - heuristic algorithm

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

M3 - статья

VL - 10

SP - 99

EP - 115

JO - МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИГР И ЕЕ ПРИЛОЖЕНИЯ

JF - МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИГР И ЕЕ ПРИЛОЖЕНИЯ

SN - 2074-9872

IS - 1

ER -