Geodesic
On a dynamic traveling salesman problem
Contributions to game theory and management, Tome 10 (2017), pp. 326-338.

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

In this paper we consider a dynamic traveling salesman problem (DTSP) in which $n$ objects (the salesman and $m$ customers) move on a plane with constant velocities. Each customer aims to meet the salesman as soon as possible. In turn, the salesman aspires to meet all customers for the minimal time. We formalize this problem as non-zero sum game of pursuit and find its solution as a Nash equilibrium. Finally, we give some examples to illustrate the obtained results.
Keywords: dynamic traveling salesman problem, non-zero sum game, Nash equilibrium. 
@article{CGTM_2017_10_a19,
     author = {Svetlana Tarashnina and Yaroslavna Pankratova and Aleksandra Purtyan},
     title = {On a dynamic traveling salesman problem},
     journal = {Contributions to game theory and management},
     pages = {326--338},
     publisher = {mathdoc},
     volume = {10},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2017_10_a19/}
}
TY  - JOUR
AU  - Svetlana Tarashnina
AU  - Yaroslavna Pankratova
AU  - Aleksandra Purtyan
TI  - On a dynamic traveling salesman problem
JO  - Contributions to game theory and management
PY  - 2017
SP  - 326
EP  - 338
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2017_10_a19/
LA  - en
ID  - CGTM_2017_10_a19
ER  - 
%0 Journal Article
%A Svetlana Tarashnina
%A Yaroslavna Pankratova
%A Aleksandra Purtyan
%T On a dynamic traveling salesman problem
%J Contributions to game theory and management
%D 2017
%P 326-338
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2017_10_a19/
%G en
%F CGTM_2017_10_a19
Svetlana Tarashnina; Yaroslavna Pankratova; Aleksandra Purtyan. On a dynamic traveling salesman problem. Contributions to game theory and management, Tome 10 (2017), pp. 326-338. http://geodesic.mathdoc.fr/item/CGTM_2017_10_a19/

[1] Isaaks R., Differential Games: a mathematical theory with applications to warfare and pursuit, Control and Optimization, Wiley, New York, 1965 | MR

[2] Kleimenov A. F., Non zero-sum differential games, Nauka, Ekaterinburg, 1993 | MR

[3] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., The Traveling Salesman, John Wiley and Sons, 1986 | MR

[4] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, 2nd edition, Springer-Verlag, 1994 | MR | Zbl

[5] Pankratova Y., “Some cases of cooperation in differential pursuit games”, Contributions to Game Theory and Management, Collected papers presented on the International Conference Game Theory and Management, eds. L. A. Petrosjan, N. A. Zenkevich, Graduated School of Management, SPbGU, St. Petersburg, 2007, 361–380 | MR

[6] Pankratova Ya. B., “A Solution of a cooperative differential group pursuit game”, Diskretnyi Analiz i Issledovanie Operatsii, 17:2 (2010), 57–78 (in Russian) | MR | Zbl

[7] Pankratova Ya., Tarashnina S., “How many people can be controlled in a group pursuit game”, Theory and Decision, 56, Kluwer Academic Publishers, 2004, 165–181 | DOI | MR

[8] Pankratova Y., Tarashnina S., Kuzyutin D., “Nash Equilibria in a Group Pursuit Game”, Applied Mathematical Sciences, 10:17 (2016), 809–821 | DOI

[9] Petrosjan L. A., “On a Family of Differential Games of Survival in $R^n$”, Akad. Nauk Dokl. SSSR Ser. Mat., 1 (1965), 52–54 | MR

[10] Petrosjan L. A., “Ustojchivost' Reshenij v Differencial'nyh Igrah so Mnogimi Uchastnikami”, Vestnik Leningrad Univ. Math., 19:4 (1977), 49–52

[11] Petrosjan L. A., Shirjaev V. D., “Simultaneous Pursuit of Several Evaders by one Pursuer”, Vestnik Leningrad Univ. Math., 13 (1981)

[12] Petrosjan L., Tomskii G., Geometry of Simple Pursuit, Nauka, Novosibirsk, 1983 (in Russian) | MR

[13] Reinelt G., The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, 1994 | MR

[14] Tarashnina S., “Nash equilibria in a differential pursuit game with one pursuer and $m$ evaders”, Game Theory and Applications, III, N.Y. Nova Science Publ., 1998, 115–123 | MR

[15] Tarashnina S., “Time-consistent solution of a cooperative group pursuit game”, International Game Theory Review, 4 (2002), 301–317 | DOI | MR | Zbl

[16] Sedakov A. A., “Strong Time Consistent Core”, Mat. Teor. Igr. Prilozh., 7:2 (2015), 69–84 | MR | Zbl