AbstractsMathematics

The thesis considers the target visitation problem, a combinatorial optimization problem, which merges the classical traveling salesman problem with the linear ordering problem. In more detail, we are looking for a tour which visits a set of targets and which is optimal with respect to two different aspects: On the one hand, we have given a travel cost from each target to every other. On the other hand, we have preference values which tell us how much we would like to visit one target before another one. The objective is now to maximize the difference of the sum of the met preferences and the total travel costs. We test several different integer programming formulations and examine the associated polytopes concerning their facets and combinatorial structure. We come to the result that a model based on the combination of integer programming formulations for the traveling salesman problem and the linear ordering problem is most suitable for being used in practical computations. For this model we then develop an extended formulation. Besides the theoretical studies, this thesis also contains a practical part, where we apply the various methods of combinatorial optimization to the target visitation problem. We examine their performance and the amount of memory they need on a set of self-defined benchmark instances. We also realize that the target visitation problem is, from a practical point of view, a really tough problem. Therefore, we cannot only implement the basic methods, but we have to apply special techniques to obtain exact solutions for instances with thirty or more targets. The best results are achieved by a branch-and-cut approach which uses the facet classes we discovered in the theoretical part of the thesis. Besides the exact approaches, we also examine different heuristics which are inspired by approximation approaches for the traveling salesman problem.