Synchronized Traveling Salesman Problem
| Autor: | József Varnyú, Gyula Pap |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Discrete Mathematics (cs.DM) General Computer Science Computer science Time horizon Travelling salesman problem Upper and lower bounds Tree (graph theory) Computer Science Applications Theoretical Computer Science Computational Theory and Mathematics Flow (mathematics) Graph (abstract data type) Node (circuits) Geometry and Topology Minimum-cost flow problem Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Graph Algorithms and Applications. 25:437-459 |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00566 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|