Formulações e heurísticas para o problema de localização de coberturas com sobreposições
Arquivos
Data
2020-02-19
Autores
Araujo, Eliseu Junio 
Orientadores
Chaves, Antonio Augusto
Tipo
Tese de doutorado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
Coverage location problems and its variations aim to locate facilities strategically to meet the maximum number of demand points that require attendance, meeting different criteria, for example, meeting service capacity constraints. We observe that in many contexts, there are regions that need different priorities for their population concentration, since a region may have different population concentrations. Thus, the priorities are represented by the amount and the organization of coverage zones that must offer as adequate support according to the number of demands covered, avoiding overload of service. Due to the literature have gaps of efficient approaches about this theme, this thesis proposes the overlaps control between coverage zones to meet different prioritization criteria. Thus, a constraint that enables this control is adapted to classical coverage problems. Basically, this constraint quantifies the proportion of overlaps between coverage zones and, depending on the user’s choice, maximizes or minimizes them. Therefore, the control is integrated into the Maximal Coverage Location Problem (MCLP), to the Probabilistic Maximal Coverage location-allocation Problem (PMCLP), and to the Coverage Location Problem (CLP). In instances that optimal solution was not found by CPLEX, the method Density Clustering Search (DCS) was chose to give good solutions to the classical problems due to having re- turned good solutions to problems related to coverage. Results show that overlaps control combination with coverage location problems was efficient, giving the expected solutions. DCS results also show that the method is efficient in terms of objective function value and computational time.
O problema de localização de coberturas e suas variações consistem em localizar estrategicamente facilidades para atender o máximo de demandas possível que requisitam serviços, obedecendo a diferentes critérios estabelecidos, como, por exemplo, o atendimento de restrições de capacidade de serviços. Percebe-se que em muitos contextos, há regiões que necessitam de prioridades diferenciadas de atendimento em decorrência de sua concentração populacional, uma vez que uma mesma região pode ter locais com diferentes densidades de moradores. Portanto, as prioridades são representadas pela quantidade e pela forma como estão organizadas as coberturas de serviços, que devem procurar oferecer um suporte adequado de acordo com a quantidade de demandas cobertas, evitando sobrecarga de serviços. Devido a essa necessidade ser recorrente e a literatura apresentar falta de abordagens abrangentes e eficientes que a atendam, este trabalho propõe o controle de sobreposições entre coberturas para localizar as facilidades de tal forma a obedecer aos mais diversos critérios de priorização. Assim, uma restrição que viabiliza esse controle é incluída em modelos clássicos de cobertura presentes na literatura. Essa restrição quantifica a proporção de sobreposições entre as coberturas e, de acordo com a escolha do usuário, as maximiza ou minimiza. O controle é integrado ao problema de máxima cobertura para priorizar regiões de acordo com suas densidades populacionais, ao problema probabilístico de alocação-localização de máxima cobertura para melhorar a qualidade de atendimento à população e ao problema de localização de coberturas para minimizar custos operacionais. Os testes computacionais foram feitos por meio da aplicação do solver CPLEX em instâncias da literatura. Nos contextos em que a solução ótima não foi encontrada com a aplicação do solver CPLEX, o método híbrido Density Clustering Search (DCS) foi escolhido para retornar boas soluções aos problemas devido aos bons resultados que têm retornado em contextos próximos ao problema de coberturas. Os resultados demonstraram que a combinação do con- trole de sobreposições aos diferentes problemas foi eficiente, ao reportar as soluções esperadas para os contextos analisados. Os resultados do DCS também atestaram eficiência do método em termos de função objetivo e tempo computacional.
O problema de localização de coberturas e suas variações consistem em localizar estrategicamente facilidades para atender o máximo de demandas possível que requisitam serviços, obedecendo a diferentes critérios estabelecidos, como, por exemplo, o atendimento de restrições de capacidade de serviços. Percebe-se que em muitos contextos, há regiões que necessitam de prioridades diferenciadas de atendimento em decorrência de sua concentração populacional, uma vez que uma mesma região pode ter locais com diferentes densidades de moradores. Portanto, as prioridades são representadas pela quantidade e pela forma como estão organizadas as coberturas de serviços, que devem procurar oferecer um suporte adequado de acordo com a quantidade de demandas cobertas, evitando sobrecarga de serviços. Devido a essa necessidade ser recorrente e a literatura apresentar falta de abordagens abrangentes e eficientes que a atendam, este trabalho propõe o controle de sobreposições entre coberturas para localizar as facilidades de tal forma a obedecer aos mais diversos critérios de priorização. Assim, uma restrição que viabiliza esse controle é incluída em modelos clássicos de cobertura presentes na literatura. Essa restrição quantifica a proporção de sobreposições entre as coberturas e, de acordo com a escolha do usuário, as maximiza ou minimiza. O controle é integrado ao problema de máxima cobertura para priorizar regiões de acordo com suas densidades populacionais, ao problema probabilístico de alocação-localização de máxima cobertura para melhorar a qualidade de atendimento à população e ao problema de localização de coberturas para minimizar custos operacionais. Os testes computacionais foram feitos por meio da aplicação do solver CPLEX em instâncias da literatura. Nos contextos em que a solução ótima não foi encontrada com a aplicação do solver CPLEX, o método híbrido Density Clustering Search (DCS) foi escolhido para retornar boas soluções aos problemas devido aos bons resultados que têm retornado em contextos próximos ao problema de coberturas. Os resultados demonstraram que a combinação do con- trole de sobreposições aos diferentes problemas foi eficiente, ao reportar as soluções esperadas para os contextos analisados. Os resultados do DCS também atestaram eficiência do método em termos de função objetivo e tempo computacional.