# Continuous Space Wireless Communication Tower Placement by Hybrid Simulated Annealing
## 2 Related Work  
There are many communication tower placement problems in the real world, such as base station placement problems [4; 5; 6; 7; 8; 9], relay station placement problems [10; 11], sensor placement problems [12; 13], access point placement problems [14; 15], edge server placement problems [16; 17], cloudlet placement problems [18; 19; 20], gateway placement problems [21; 22; 23], and CORS network placement problems [24; 2]. These communication tower placement problems are different from each other in their objectives and/or constraints. From the computational perspective, wireless communication tower placement problems can be categorized into _discrete wireless communication tower placement problems_ and _continuous space wireless communication tower placement problems_. In discrete wireless communication tower placement problems, the candidate locations of the communication towers are given. Thus, discrete communication tower placement problems involve choosing a set of locations among those candidate locations to place communication devices such that their objectives are optimal, subject to some constraints. From a computational point of view, discrete wireless communication tower placement problems are constrained combinatorial optimization problems. Thus, various combinatorial optimization algorithms have been applied to solve the problems of locating discrete wireless communication towers. In continuous space wireless communication tower placement problems, no candidate locations are given for the placement of wireless communication towers. Thus, continuous space wireless communication tower placement problems involve finding locations in a given two-dimensional area to place those wireless communication towers such that their objectives are optimal, subject to some constraints. To handle the continuous space wireless communication tower placement problems, the two-dimensional area is usually divided into grids, and the placement of the communication towers is limited to the grid positions. In this way, a continuous wireless communication tower placement problem can be transformed into a discrete wireless communication tower placement problem by approximation, and the methods used to solve the discrete wireless communication tower placement problems are used to solve the continuous communication tower placement problems [9]. However, this approximation method may not find an optimal solution to the wireless communication tower placement problem, as the approximation method omits a large amount of continuous search space. Figure 1 shows a scenario where a discrete algorithm cannot find an optimal solution to a wireless communication tower placement problem. In this scenario, there are five users and four grid points, A, B, C, and D. However, if the wireless communication tower is placed at A, B, C, or D, the wireless communication tower cannot cover all five users. However, as illustrated in the figure, all five users can be covered by a single wireless communication tower at the location marked '\(\times\)'. Since the location is not a grid point, this optimal solution is excluded by the approximation method. In addition, most existing methods for discrete wireless communication tower placement problems use integer programming, mixed integer programming, or mixed integer nonlinear programming. Thus, they are suitable for large-scale communication tower placement problems, as they are not scalable. In recent years, simulated annealing (SA) has been used to solve various tower/base station placement problems [25; 26]. The research problem addressed in [25] is a discrete base transmitter station (BTS) problem. Its objectives are to optimize the capacity and location of existing BTS towers to obtain telecommunication efficiency and quality of service. The research problem addressed in [26] is a classical k-facility placement problem. It is also a discrete placement problem, as it is assumed that all the facilities must be placed on a grid graph. The objective is to maximize the coverage of k facilities.