考虑冗余的极小碰集问题研究

Research on the Minimal Hitting Set Problem with Redundancy

针对海上采油平台可燃气体探测器布设优化问题,首先建立了一个精确理论模型;通过对精确理论模型进行降维、简化和数字化处理,得到一个近似应用模型,该模型可视为极小碰集问题的一个变体,即考虑冗余的极小碰集问题。证明了冗余度大于或等于2的极小碰集问题都是NP-完备的。结合探测器布设的应用背景,针对冗余度为2的问题设计了一个启发式算法,旨在保证冗余度的前提下,极小化所需探测器的数目。仿真结果表明,该算法可以在不显著增加或减少探测器安装数目的情况下,使得任何一个拟泄漏点在任何风向下发生泄漏,都可以至少被两个探测器探测到,从而大大提高平台的安全性。

In the production of oil and gas on offshore platforms,there may be leaks in their production and transportation devices.Once leaked,it not only pollutes the marine ecological environment,but also causes explosions when the concentration reaches a certain value,posing a threat to the safety of personnel and equipment.In order to closely monitor the leakage and concentration of gas,combustible gas detectors are usually installed on the platform.The detection range of each combustible gas detector is limited and the detectors are expensive,so it is necessary to optimize the layout of the detector to minimize economic costs while ensuring safety.In the past,the layout of detectors was mostly determined based on empirical criteria in actual production,lacking scientific and systematic methods.This article establishes a mathematical model and designs a heuristic for the optimization of the layout of combustible gas detectors on offshore oil extraction platforms,in order to provide a more scientific and systematic layout plan.Based on the mechanism and characteristics of the layout optimization problem of combustible gas detector,a mathematical programming theoretical model is first established.Then,based on production practice,the theoretical model is dimensionally reduced and simplified:(1)Due to the layout height of detectors is decided by the density of the gas to be leaked,the layout height can be determined in advance,thus the model can be simplified from three-dimensional to two-dimensional.(2)Lower limit of concentration and upper limit of response time are considered for deciding whether the monitoring system will alarm,so the modeling can just consider the state at a certain time,thereby omitting the consideration of time dimension.(3)By digitizing graphics using grids,continuous optimization problems can be transformed into discrete optimization problems,simplifying the problem while also improving operability.Through the above processing,an approximate application model is obtained,which can be regarded as a variant of the minimal hitting set problem,that is,the minimal hitting set problem with redundancy.The computational complexity of minimal hitting set problems with redundancy greater than or equal to 2 are proved to be NP complete by using the method of polynomial reduction.Combined with the application background of layout optimization of combustible gas detectors,a heuristic is designed to solve the minimal hitting set problem,whose redundancy is 2.The heuristic prioritizes the situation where detectors have to be layout,and then takes a series of measures to maximize the number of leakage points that each detector may cover,that is,to achieve the sharing of leakage points with detectors as much as possible,aiming to minimize the number of required detectors while ensuring redundancy.In the simulation experiment,a CHARM 3D simulation model is established based on the Navisworks 3D model of a certain oil extraction platform structure in the South China Sea,and diffusion simulation is conducted,assuming that the gas to be leaked is methane,gas diffusion simulation is conducted in 6 wind directions,and the heuristic is implemented using C language programming.The simulation results show that this heuristic can detect any potential leak point in any wind direction by at least two detectors without significantly increasing or reducing the number of detectors installed,thereby greatly improving the security of the platform.Our next step is to conduct systematic research on the minimum hitting set problem considering redundancy and design a complete algorithm.