New exact algorithms for planar maximum covering location by ellipses problems

Autor(es)

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

Afiliação do(s) autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 291, n. 1, p. 114-127, MAY 16 2021.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático