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.
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection