Lagrangian relaxation for the directional sensor coverage problem with continuous orientation. (March 2018)

• Record Type: Journal Article
• Authors: Astorino, Annabella; Gaudioso, Manlio; Miglionico, Giovanna
• Is Part Of: Omega. Volume 75(2018)
• Page Start: 77
• Page End: 86
• Publication Date: 2018-03
• Subjects: Directional sensors -- Lagrangian relaxation -- Lagrangian heuristics -- MINLP; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2017.03.001
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: MINLP formulation of the directional sensor coverage problem. The orientation of each sensor is a continuous variable. NP-hardness of the problem is proved. Lagrangian relaxation approach is adopted plus ad hoc dual ascent. The Lagrangian based heuristics is compared against an exact method. Abstract: We present a mixed integer nonlinear programming formulation of the Directional Sensors Continuous Coverage Problem (DSCCP), where a given set of targets on a plane are to be covered by a set of sensors whose locations are known. Sensors are supposed to be directional, that is characterized by a discrete set of possible radii and aperture angles. The orientation (which is a continuous variable), the radius and the aperture angle of each sensor are to be decided, taking into account possibility of keeping one or more sensors switched off. The objective is to minimize cost coverage. We incorporate into the objective function penalty cost for possibly uncovered targets. We prove NP-hardness of DSCCP and introduce a Lagrangian relaxation model. We design a dual ascent procedure based on acting on a single multiplier at a time accompanied by a heuristics to find a feasible solution at each ascent iteration. We report also the results of the method on several test problems.