RUS  ENG
Full version
JOURNALS // Contributions to Game Theory and Management // Archive

Contributions to Game Theory and Management, 2017 Volume 10, Pages 326–338 (Mi cgtm313)

This article is cited in 1 paper

On a dynamic traveling salesman problem

Svetlana Tarashnina, Yaroslavna Pankratova, Aleksandra Purtyan

St. Petersburg State University, Universitetskaya emb., 7/9, St. Petersburg, 199034, Russia

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.

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024