Geodesic
Synchronized Traveling Salesman Problem
Journal of graph algorithms and applications, Tome 25 (2021) no. 1, pp. 437-459 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We consider a variation of the well-known traveling salesman problem in which there are multiple agents who all have to tour the whole set of nodes of the same graph, while obeying node- and edge-capacity constraints require that agents must not "crash". We consider the simplest model in which the input is an undirected graph with all capacities equal to one. A solution to the synchronized traveling salesman problem is called an "agency". Our model puts the synchronized traveling salesman problem in a similar relation with the traveling salesman problem as the so-called evacuation problem, or the well-known dynamic flow (flow-over-time) problem is in relation with the minimum cost flow problem. We measure the strength of an agency in terms of number of agents which should be as large as possible, and the time horizon which should be as small as possible. Beside some elementary discussion of the notions introduced, we establish several upper and lower bounds for the strength of an agency under the assumption that the input graph is a tree, or a 3-connected 3-regular graph. 
@article{JGAA_2021_25_1_a19,
     author = {Gyula Pap and J\'ozsef Varny\'u},
     title = {Synchronized {Traveling} {Salesman} {Problem}},
     journal = {Journal of graph algorithms and applications},
     pages = {437--459},
     year = {2021},
     volume = {25},
     number = {1},
     doi = {10.7155/jgaa.00566},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00566/}
}
TY  - JOUR
AU  - Gyula Pap
AU  - József Varnyú
TI  - Synchronized Traveling Salesman Problem
JO  - Journal of graph algorithms and applications
PY  - 2021
SP  - 437
EP  - 459
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00566/
DO  - 10.7155/jgaa.00566
LA  - en
ID  - JGAA_2021_25_1_a19
ER  - 
%0 Journal Article
%A Gyula Pap
%A József Varnyú
%T Synchronized Traveling Salesman Problem
%J Journal of graph algorithms and applications
%D 2021
%P 437-459
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00566/
%R 10.7155/jgaa.00566
%G en
%F JGAA_2021_25_1_a19
Gyula Pap; József Varnyú. Synchronized Traveling Salesman Problem. Journal of graph algorithms and applications, Tome 25 (2021) no. 1, pp. 437-459. doi: 10.7155/jgaa.00566

Cité par Sources :