The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the Disc Covering Problem on a Line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of- view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.

Agnetis, A., Grande, E., Mirchandani, P., Pacifici, A. (2009). Covering a line segment with variable radius discs. COMPUTERS & OPERATIONS RESEARCH, 36(5), 1423-1436 [10.1016/j.cor.2008.02.013].

Covering a line segment with variable radius discs

PACIFICI, ANDREA
2009-01-01

Abstract

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the Disc Covering Problem on a Line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of- view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.
2009
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/09 - RICERCA OPERATIVA
English
Agnetis, A., Grande, E., Mirchandani, P., Pacifici, A. (2009). Covering a line segment with variable radius discs. COMPUTERS & OPERATIONS RESEARCH, 36(5), 1423-1436 [10.1016/j.cor.2008.02.013].
Agnetis, A; Grande, E; Mirchandani, P; Pacifici, A
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
COR.pdf

accesso aperto

Descrizione: Articolo principale
Dimensione 335.09 kB
Formato Adobe PDF
335.09 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/10964
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 28
social impact