New exact algorithms for planar maximum covering location by ellipses problems

Author(s)

Tedeschi, Danilo ^[1] ; Andretta, Marina ^[1]

Affiliation

^[1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Dept Matemt Aplicada & Estat, Ave Trabalhador Sao Carlense 400, BR-13566590 Sao Carlos, SP - Brazil

• Document type: Journal article
• Source: European Journal of Operational Research; v. 291, n. 1, p. 114-127, MAY 16 2021.
• Web of Science Citations: 0

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

• FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
• Grantee: Francisco Louzada Neto
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants