Exact and approximation algorithms for many-visits travelling salesperson problems

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.

Schlagworte

traveling salesman problem

approximation algorithms

graph algorithms

combinatorial optimization

matroid theory

DDC Class

510: Mathematik

Funding Organisations

Deutsche Forschungsgemeinschaft (DFG)

Deutscher Akademischer Austauschdienst (DAAD)

More Funding Information

DAAD grant no. 57449568 and DFG project MN 59/4-1.

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

Roland_Vincze_PhD_thesis_2021_Exact-and-Approximation-Algorithms-for-Many-Visits-Travelling-Salesperson-Problems.pdf

Size

1.22 MB

Format

Adobe PDF

Options

Exact and approximation algorithms for many-visits travelling salesperson problems