The large investments required for deploying passive optical networks (PONs) render the disposal of appropriate planning tools for designing such networks in a cost-effective way a necessity. This paper addresses the problem of finding the least costly tree topology time-division multiplexing PON (TDM-PON) deployment configurations considering equipment and installation costs (CAPEX) and operational exploration costs. With this purpose, an integer linear programing model is developed, which is capable of designing not only common single-stage PON configurations, but also PONs with multiple stages of optical splitting. In order to reduce the computation time for problems of larger size, a two-stage heuristic is also proposed. The simulation results for the cases studied reveal that an optimal multistage splitting strategy can lead to cost savings of up to 15% in CAPEX expenditures in comparison with the traditional single-stage approach. Furthermore, the heuristic procedure proposed is shown to obtain results within acceptable bounds relative to the optimum solutions, hence validating its use for larger sized networks. The results also show that the average CAPEX cost savings between the two-stage and single-stage approaches are quite dependent on the strategies used to choose candidate locations for the splitters, with values ranging from 5 to 12% depending on whether random candidate placement or k-means-based placement is used.