TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Approximations for many-visits multiple traveling salesman problems
 
Options

Approximations for many-visits multiple traveling salesman problems

Citation Link: https://doi.org/10.15480/882.4873
Publikationstyp
Journal Article
Date Issued
2023-04
Sprache
English
Author(s)
Bérczi, Kristóf  
Mnich, Matthias  orcid-logo
Vincze, Roland  orcid-logo
Institut
Algorithmen und Komplexität E-11  
TORE-DOI
10.15480/882.4873
TORE-URI
http://hdl.handle.net/11420/14130
Journal
Omega  
Volume
116
Article Number
102816
Citation
Omega 116: 102816 (2023)
Publisher DOI
10.1016/j.omega.2022.102816
Scopus ID
2-s2.0-85143772894
Publisher
Elsevier
Peer Reviewed
true
Is New Version of
10.15480/882.4524
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.
Subjects
Traveling salesman
Many-agent scheduling
Aircraft sequencing
DDC Class
330: Wirtschaft
Funding(s)
Simultaneous approximation of multi-criteria optimization problems  
Funding Organisations
Deutscher Akademischer Austauschdienst (DAAD)  
Publication version
submittedVersion
Lizenz
http://rightsstatements.org/vocab/InC/1.0/
Loading...
Thumbnail Image
Name

2201.02054 (1).pdf

Size

887.57 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback