Filters

Settings

Now showing1 - 2 of 2
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: with files ,
    Approximations for many-visits multiple traveling salesman problems
    (Elsevier, 2023-04)
    Bérczi, Kristóf
    ;
    Mnich, Matthias
    ;
    Vincze, Roland
    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.
    Publicationtype: Journal Article
    Scopus© Citations 2  118  395
  • Some of the metrics are blocked by your 
    consent settings
    Item type:Publication, Access status: with files ,
    Scopus© Citations 8  186  561