Metaheuristics applied to the Sensor Network Planning Problem for Gas Leak Detection in Chemical Plants

Wireless Sensor Networks play a central role in industrial monitoring systems, particularly in the detection of gas leaks in chemical plants. In this context, the definition of the subset of active sensors must simultaneously consider energy limitations, coverage quality, and device incompatibility constraints. Such Sensor Network Planning Problem for Gas Leak Detection in Chemical Plants (PPRS-DVG) can be modeled as a Backpack Problem with Disjunctive Constraints, NP-difficult in nature. This work proposes the CALNS-RVND metaheuristic, which combines a constructive heuristic guided by graph coloring, adaptive destruction and repair operators that explore the structure of the conflict graph, and systematic local search via RVND. Computational experiments on 50 benchmark instances demonstrate that CALNS-RVND outperforms the commercial CPLEX resolver and the E-ILS metaheuristics with average gains of 1.18% and 2.46%, respectively.