Coalition-Formation Problem for Cooperative Inventory Routing Game

V. A. Shirokikh, E. A. Lezhnina

Результат исследований: Научные публикации в периодических изданияхстатья

Выдержка

This paper studies stability of carrier coalitions in a cooperative inventory routing game (CIRG). Difficulty of this study is not only in a computational complexity of the class of routing problems, but also in the task of constructing a characteristic function, since heuristic solutions that are usually used in routing problems can't guarantee the subadditivity property in the general case. In its turn, violation of subadditivity can lead to instability of a coalition, because a player could get more profit in a different coalition or individually. To solve routing problems, Adaptive large neighborhood search (ALNS) and its modification with the Dynamic adaptation method, DALNS, are used in this work. A special Direct coalition induction algorithm (DCIA) is used to construct a subadditive characteristic function, and four different concepts of cooperative game solutions are considered. The analysis of extensive computational experiments allows to illustrate the dependence of the stability of a grand coalition on such factors as a routing algorithm, an algorithm for a characteristic function construction, and a solution concept for a cooperative game.

Язык оригиналаАнглийский
Страницы (с-по)1358-1367
ЖурналAutomation and Remote Control
Том80
Номер выпуска7
DOI
СостояниеОпубликовано - 1 июл 2019

Предметные области Scopus

  • Системотехника
  • Электротехника и электроника

Цитировать

@article{a9fa019b34694f83a25894a501f377a5,
title = "Coalition-Formation Problem for Cooperative Inventory Routing Game",
abstract = "This paper studies stability of carrier coalitions in a cooperative inventory routing game (CIRG). Difficulty of this study is not only in a computational complexity of the class of routing problems, but also in the task of constructing a characteristic function, since heuristic solutions that are usually used in routing problems can't guarantee the subadditivity property in the general case. In its turn, violation of subadditivity can lead to instability of a coalition, because a player could get more profit in a different coalition or individually. To solve routing problems, Adaptive large neighborhood search (ALNS) and its modification with the Dynamic adaptation method, DALNS, are used in this work. A special Direct coalition induction algorithm (DCIA) is used to construct a subadditive characteristic function, and four different concepts of cooperative game solutions are considered. The analysis of extensive computational experiments allows to illustrate the dependence of the stability of a grand coalition on such factors as a routing algorithm, an algorithm for a characteristic function construction, and a solution concept for a cooperative game.",
keywords = "characteristic function, cooperative inventory-routing game (CIRG), heuristic algorithm, inventory routing problem (IRP)",
author = "Shirokikh, {V. A.} and Lezhnina, {E. A.}",
year = "2019",
month = "7",
day = "1",
doi = "10.1134/S0005117919070129",
language = "Английский",
volume = "80",
pages = "1358--1367",
journal = "Automation and Remote Control",
issn = "0005-1179",
publisher = "МАИК {"}Наука/Интерпериодика{"}",
number = "7",

}

Coalition-Formation Problem for Cooperative Inventory Routing Game. / Shirokikh, V. A.; Lezhnina, E. A.

В: Automation and Remote Control, Том 80, № 7, 01.07.2019, стр. 1358-1367.

Результат исследований: Научные публикации в периодических изданияхстатья

TY - JOUR

T1 - Coalition-Formation Problem for Cooperative Inventory Routing Game

AU - Shirokikh, V. A.

AU - Lezhnina, E. A.

PY - 2019/7/1

Y1 - 2019/7/1

N2 - This paper studies stability of carrier coalitions in a cooperative inventory routing game (CIRG). Difficulty of this study is not only in a computational complexity of the class of routing problems, but also in the task of constructing a characteristic function, since heuristic solutions that are usually used in routing problems can't guarantee the subadditivity property in the general case. In its turn, violation of subadditivity can lead to instability of a coalition, because a player could get more profit in a different coalition or individually. To solve routing problems, Adaptive large neighborhood search (ALNS) and its modification with the Dynamic adaptation method, DALNS, are used in this work. A special Direct coalition induction algorithm (DCIA) is used to construct a subadditive characteristic function, and four different concepts of cooperative game solutions are considered. The analysis of extensive computational experiments allows to illustrate the dependence of the stability of a grand coalition on such factors as a routing algorithm, an algorithm for a characteristic function construction, and a solution concept for a cooperative game.

AB - This paper studies stability of carrier coalitions in a cooperative inventory routing game (CIRG). Difficulty of this study is not only in a computational complexity of the class of routing problems, but also in the task of constructing a characteristic function, since heuristic solutions that are usually used in routing problems can't guarantee the subadditivity property in the general case. In its turn, violation of subadditivity can lead to instability of a coalition, because a player could get more profit in a different coalition or individually. To solve routing problems, Adaptive large neighborhood search (ALNS) and its modification with the Dynamic adaptation method, DALNS, are used in this work. A special Direct coalition induction algorithm (DCIA) is used to construct a subadditive characteristic function, and four different concepts of cooperative game solutions are considered. The analysis of extensive computational experiments allows to illustrate the dependence of the stability of a grand coalition on such factors as a routing algorithm, an algorithm for a characteristic function construction, and a solution concept for a cooperative game.

KW - characteristic function

KW - cooperative inventory-routing game (CIRG)

KW - heuristic algorithm

KW - inventory routing problem (IRP)

UR - http://www.scopus.com/inward/record.url?scp=85068843879&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/coalitionformation-problem-cooperative-inventory-routing-game

U2 - 10.1134/S0005117919070129

DO - 10.1134/S0005117919070129

M3 - статья

VL - 80

SP - 1358

EP - 1367

JO - Automation and Remote Control

JF - Automation and Remote Control

SN - 0005-1179

IS - 7

ER -