# Modeling and Optimization of NO2 Stations in the Smart City of Barcelona
## 4 Methodology
### Optimal Location of Stations
Next, the algorithm performs a multistart procedure to generate new solutions until a maximum execution time is reached. In each iteration, the algorithm generates a new solution \(S_{new}\) using a biased-randomized version of the destructive heuristic combined with the local search operator. The biased-randomized heuristic introduces a slight modification in the greedy constructive behavior, which provides a certain degree of randomness while maintaining the logic behind the constructive heuristic. The biased-randomized version considers each element in the edges list with a probability that follows a geometric distribution with a single parameter \(\beta\in(0,1)\), which controls the relative level of greediness present in the randomized behavior of the algorithm [62]. By employing a biased-randomized version of the constructive heuristic, multiple alternative solutions can be generated without losing the logic behind the original heuristic. Next, the algorithm compares the newly generated solution to the best-known solution. If the new solution has a lower objective function value, the best-known solution is updated. Once the stopping criterion is met, the algorithm returns the best-found solution. Algorithm 2 shows the destructive heuristic procedure. Initially, the heuristic assumes all stations are opened. Then, the edges connecting the stations are sorted in ascending order according to their distance between the stations. Next, an iterative process begins, where certain stations are removed from the solution. At each iteration, an edge is selected from the list of edges in a greedy or biased-randomized manner. The facility to be removed is chosen randomly from the two stations connected by the selected edge, and the edges connected to the deleted facility are also removed from the list of edges. This procedure is repeated until the percentage of open stations falls below the required threshold. Then, the last facility that was removed is reintroduced in the solution to preserve its feasibility, and the initial solution is returned by the procedure. The local search procedure is depicted in Algorithm 3. This procedure involves removing the oldest station from the solution and reconstructing the solution with a station not currently included. It is important to note that a removed station will not be considered for generating a new solution until all older stations (i.e., those added earlier) have been eliminated from the solution. This approach facilitates efficient space exploration while avoiding redundancy in the search process. The procedure continues until a maximum number of iterations without improvement is reached. Given the budget constraints on the number of stations that can be installed, we also analyze the impact of the percentage of open stations, which is controlled by a parameter \(m\). When \(m\) is set to 0.1, it indicates that only 10% of the stations are open; conversely, setting \(m\) to 0.9 means that 90% of the air quality stations are operational. Our objective is to identify the optimal combination of area coverage percentage and overlap among these stations, resulting in the most efficient air quality monitoring network. To achieve this, we utilize a Pareto frontier to evaluate the effects of the parameter \(m\) on both the percentage of area coverage and the percentage of overlap between stations. By generating the Pareto frontier, we can discern the trade-offs between the percentage of covered area and the percentage of overlap, enabling us to identify the best configurations that balance maximizing coverage with minimizing redundancy.