A computational study for the hierarchical maximal covering location problem
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Estudo computacional para o problema hierárquico de cobertura máxima
Primeiro orientador
Membros da banca
Alexandre Xavier Martins
Fatima Machado de Sousa Lima
Gilberto de Miranda Jr.
Marcone Jamilson Freitas Souza
Fatima Machado de Sousa Lima
Gilberto de Miranda Jr.
Marcone Jamilson Freitas Souza
Resumo
Choosing the ideal location for a business or service is a crucial decision in both
the private and public sectors. An incorrect location can result in additional relocation
costs and can also jeopardize the organization’s strategy. In healthcare,
this is particularly crucial, as it has the potential to compromise the health care
provided to the population, resulting in increased morbidity and mortality. Maximum
coverage issues are valuable in situations where resource constraints prevent
the entire population from being served, thus requiring the selection of the location
that offers the highest possible level of service. Healthcare services are inherently
hierarchical, characterized by varying types of care, levels of complexity, and areas
of coverage. Based on the systematic review addressing the location of healthcare
services, we found that the literature considers only up to two hierarchical
levels. However, in real-world scenarios, it may be necessary to consider three
levels of healthcare services – Emergency Department, Clinic, and Hospital. This
study aims to evaluate the performance of four approaches using Benders decomposition,
an exact method, to solve the hierarchical service location problem in
adapted instances of Cordeau et al. (2019) with up to 100,000 customers. The
results indicate that, especially in large-scale problems, hierarchical location represents
a significant challenge for traditional solvers such as CPLEX. Benders’
algorithms are significantly faster than CPLEX, reaching up to 58 times faster in
finding the optimal solution for instances with up to 100,000 customers. The epigraph
and reverse polar approaches obtained the best performances, being good
options to assist decision makers in choosing the best location for health services.
The three-level hierarchical location problem still presents many challenges for research
and future work, to make it a problem closer to reality, such as considering
service capacity, road conditions and applying the algorithm to real data.
Abstract
A escolha do local ideal para um negócio ou serviço é uma decisão crucial, tanto no
setor privado quanto no público. Uma escolha incorreta pode implicar em custos
adicionais para realocar, além de prejudicar a estratégia das organizações. Nos
serviços de saúde, isso se torna particularmente crucial, pois tem o potencial de
comprometer o atendimento médico à população, resultando em um aumento da
morbidade e da mortalidade. Os problemas de máxima cobertura são valiosos em
situações onde há restrições de recursos que impedem atender a totalidade da população,
exigindo, assim, a seleção da localização que ofereça o maior nível de serviço
possível. Os serviços de saúde são intrinsecamente hierárquicos, caracterizados por
variados tipos de atendimento, níveis de complexidade e áreas de cobertura. Com
base na revisão sistemática abordando a localização de serviços de saúde, verificamos
que a literatura considera apenas até dois níveis hierárquicos. No entanto,
em cenários do mundo real, pode ser necessário considerar três níveis de serviços
de saúde - Pronto Atendimento, Clínico e Hospitalar. Este estudo tem como objetivo
avaliar o desempenho de quatro abordagens usando decomposição de Benders,
método exato, para a resolução do problema de localização hierárquica de serviços
em instâncias adaptadas do Cordeau et al. (2019) com até 100.000 clientes. Os
resultados indicam que, sobretudo em problemas de grande porte, a localização
hierárquica representa um desafio significativo para solvers tradicionais como o
CPLEX. Os algoritmos de Benders mostram-se significativamente mais rápidos
que o CPLEX, chegando a ser até 58 vezes mais rápido para encontrar a solução
ótima para instâncias com até 100.000 clientes. As abordagens da epígrafe e polar
reverso obtiveram os melhores desempenhos, sendo boas opções para auxiliar os
tomadores de decisão na escolha da melhor localização dos serviços de saúde. O
problema de localização hierárquica de três níveis ainda apresenta muito desafio de
pesquisas e trabalhos futuros, para torná-lo um problema mais próximo da realidade
como por exemplo considerar capacidade dos serviços, condições das estradas
e aplicar o algoritmo a dados reais.
Assunto
Engenharia de produção, Serviços de saúde, Programação (Computadores)
Palavras-chave
Facility location, Localização de facilidades, Hierarchical location, Localização hierárquica, Maximum coverage, Máxima cobertura, Healthcare services, Serviços de saúde, Benders decomposition, Decomposição de benders