BİLDİRİ DETAY

Mumtaz KARATAS, Ertan YAKICI
SOLVING A DISCRETE BARRIER LOCATION PROBLEM: MATHEMATICAL MODELLING AND METAHEURISTIC APPROACHES
 
Introduction: Sensor or facility location problems can be categorized with respect to the problem structure as: area coverage, point coverage, and barrier coverage problems. In area coverage problems the objective is to cover an area of interest with available sensors. In point coverage problems, the objective is to protect or attain surveillance on a number of critical points in the area. In such applications other parts of the area can be left uncovered and they mostly require less sensors than required in area coverage scenarios. In barrier coverage problems, on the other hand, the decision-maker’s objective is to protect a belt-shaped region or a line segment which represents a barrier separating two regions. In this study we consider the barrier problem and assuming discrete candidate sensor locations we develop an analytical method and a greedy heuristic to locate a given number of sensor. We further assume that multiple types of targets and sensors exist. Purpose: The purpose of this research is to analyze the performances of mathematical modelling, greedy heuristic, and genetic algorithm approaches in solving discrete barrier problems in the presence of multiple sensor and target types. Scope: The scope of this study includes the discrete barrier problem where the barrier is modelled as a single line segment between two regions. The research has lasted approximately two months. Limitations: The scope of this study includes line type barriers with discrete settings. Also we do not consider intelligent target types. Method: To achieve our objectives, we first modeled the location problem using an Integer Non-Linear Programming (INLP) model. Next we implemented a greedy heuristic approach for the same problem. Finally we designed a Genetic Algorithm (GA) metaheuristic and compared the performances of the three approaches in terms of computation time and solution quality. We’ve also compared the results of our models with the lower and upper bounds computed by random and uniform sensor location schemes. For this purpose we’ve developed several test cases by changing the number of sensors available and number of candidate sensor locations. Each problem setting is solved for 30 random replications. Instances are generated and solved in the General Algebraic Modeling System (GAMS©) environment using CPLEX 12.2.0.2 solver. Findings: The simulation results provided us with the quantitative performances of solution approach with respect to the computation times and solution qualities. The results revealed that, on the overall, the GA performs poorest in terms of computation time and the INLP outperforms other approaches. In terms of solution quality, on the other hand, the superior approach varies depending on the number of candidate locations used in the problem. In general, the INLP performs slightly better in large problem instances whereas the Greedy heuristic is better for small instances. Interestingly, the GA can only outperform the Greedy heuristic in large problem instances. Conclusion: The results obtained through our numerical experiments provided us with a quantitative assessment of the performances of the three solution approaches with respect to computing time and solution qualities. Our analysis revealed that the most appropriate solution approach varies depending on the problem size.

Anahtar Kelimeler: Sensor Networks, Barrier Coverage, Simulation, Genetic Algorithm, Greedy Heuristic



 


Keywords: