Abstract:
|
Metaheuristics are successful algorithmic concepts to tackle extit{NP}-hard combinatorial optimization problems.
In this paper we deal with metaheuristics for the K-cardinality tree (KCT) problem in edge-weighted graphs. This
problem has several applications, which justify the need for efficient methods to obtain good solutions. There are
already metaheuristic approaches to tackle the KCT problem to be found in the literature. However, there is a lack
of benchmark problem instances and therefore also a lack of comparison between these approaches. Moreover,
studies comparing metaheuristic approaches -- for whatever combinatorial optimization problem -- often suffer from
the fact that they compare results obtained on different processors, on program code implemented in different
programming languages and based on different data structures. In contrast to these studies, we aim for a fair
comparison of three different metaheuristic approaches. We compare these approaches on a carefully chosen set of
benchmark instances characterized by several distinguishing features. Our results show, that due to the different
characteristics of different areas of the problem instance space none of our metaheuristic approaches can be
identified as the best metaheuristic approach. It is rather the case that each approach has its advantages for certain
areas of the problem instance space. |