The paper, Advanced Algorithms for the Three-Dimensional Beacon Placement Problem Based on Constraint Programming, Large Neighborhood Search, and Evolutionary Methods, investigates how Bluetooth Low Energy (BLE) beacons can be positioned efficiently throughout large, multi-storey buildings. The aim is to minimise the number of beacons, and therefore installation and maintenance costs, while ensuring that every relevant indoor position is covered by at least three beacons so that trilateration can be used reliably.
The problem is challenging because beacon signals are affected by the three-dimensional structure of a building, including walls, ceilings, their thicknesses and their materials. The authors therefore use an RSSI-based signal model that represents different levels of signal resistance for open space, drywall, solid walls and glass. Building layouts are discretised into spatial cells, with the model calculating which areas each possible beacon position can cover. The optimisation must achieve triple coverage while also maintaining sufficient separation between beacons and minimising the total number deployed.
The paper compares three main families of optimisation techniques. Constraint Programming formulates beacon placement as a Constraint Optimisation Problem and can theoretically identify globally optimal solutions, but the search space becomes extremely large in three dimensions. Large Neighborhood Search (LNS) instead starts with a feasible placement and repeatedly removes and replaces groups of beacons, attempting to improve the solution. Evolutionary Algorithms maintain populations of placements and use selection, crossover and mutation to progressively favour solutions that require fewer beacons. The authors also develop hybrid approaches in which Constraint Programming and LNS are combined on a floor-by-floor basis.
The paper shows that the best way to solve large three-dimensional BLE beacon placement problems is not to pursue a single globally optimal search. A hybrid approach combining constraint-based optimisation with faster heuristic search can produce near-minimal, fully covering beacon layouts much more reliably and at a scale that is realistic for complex buildings.