Synchronized traveling salesman problem

DOI10.7155/JGAA.00566MaRDI QIDQ5084688zbMATH OpenOpenAlexFDO

Authors Gyula Pap, József Varnyú

Publication date 28 June 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.00311

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: 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.

Recommendations

• The synchronized multi-assignment orienteering problem
• The traveling agent problem
• Cooperative TSP
• Cooperative TSP
• The synchronized arc and node routing problem: application to road marking

Cites work

• A Cutting Planes Algorithm for the m-Salesmen Problem
• A novel approach to solve multiple traveling salesmen problem by genetic algorithm
• An introduction to network flows over time
• Constructing maximal dynamic flows from static flows
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Finding 2-factors closer to TSP tours in cubic graphs
• Pebble game algorithms and sparse graphs
• The dynamic transportation problem: A survey
• The prize collecting traveling salesman problem
• The quickest transshipment problem

Cited in

(1)

• The synchronized multi-assignment orienteering problem

Describes a project that uses

Uses Software

• VRP

This page was built for publication: Synchronized traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084688)