| Telecommunications network design and logistics are two fields where operations research techniques can be applied to greatly improve service quality and cost-effectiveness. Tabu Search (TS) is a powerful approach for solving many difficult combinatorial optimization problems. In this dissertation, TS heuristics are developed and implemented for solving a set of important decision-making problems arising in the above two areas. The first problem addressed is a problem in Digital Data Service network design that involves selection of a subset of central offices to connect all customers in a spanning tree or ring framework. The second problem considered is the trunk capacity planning problem in a dynamic routing communications network. Finally, the well-known vehicle routing problem (VRP) which is at the heart of many logistics and delivery systems is addressed. All these problems can be formulated as integer programming problems and are computationally intractable.;The TS algorithms developed for solving these problems contain some key elements that include blending of different neighborhoods, recency-based memory, aspiration criteria, frequency-based memory, cost estimation and error-correction, probabilistic move selection, candidate list strategy, elite solution recovery strategy, multi-level schema, systematic fine-tuning, and efficient data structures. For the VRP problem, a generic two phase heuristic based on a set-covering approach is also developed. Computational experiments on test data show that for the two telecommunications network design problems, the tabu search heuristics can obtain optimal solutions for all small size problems, and significantly improve the best heuristics available for these problems. For the VRP benchmark problems the heuristics developed are highly competitive with other cutting edge heuristics. The results validate TS as a highly effective tool for solving difficult combinatorial optimization problems. |
