Advanced Algorithms for the Three-Dimensional Beacon Placement Problem Based on Constraint Programming, Large Neighborhood Search, and Evolutionary Methods

With the increasing deployment of large and heterogeneous building infrastructures, indoor localization has become a key enabling technology for smart buildings and safety-critical environments. In scenarios such as industrial facilities or care institutions, fast and reliable localization of individuals is essential. A common solution is the deployment of Bluetooth beacons within the building, whose signals allow mobile devices to estimate their position. This gives rise to a challenging optimization problem: while sufficient beacon coverage is required to guarantee reliable localization, deployment costs must be minimized by avoiding redundant placements. Consequently, determining an efficient beacon placement that balances coverage quality and cost is a central research challenge. In our previous work presented at the International Conference on Informatics in Control, Automation and Robotics (ICINCO 2025), we investigated several algorithmic approaches to address this problem, including methods based on Constraint Programming, Large Neighborhood Search, and Evolutionary Algorithms. In the present extended paper, we revisit and consolidate the results reported at ICINCO 2025 and present substantially improved solution strategies for each of these paradigms. In particular, we introduce more accurate and computationally efficient techniques for determining the areas covered by deployed beacons, propose a refined parameterization of the individual solving approaches, and develop multiple hybrid methods that combine the strengths of different optimization techniques. Using a set of synthetically generated three-dimensional building models, the proposed beacon placement approaches were systematically compared and evaluated with respect to solution quality, computational efficiency, and scalability. The experimental results show that the developed methods achieve high-quality placements while remaining computationally feasible for problem instances of realistic size, thereby demonstrating their suitability for practical deployment in real-world building environments.