Optimization for Sensor Locations to Detect Sewer Overflows

Challenge

The purpose of the project was to validate a technique to select monitoring locations and times that best reduce the probability and consequences of sewage overflows.

In physical terms, the problem represents movement of ultrasonic level monitors through discrete locations in a sewer network. The monitors move in both a distance and direction in accordance with rules established by a search algorithm.

As the monitors move, they change their state, defined by a "Risk Priority Number" (RPN). The monitors act individually but it is their collective RPN that needs to be optimized. The goal is for the monitors to seek "hot spots" in the environment where the RPN is highest. RPNs are known to cluster within the environment as illustrated below. The deepest purple color codes indicate the highest clusters of RPN. Red line segments are a redundant indication of high RPN.

The main objective was to generate a tool using AnyLogic to parameterize the problem and to have an easy and clean method to develop the best optimization algorithm.

Solution

The data was imported from GIS files and cleaned using R. The cleaned data was exported to an Excel file to be used by AnyLogic directly. Using R in this case was easier and faster than processing the data using the ShapeFile and JAVA directly in AnyLogic. It is generally a good idea to process the data before using it in AnyLogic.

The monitors can move in different ways depending on the optimization algorithm chosen. The idea was to enhance the simulated annealing algorithm and compare it to three others:

• The basic version of simulated annealing algorithm
• The greedy algorithm
• The sequential search

The map shows the manholes with the different characteristics of the search parameters (monitors, hotspots, manholes and search reach) and graphs on the evolution of the objective function from iteration to iteration. The map was generated using Euclidean coordinates since the shapefile provided by the client didn't have the geolocation of the manholes, but instead had a transformation to Euclidean space.

In this project, the client was very participative and interested in doing most of the analysis himself, so the focus was mainly oriented into developing tools within the simulation model to help the client perform those analyses. The client learned how to use the simulation model thoroughly. We then worked together to improve the enhanced simulated annealing algorithm.

Outcome

The model was very useful for the client to understand different characteristics of the system and the use of diverse parameters necessary to generate hotspots and to initialize the position of monitors in the real world. It was also very insightful for the client to find a way to improve the algorithm by testing a number of parameter combinations and small adjustments to enhance the simulated annealing algorithm. We worked step-by-step making small changes progressively until we found a good solution that fulfilled the initial needs.

Project Features

• Industry: Wastewater
• Model: Agent-Based
• Duration: 11 months