Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.4873

Publisher DOI: | 10.1016/j.omega.2022.102816 | 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. |
URI: | http://hdl.handle.net/11420/14130 | 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: | ![]() |
Is new version of: | 10.15480/882.4524 |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2201.02054 (1).pdf | 887,57 kB | Adobe PDF | View/Open![]() |
Page view(s)
64
checked on Mar 22, 2023
Download(s)
42
checked on Mar 22, 2023
Google ScholarTM
Check
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.