Geodesic
About construction of realizability arias of salesman strategies in dynamic salesmen problem
Contributions to game theory and management, Tome 14 (2021), pp. 113-121.

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

The dynamic travelling salesman problem, where we assume that all objects can move with constant velocity, is considered. To solve this NP-hard problem we use a game-theoretic approach and well-known solution concepts of pursuit games. We identify the realizability areas of salesman strategies depending on the initial positions of customers and their velocities. We present different cases of realizability areas of salesman strategies constructing in Python program with several numbers of customers.
Keywords: dynamic travelling salesman problem, non-zero sum game, Nash equilibrium, realizability areas. 
@article{CGTM_2021_14_a10,
     author = {Anastasiya V. Gavrilova and Yaroslavna B. Pankratova},
     title = {About construction of realizability arias of salesman strategies in dynamic salesmen problem},
     journal = {Contributions to game theory and management},
     pages = {113--121},
     publisher = {mathdoc},
     volume = {14},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2021_14_a10/}
}
TY  - JOUR
AU  - Anastasiya V. Gavrilova
AU  - Yaroslavna B. Pankratova
TI  - About construction of realizability arias of salesman strategies in dynamic salesmen problem
JO  - Contributions to game theory and management
PY  - 2021
SP  - 113
EP  - 121
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2021_14_a10/
LA  - en
ID  - CGTM_2021_14_a10
ER  - 
%0 Journal Article
%A Anastasiya V. Gavrilova
%A Yaroslavna B. Pankratova
%T About construction of realizability arias of salesman strategies in dynamic salesmen problem
%J Contributions to game theory and management
%D 2021
%P 113-121
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2021_14_a10/
%G en
%F CGTM_2021_14_a10
Anastasiya V. Gavrilova; Yaroslavna B. Pankratova. About construction of realizability arias of salesman strategies in dynamic salesmen problem. Contributions to game theory and management, Tome 14 (2021), pp. 113-121. http://geodesic.mathdoc.fr/item/CGTM_2021_14_a10/

[1] Gavrilova A. A., Pankratova Ya. B., “Realizability Areas of Strategies in the Dynamic Traveling Salesman Problem”, Control Processes and Sustainability, 7:1 (2020), 367–371

[2] de Freitas J. C., Penna P. H. V., “A variable neighborhood search for flying sidekick traveling salesman problem”, International Transactions in Operational Research, 27:1, 267–290 | MR

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

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

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

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

[7] 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

[8] 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 | MR

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

[10] Petrosjan L. A., ““Life-line” Pursuit Games with Several Players”, Izv. Akad. Nauk Armjan. SSR Ser. Mat., 1:5 (1965), 331–340 | MR

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

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

[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, v. III, Nova Science Publ., N.Y., 1998, 115–123 | MR

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

[16] Tarashnina S., Pankratova Y., Purtyan A., “On a dynamic traveling salesman problem”, Contributions to Game Theory and Management, 10 (2017), 326–338 | MR

[17] Autom. Remote Control, 69:1 (2008), 42–51 | MR | MR | Zbl