|Passive optical networks (PONs) are point-to-multipoint networks where a single Central
Office (CO) is connected to a number of downstream Optical Network Units (ONUs)
via a single optical fiber by splitting the optical signal with passive splitters. Due to
technology advances and increasing bandwidth requirements, these networks have moved to last mile deployment, also known as fiber-to-the-home (FTTH). The planning of these PONs are traditionally done by hand, but automated methods
can be used to decrease deployment costs and planning time. Even though a number
of methods have been proposed to address this problem through the solving of integer
linear programming (ILP) models, they suffer from limited availability, inaccuracies and limited scalability due to the problem complexity. This dissertation focusses on improving the accuracy of these models as well as improving scalability to a point where large-scale problems can be solved feasibly. To address this, a basic model is implemented to capture the network structure and verified accordingly. Results show this model can be solved quickly, but has large discrepancies with real-world plans. Refinements in the form of fiber duct sharing, network constraints, multiple splitter types and economies of scale among others are then incorporated into a refined model and solved. Analysis of the experimental results indicates improved accuracy and lower deployment costs, at the expense of increasing computation effort considerably. Heuristic techniques are then examined to improve computational performance, including an elementary heuristic (ELEM), the Branch Contracting Algorithm (BCA) and problem decomposition. It is demonstrated that through the use of k-means clustering, the refined model can be solved in a fraction of the time while keeping deployment costs comparably low.