Doctor's Theses (authored and supervised):

B. Hu:
"Hybrid Metaheuristics for Generalized Network Design Problems";
Supervisor, Reviewer: G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2008; oral examination: 2008-12-11.

English abstract:
In this thesis, we consider several generalized network design problems (NDPs) which
belong to the family of NP-hard combinatorial optimization problems. In contrast
to classical NDPs, the generalized versions are de ned on graphs whose node sets
are partitioned into clusters. The goal is to nd a subgraph which spans exactly one
node from each cluster and also meets further constraints respectively.
Applicable methodologies for solving combinatorial optimization problems can
roughly be divided into two mainstreams. The rst class consists of algorithms which
aim to solve these problems to proven optimality { provided that they are given
enough run-time and memory. This thesis starts with a brief introduction to linear
and integer linear programming techniques since popular algorithms like branch-andbound,
branch-and-cut, etc. are based on them. The second class are metaheuristics
which compute approximate solutions but usually require signi cantly less runtime.
By combining these two classes, we are able to form collaboration approaches that
bene t from advantages of both sides. We will examine various possibilities of such
combinations and some of them will be used to solve the NDPs in this thesis.
The rst considered NDP is the generalized minimum spanning tree problem. Given
a graph whose nodes are partitioned into clusters, we seek a minimum spanning tree
which connects exactly one node from each cluster. A variable neighborhood search
(VNS) approach will be presented that uses three di erent neighborhood types. Two
of them work in complementary ways in order to maximize search performance. Both
are large in the sense that they contain exponentially many candidate solutions,
but e cient polynomial-time algorithms are used to identify best neighbors. For
the third neighborhood type we apply integer programming to optimize local parts
within candidate solution trees.
We then study the generalized traveling salesman problem (GTSP). Given a clustered
graph, we seek the minimum-costs round trip visiting one node from each
cluster. A VNS algorithm based on two complementary, large neighborhood structures
is proposed. One of them is the already known generalized 2-opt neighborhood
for which a new incremental evaluation technique is described, which speeds up the
search signi cantly. The second structure is based on node exchanges and the application
of the chained Lin-Kernighan heuristic.
As a related problem to the GTSP, we also consider the railway traveling salesman
problem (RTSP).We are given a timetable and a salesman who has to visit a number
of cities by train to carry out some business. He starts and ends at a speci ed home
city, and the required time for the overall journey, including waiting times, shall
be minimized. Two transformation schemes to reformulate the problem as either a
classical asymmetric or symmetric traveling salesman problem (TSP) are presented.
Using these transformations, established algorithms for solving the TSP can be used
to attack the RTSP as well.
Finally, we consider the generalized minimum edge biconnected network problem.
For a given clustered graph, we look for a minimum-costs subgraph connecting one
node from each cluster in an edge biconnected way, i.e. at least two edge-disjoint
paths must exist between each pair of nodes. Three VNS variants are considered
that utilize di erent types of neighborhood structures, each of them addressing particular
properties as spanned nodes and/or the edges between them. For the more
complex neighborhood structures, e cient techniques { such as a graph reduction
{ are applied to essentially speed up the search process. For comparison purpose,
a mixed integer linear programming formulation based on multi commodity ows is
proposed to solve smaller instances of this problem to proven optimality.
Looking at the obtained results, we observe that the fundamental strategy of combining
complementary neighborhood structures is very successful for solving generalized
NDPs. In particular, all of them are shown to contribute signi cantly to the search

Created from the Publication Database of the Vienna University of Technology.