On a Dynamic Traveling Salesman Problem

Authors

  • Svetlana Tarashnina Saint Petersburg State University
  • Yaroslavna Pankratova Saint Petersburg State University
  • Aleksandra Purtyan Saint Petersburg State University

Abstract

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

Downloads

Download data is not yet available.

References

Isaaks, R. (1965). Differential Games: a mathematical theory with applications to warfare and pursuit, Control and Optimization, New York: Wiley.

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). On a Family of Differential Games of Survival in Rn. Akad. Nauk Dokl. SSSR Ser. Mat., 1, 52–54.

Petrosjan, L.A. (1977). Ustojchivost’ Reshenij v Differencial’nyh Igrah so Mnogimi Uchastnikami. Vestnik Leningrad Univ. Math., 19(4), 49–52.

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 m 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.

Sedakov, A.A. (2015). Strong Time Consistent Core. Mat. Teor. Igr. Prilozh., 7(2), 69–84.

Downloads

Published

2022-04-17

How to Cite

Tarashnina, S., Pankratova, Y., & Purtyan, A. (2022). On a Dynamic Traveling Salesman Problem. Contributions to Game Theory and Management, 10. Retrieved from https://gametheory.spbu.ru/article/view/13266

Issue

Vol. 10 (2017)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.