Path Selection Problem in Network Design

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2014-04-10
Authors/Contributors
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.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Attachment Size
etd8306_XShen.pdf 1.11 MB