Title page for ETD etd-09032002-115648

Type of Document

Master's Thesis

Author

Kulkarni, Girish ,

Author's Email Address

gkulkar@unity.ncsu.edu

URN

etd-09032002-115648

Title

A Tabu Search Algorithm for the Steiner Tree Problem.

Degree

Master of Science

Graduate Program

Operations Research

Advisory Committee

Advisor Name	Title
Dr. Yahya Fathi	Committee Chair
Dr Stephen Roberts	Committee Member
Dr. George Rouskas	Committee Member

Keywords

Steiner Tree
Tabu Search
meta-heuristics

Date of Defense

2002-08-15

Availability

unrestricted

Abstract

ABSTRACT

KULKARNI, GIRISH. A Tabu Search Algorithm for the Steiner Tree Problem. (Under the direction of Professor Yahya Fathi.)

The Steiner Tree problem in graphs is an NP-hard problem having applications in many areas including telecommunication, distribution and transportation systems. We survey, briefly, a few exact methods and a few heuristic approaches that have been proposed for solving this problem. Further, we propose a tabu search algorithm whose key feature includes a neighborhood definition consisting of exchange of key paths. The algorithm is empirically tested by running computational experiments on problem sets, with known optimal values, that are available over the internet. The results from the tabu search are compared with the optimal values and with the results of a well-known heuristic procedure. The experimental results show that the tabu search algorithm is reasonably successful. It produces near-optimal solutions in the experiments conducted and performs better than the heuristic procedure. We also explore other avenues for future work and possible extensions to the tabu search algorithm.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	624.25 Kb	00:02:53	00:01:29	00:01:18	00:00:39	00:00:03