Resource type
Thesis type
(Thesis) M.Sc.
Date created
2014-04-10
Authors/Contributors
Author: Shen, Xueying
Abstract
In this thesis we study several models for the Path Selection Problem associated with the construction of fibre optic networks. Four different variations of the problem are studied: Greedy Path Selection Problem (GPSP), Benevolent Path Selection Problem (BPSP), Discounted Path Selection Problem (DPSP) and Path Selection with capacity expansion (EPSP). All the variations are NP-hard and polynomially solvable special cases are identified for GPSP and BPSP. We also present detailed complexity analysis and integer programming formulations for these problems. Heuristic algorithms including greedy algorithm, semi-greedy algorithm and multi-start local search algorithm are developed for each problem. Extensive computational results are provided with the algorithm performance analysis. We also present some future directions for research.
Document
Identifier
etd8306
Copyright statement
Copyright is held by the author.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Download file | Size |
---|---|
etd8306_XShen.pdf | 1.11 MB |