Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00566
Synchronized Traveling Salesman Problem
Gyula Pap and
József Varnyú
Vol. 25, no. 1, pp. 437459, 2021. Regular paper.
Abstract We consider a variation of the wellknown 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 edgecapacity 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 socalled evacuation problem, or the wellknown dynamic flow (flowovertime) 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 3connected 3regular graph.
This work is licensed under the terms of the CCBY license.

Submitted: December 2020.
Reviewed: May 2021.
Revised: July 2021.
Accepted: July 2021.
Final: August 2021.
Published: September 2021.
Communicated by
Yoshio Okamoto

Journal Supporters
