Exact and approximation algorithms for many-visits travelling salesperson problems
| Autor: | Vincze, Roland |
|---|---|
| Přispěvatelé: | Mnich, Matthias |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Technische Universität Hamburg (2022) |
| Popis: | Das Problem des Handlungsreisenden mit mehrfachen Besuchen ist eine natürliche Verallgemeinerung des Problems des Handlungsreisenden. Gegeben ist hierbei eine Reihe von Städten mit ihren paarweisen Abständen und eine geforderte Anzahl an Besuchen für jede Stadt. Das Ziel ist es zwischen zwei vorgegebenen Städten eine Reisestrecke minimaler Kosten zu finden, die jede Stadt genau so oft besucht, wie es gefordert ist. In dieser Arbeit stellen wir zunächst einen exakten Algorithmus vor, welcher eine optimale Lösung berechnet und dabei, abhängig von der Größe der Eingabe, exponentiell viel Zeit aber nur polynomiell viel Speicherplatz benötigt. Die Zeit- und Speicherplatzkomplexität ist dabei asymptotisch optimal. Darüber hinaus präsentieren wir eine effiziente 1,5-Approximation unter metrischen Entfernungskosten sowie Approximationen mit konstanter Güte für verschiedene Varianten des Problems mit mehreren Reisenden. The Many-Visits Path TSP is a natural generalisation of the Travelling Salesman Path Problem. We are given a set of cities, with pairwise distances between the cities, and in addition a visit requirement for each city. The aim is to find a minimum-cost walk between two specified end-vertices, that visits each city exactly as many times, as its requirement. In this thesis, we first provide an exact algorithm for the problem, that calculates an optimal solution in time exponential but space polynomial in the size of the input. The time and space complexities are asymptotically best possible. Moreover, we provide an efficient 1.5-approximation in case of metric distance costs, and constant-factor approximations for several variants of the problem with multiple agents. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|