Internet service providers cost optimization

Fast, reliable and affordable internet is a necessity of our age. In this thesis, the productivity of internet service provider(ISP) companies' in Turkey is examined. We studied how ISPs can lower the expenses to provide cheaper and faster service for their customers and our study revealed that excavation costs make up more that ninety percent of the total infrastructure costs. Thus, setting up the network so that the excavation costs are minimized would significantly reduce the infrastucture costs. The problem is modelled as the Steiner Tree Problem, which is known to be NP-hard. Since our graph is huge, using superpolynomial algorithms to solve the problem optimally would be computationally infeasible. Therefore; we used Prim's heuristic, which guarantees a solution within a factor of 2 of the optimum and runs rather fast. PostgreSQL relational database management system and Python programming language are the technologies we used in our implementation. In this work, real data obtained from one of the pioneer ISPs in Turkey is utilized. We have determined that 14.776 km long excavation is sufficient to serve all the customers of the ISP whose data we utilized. This is a significant improvement over their existing 24.868 km long network.