New exact algorithms for planar maximum covering location by ellipses problems

Danilo Tedeschi and Marina Andretta

European Journal of Operational Research, 2021, vol. 291, issue 1, 114-127

Abstract: Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to choose the location of ellipses given their major and minor axes to cover demand points, maximizing a function depending on the value of covered points. We propose new exact algorithms for two versions of this problem, one where the ellipses have to be parallel to the coordinate axes, and another where they can be freely rotated. Besides finding optimal solutions for previously published instances, including the ones where no optimal solution was known, both algorithms proposed by us were able to obtain optimal solutions for some new larger instances with up to seven hundred demand points and five ellipses.

Keywords: Combinatorial optimization; Planar maximal covering location problem; Planar covering by ellipses; Exact algorithms (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172030833X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:291:y:2021:i:1:p:114-127

DOI: 10.1016/j.ejor.2020.09.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().