2022/01/06 by Kristóf Bérczi, Bérczi, Kristóf, Matthias Mnich +3
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2201.02054
25 pages, 3 figures
arxiv created 2022/01/06 · openalex publication_date 2022/01/06 · arxiv updated 2022/01/07 · openalex created_date 2022/04/03 · openalex updated_date 2026/08/04
A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of m salesmen jointly visit all cities from a set of n cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. An extensive survey by Bektas (Omega 34(3), 2006) lists a variety of heuristic and exact solution procedures for the mTSP, which quickly solve particular problem instances. In this work we consider a further generalization of mTSP, the many-visits mTSP, where each city v has a request r(v) of how many times it should be visited by the salesmen. This problem opens up new real-life applications such as aircraft sequencing, while at the same time it poses several computational challenges. We provide multiple efficient approximation algorithms for important variants of the many-visits mTSP, which are guaranteed to quickly compute high-quality solutions for all problem instances.