Please use this identifier to cite or link to this item:
Fulltext available Open Access
Publisher DOI: 10.1016/
Title: Approximations for many-visits multiple traveling salesman problems
Language: English
Authors: Bérczi, Kristóf 
Mnich, Matthias  
Vincze, Roland  
Keywords: Traveling salesman; Many-agent scheduling; Aircraft sequencing
Issue Date: 2022
Publisher: Elsevier
Source: Omega - The International Journal of Management Science (2022)
Abstract (english): 
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.
DOI: 10.15480/882.4873
ISSN: 1873-5274
Journal: Omega - The International Journal of Management Science 
Institute: Algorithmen und Komplexität E-11 
Document Type: Article
Project: Simultaneous approximation of multi-criteria optimization problems 
Funded by: Deutscher Akademischer Austauschdienst (DAAD) 
Peer Reviewed: Yes
License: In Copyright In Copyright
Is new version of: 10.15480/882.4524
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
2201.02054 (1).pdf887,57 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Mar 22, 2023


checked on Mar 22, 2023

Google ScholarTM


Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.