Geodesic
Cooperative strong equilibrium in a~vehicle routing game
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 5 (2013) no. 3, pp. 3-26.

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

In the paper game-theoretic approach is considered for the vehicle routing problem with many distributors. Any customer is characterized by demand and wholesale price. Under this scenario some customers could be unvisited by a distributor. Such a statement is called vehicle routing game, VRG, in coordinated strategies. A procedure for determining strong equilibrium in the VRG is proposed. Such solution is stable against deviations of any coalition. In the procedure the optimization problem is solved iteratively for every distributor. On each step a set of customers is reduced. Existence of two types of strong equilibrium is solved. Cooperative strong equilibrium is presented. All results are illustrated with numerical examples.
Keywords: combinatorial optimization, Nash equilibrium, strong equilibrium, cooperative strong equilibrium, transportation network, vehicle routing problem. 
@article{MGTA_2013_5_3_a0,
     author = {Nikolay A. Zenkevich and Andrey V. Zyatchin},
     title = {Cooperative strong equilibrium in a~vehicle routing game},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {3--26},
     publisher = {mathdoc},
     volume = {5},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2013_5_3_a0/}
}
TY  - JOUR
AU  - Nikolay A. Zenkevich
AU  - Andrey V. Zyatchin
TI  - Cooperative strong equilibrium in a~vehicle routing game
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2013
SP  - 3
EP  - 26
VL  - 5
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2013_5_3_a0/
LA  - ru
ID  - MGTA_2013_5_3_a0
ER  - 
%0 Journal Article
%A Nikolay A. Zenkevich
%A Andrey V. Zyatchin
%T Cooperative strong equilibrium in a~vehicle routing game
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2013
%P 3-26
%V 5
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2013_5_3_a0/
%G ru
%F MGTA_2013_5_3_a0
Nikolay A. Zenkevich; Andrey V. Zyatchin. Cooperative strong equilibrium in a~vehicle routing game. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 5 (2013) no. 3, pp. 3-26. http://geodesic.mathdoc.fr/item/MGTA_2013_5_3_a0/

[1] Zakharov V., Schegryaev A., “Ustoichivaya kooperatsiya v dinamicheskikh zadachakh marshrutizatsii transporta”, Matematicheskaya teoriya igr i ee prilozheniya, 4:2 (2012), 39–56 | Zbl

[2] Petrosyan L. A., “Odna transportnaya teoretiko-igrovaya model na seti”, Matematicheskaya teoriya igr i ee prilozheniya, 3:4 (2011), 89–98 | Zbl

[3] Aas B., Gribkovskaia I., Halskau Sh. Sr., Shlopak A., “Routing of supply vessels to petroleum installations”, International Journal of Physical Distribution Logistics Management, 37:2 (2007), 164–179 | DOI

[4] Aumann R. J., “Acceptable points in general cooperative $n$-person games”, Contributions to the Theory of Games, v. IV, Annals of Mathematics Study, 40, ed. A. W. Tucker, 1959, 287–324 | MR | Zbl

[5] Cornillier F., Boctor F. F., Laporte G., Renaud J., “An exact algorithm for the petrol station replenishment problem”, Journal of the Operational Research Society, 59:5 (2008), 607–615 | DOI | Zbl

[6] Dantzig G. B., Ramser J. H., “The truck dispatching problem”, Management Science, 6:1 (1959), 80–91 | DOI | MR | Zbl

[7] Desrochers M., Lenstra J. K., Savelsbergh M. W. P., “A classification scheme for vehicle-routing and scheduling problems”, European Journal of Operational Research, 46:3 (1990), 322–332 | DOI | Zbl

[8] Dresher M., The mathematics of games of strategy: theory and applications, Rand Corp., Santa Monica, CA, 1961, Chapter 4 | MR | Zbl

[9] Gairing M., Monien B., Tiemann K., “Selfish routing with incomplete information”, Theory of Computing Systems, 42:1 (2008), 91–130 | DOI | MR | Zbl

[10] Galeotti A., Goyal S., Jackson M. O., Vega-Redondo F., Yariv L., “Network Games”, Review of Economic Studies, 77:1 (2010), 218–244 | DOI | MR | Zbl

[11] Jackson M., “The stability and efficiency of economic and social networks”, Advances in economic design, eds. B. Dutta, M. O. Jackson, 2003, 319–361 | DOI

[12] Lau H. C., Sim M., Teo K. M., “Vehicle routing problem with time windows and a limited number of vehicles”, European Journal of Operational Research, 148:3, 559–569 | DOI | MR | Zbl

[13] Luce R. D., Raiffa H., Games and decisions: introduction and critical survey, Wiley, New York, 1957, Chapter 3 | MR | Zbl

[14] Myerson R., “Graphs and cooperation in games”, Mathematics of Operations Research, 2:3 (1977), 225–229 | DOI | MR | Zbl

[15] Myerson R., Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, Mass., 1991 | MR | Zbl

[16] Savelsbergh M. W. P., Sol M., “The general pickup and delivery problem transportation”, Science, 29 (1995), 17–29 | Zbl

[17] Solomon M. M., Desrosiers J., “Time window constrained routing and scheduling problems”, Transportation Science, 22:1 (1988), 1–13 | DOI | MR | Zbl

[18] Taillard E., Badeau P., Gendreau M., Guertin F., Potvin J. Y., “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation Science, 31:2 (1997), 170–186 | DOI | Zbl

[19] Zenkevich N., Zyatchin A., “Strong equilibrium technique in differential games”, Game Theory and Applications, 15 (2011), 207–224