About Construction of Realizability Arias of Salesman Strategies in Dynamic Salesmen Problem

Anastasiya V. Gavrilova; Yaroslavna B. Pankratova

doi:10.21638/11701/spbu31.2021.10

Authors

Anastasiya V. Gavrilova Foresight, Beloostrovskaya St.,17- 2 Saint-Petersburg 197342, Russia
Yaroslavna B. Pankratova St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia https://orcid.org/0000-0002-9827-9681

DOI:

https://doi.org/10.21638/11701/spbu31.2021.10

Abstract

The dynamic travelling salesman problem, where we assume that all objects can move with constant velocity, is considered. To solve this NPhard 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

Downloads

Download data is not yet available.

References

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

de Freitas, J. C. and Penna, P. H. V. (2020) A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 27(1), 267–290

Kleimenov, A. F.(1993). Non zero-sum differential games, Ekaterinburg: Nauka

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Shmoys, D. B. (1986). The Traveling Salesman. JohnWiley and Sons

Michalewicz, Z. (1994). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 2nd edition

Pankratova, Y. (2007). 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 / Editors L.A. Petrosjan, N. A. Zenkevich. St.Petersburg. Graduated School of Management, SPbGU, 361–380

Pankratova, Ya. B. (2010). A Solution of a cooperative differential group pursuit game. Diskretnyi Analiz i Issledovanie Operatsii, 17(2), 57–78 (in Russian)

Pankratova, Ya. and Tarashnina, S. (2004). How many people can be controlled in a group pursuit game. Theory and Decision. Kluwer Academic Publishers. 56, 165–181

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

Petrosjan, L. A. (1965). “Life-line" Pursuit Games with Several Players. Izv. Akad. Nauk Armjan. SSR Ser. Mat., 1(5), 331–340

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

Petrosjan, L. and Tomskii, G. (1983). Geometry of Simple Pursuit. Nauka, Novosibirsk (in Russian)

Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag

Tarashnina, S. (1998). Nash equilibria in a differential pursuit game with one pursuer and evaders. Game Theory and Applications. N.Y. Nova Science Publ. III, 115–123

Tarashnina S. (2002). Time-consistent solution of a cooperative group pursuit game. International Game Theory Review, 4, 301–317

Tarashnina, S., Pankratova, Y., Purtyan, A. (2017). On a dynamic traveling salesman problem. Contributions to Game Theory and Management, 10, 326–338

Sergeev, S. (2008). Hybrid control systems and the dynamic traveling salesman problem. Avtomat. i Telemekh., 1, 45–54; Autom. Remote Control, 69(1), 42–51