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

Translated title of the contribution: COALITION-FORMATION PROBLEM FOR COOPERATIVE INVENTORY ROUTING GAME

Вячеслав Андреевич Широких, Елена Александровна Лежнина

Research output: Contribution to journalArticlepeer-review

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.
Translated title of the contributionCOALITION-FORMATION PROBLEM FOR COOPERATIVE INVENTORY ROUTING GAME
Original languageRussian
Pages (from-to)99-115
JournalМАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИГР И ЕЕ ПРИЛОЖЕНИЯ
Volume10
Issue number1
StatePublished - 2018

Keywords

  • inventory routing problem (IRP)
  • cooperative inventory-routing game (CIRG)
  • characteristic function
  • heuristic algorithm

Fingerprint

Dive into the research topics of 'COALITION-FORMATION PROBLEM FOR COOPERATIVE INVENTORY ROUTING GAME'. Together they form a unique fingerprint.

Cite this