New exact algorithms for planar maximum covering location by ellipses problems

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. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

Planar Maximum Covering Location by Ellipses is an optimization problem where the goal is to choose the location of ellipses in order to cover demand points, maximizing a function based on the value of covered points. New exact algorithms were proposed for two versions of this problem - one with ellipses parallel to the coordinate axes and another with freely rotatable ellipses. These algorithms were able to find optimal solutions for previously published instances as well as new larger instances.