HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Industrial Engineering and Logistics Management >
IELM Master Theses  >

Please use this identifier to cite or link to this item:
Title: Generalized minimum spanning tree problem
Authors: Che, Chan Hou
Issue Date: 2006
Abstract: The Generalized Minimum Spanning Tree problem denoted by GMST is a generalized combinatorial optimization problem, spanning exactly one node from each cluster in an undirected graph. GMST problems are encountered in telecom-munications network planning. In our thesis, we developed a meta-heuristic method, Tabu Search algorithm, to solve this problem. A new heuristic relaxation algorithm based on this Tabu Search to estimate the lower bound is also proposed. We compared computational results of different methods, including a mixed integer programming model, Tabu Search and Genetics Algorithm. In our computational tests on 194 TSPLIB in-stances, Tabu Search found all optimal solutions (the optimal solutions are known in 152 instances out of the 194 TSP instances). For those 42 unsolved instances, our algorithm improved some previously best known solutions. Moreover, lower bounds of some unknown problems are also improved by our heuristic relaxation algorithm.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2006
xi, 52 leaves : ill. ; 30 cm
HKUST Call Number: Thesis IELM 2006 Che
Appears in Collections:IELM Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.