Selecting optimal locations for new facilities is a critical decision in organizations that provide field-based services such as delivery, maintenance and emergency services. The total logistics cost and facility establishment cost are the main objectives of the location selection procedure. With the increasing size of this problem in today's applications, the aspects of efficiency and scalability have developed into major challenges. In this paper, we study the use of spatial clustering methods to solve this problem and propose two new algorithms. The new algorithms determine the optimal locations of the new facilities plus their optimal total count during the search process. We have conducted many experiments for empirical comparative study on the application of several spatial clustering algorithms for optimal facility establishment. The benchmarks are conducted with both real world and synthetic data sets. The results reveal advantages of the proposed algorithms and confirm that these algorithms have better performance in terms of efficiency and objectives in the field-based services. Hence, the higher scalability and effectiveness of the proposed algorithms make them suitable solutions for the problem of optimal facility establishment with large databases.