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.

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

process.

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