Geodesic
Coalition-formation problem for cooperative inventory routing game
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 10 (2018) no. 1, pp. 99-115.

Voir la notice de l'article provenant de la source Math-Net.Ru

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: inventory routing problem ($IRP$), cooperative inventory-routing game ($CIRG$), characteristic function
Mots-clés : heuristic algorithm. 
@article{MGTA_2018_10_1_a5,
     author = {Viacheslav A. Shirokikh and Elena A. Lezhnina},
     title = {Coalition-formation problem for cooperative inventory routing game},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {99--115},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a5/}
}
TY  - JOUR
AU  - Viacheslav A. Shirokikh
AU  - Elena A. Lezhnina
TI  - Coalition-formation problem for cooperative inventory routing game
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2018
SP  - 99
EP  - 115
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a5/
LA  - ru
ID  - MGTA_2018_10_1_a5
ER  - 
%0 Journal Article
%A Viacheslav A. Shirokikh
%A Elena A. Lezhnina
%T Coalition-formation problem for cooperative inventory routing game
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2018
%P 99-115
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a5/
%G ru
%F MGTA_2018_10_1_a5
Viacheslav A. Shirokikh; Elena A. Lezhnina. Coalition-formation problem for cooperative inventory routing game. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 10 (2018) no. 1, pp. 99-115. http://geodesic.mathdoc.fr/item/MGTA_2018_10_1_a5/

[1] Archetti C., Bertazzi L., Laporte G., Speranza M. G., “A branch-and-cut algo-rithm for a vendor-managed inventory-routing problem”, Transportation Science, 41:3 (2007), 382–391 | DOI

[2] Archetti C., Bianchessi N., Irnich S., Speranza M. G., “Formulations for an in-ventory routing problem”, International Transactions in Operational Research, 21:3 (2014), 353–374 | DOI | MR | Zbl

[3] Aumann R. J., Dreze J. H., “Cooperative games with coalition structures”, International Journal of Game Theory, 3:4 (1974), 217–237 | DOI | MR | Zbl

[4] Bellman R., Dynamic Programming, Princeton University Press, Princeton, 1957 | MR | Zbl

[5] Coelho L. C., Cordeau J. F., Laporte G., “Thirty years of inventory routing”, Transportation Science, 48:1 (2013), 1–19 | DOI | MR

[6] Coelho L. C., Cordeau J. F., Laporte G., “The inventory-routing problem with transshipment”, Computers and Operations Research, 39:11 (2012), 2537–2548 | DOI | MR | Zbl

[7] Cordeau J. F., Lagana D., Musmanno R., Vocaturo F., “A decomposition-based heuristic for the multiple-product inventory-routing problem”, Computers Operations Research, 55 (2015), 153–166 | DOI | MR | Zbl

[8] Desaulniers G., Rakke J. G., Coelho L. C., “A branch-price-and-cut algorithm for the inventory-routing problem”, Transportation Science, 50:3 (2015), 1060–1076 | DOI

[9] Driessen T. S. H., Tijs S. H., “The Cost Gap Method and Other Cost Allocation Methods For Multipurpose Water Projects”, Water Resources Research, 21:10 (1985), 1469–1475 | DOI

[10] Frisk M., Gothe-Lundgren M., Jornsten K., Ronnqvist M., “Cost allocation in collaborative forest transportation”, European Journal of Operational Research, 205 (2010), 448–458 | DOI | Zbl

[11] Guajardo M., Ronnqvist M., “A review on cost allocation methods in collaborative transportation”, International Transactions in Operational Research, 23:3 (2016), 371–392 | DOI | MR | Zbl

[12] Jouida J. B., Sihem K., Krichen S., Klibi W., “Coalition-formation problem for sourcing contract design in supply networks”, European Journal of Operational Research, 257:2 (2017), 539–558 | DOI | MR | Zbl

[13] Kimms A., Kozeletskyi I., “Core-based cost allocation in the cooperative traveling salesman problem”, European Journal of Operational Research, 248:3 (2016), 910–916 | DOI | MR | Zbl

[14] Krajewska M. A., Kopfer H., Laporte G., Ropke S., Zaccour G., “Horizontal cooperation among freight carriers: request allocation and profit sharing”, Journal of the Operational Research Society, 59:11 (2008), 1483–1491 | DOI | Zbl

[15] Ropke S., Pisinger D., “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows”, Transportation Science, 40:4 (2006), 455–472 | DOI

[16] Verdonck L., Caris A. N., Ramaekers K., Janssens G. K., “Collaborative logistics from the perspective of road transportation companies”, Transport Reviews, 33:6 (2003), 700–719 | DOI

[17] Zakharov V., Krylatov A., “Equilibrium Assignments in Competitive and Cooperative Traffic Flow Routing”, IFIP Advances in Information and Communication Technology, 434, Springer, 2014, 641–648

[18] Zakharov V. V., Shchegryaev A. N., “Stable cooperation in dynamic vehicle routing problems”, Automation and Remote Control, 76:5 (2015), 935–943 | DOI | MR

[19] Zakharov V. V., Shirokikh V. A., “Heuristic evaluation of the characteristic function in the Cooperative Inventory Routing Game”, J. Veh. Routing Algorithms, 2017 | DOI

[20] http://www.leandro-coelho.com/instances/inventory-routing/