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

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