Evolutionary Greedy Algorithm for Optimal Sensor Placement Problem in Urban Sewage Surveillance

Abstract

<p>Designing a cost-effective sensor placement plan for sewage surveillance is a crucial task because it allows cost-effective early pandemic outbreak detection as supplementation for individual testing.<br>However, this problem is computationally challenging to solve, especially for massive sewage networks having complicated topologies. In this paper, we formulate this problem as a multi-objective<br>optimization problem to consider the conflicting objectives and put forward a novel evolutionary greedy algorithm (EG) to enable efficient and effective optimization for large-scale directed networks.<br>The proposed model is evaluated on both small-scale synthetic networks and a large-scale, real-world sewage network in Hong Kong. The experiments on small-scale synthetic networks demonstrate a<br>consistent efficiency improvement with reasonable optimization performance and the real-world application shows that our method is effective in generating optimal sensor placement plans to guide<br>policy-making. <br></p>