Heuristic algorithms for districting problems

• Ano de defesa: 2023
• Autor(a) principal: Gliesch, Alex Zoch
• Orientador(a): Ritt, Marcus Rolf Peter
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Heurística; Metaheuristicas; Planejamento territorial
• Palavras-chave em Inglês: Compactness; Hybrid heuristic; Connected partitions; Alternating search; Maximum dispersion problem; p-Median problem; p-Center problem
• Link de acesso: http://hdl.handle.net/10183/264005

Nesta tese nós estudamos problemas de distritamento, que são uma classe geral de problemas de otimização que pedem o agrupamento de pequenas unidades geográ ficas em clusters disjuntos, chamados distritos. Este tipo de problema aparece numa variedade de aplicações, que vão desde o distritamento político para eleições, ao dis tritamento de serviços para a distribuição de produtos comerciais ou a prestação de serviços urbanos, até à atribuição de parcelas de terras agrícolas em lotes. Dentre os muitos domínios estão quase sempre presentes três requisitos fundamentais: que os distritos sejam contíguos, geometricamente compactos, e mutuamente equilibrados no que diz respeito a atributos associados às unidades. Dada a vasta gama de aplica ções, estes e outros critérios de planejamento têm sido modelados matematicamente de diferentes maneiras, o que leva a vários problemas de otimização distintos. Na primeira parte desta tese apresentamos de maneira sistemática as diferentes formula ções de problemas distritamento, e os métodos de solução mais comuns encontrados na literatura. Dado que o problema central de encontrar partições equilibradas e conectadas é NP difícil, os métodos de solução para problemas de distritamento têm sido, até agora, heurísticos. Contudo, ao revisar a literatura pode-se observar que estes métodos são tipicamente desenvolvidos de forma independente por pesquisadores, com foco nas aplicações. Na segunda parte desta tese nós olhamos para distritamento sob um ponto de vista independente de aplicação. Nós propomos uma framework heurística extensível que pode lidar com um conjunto grande de variantes de problemas de dis tritamento, e a aplicamos às três variantes mais comuns que consideram differentes funções objetivo para minimizar a dispersão: a p-median, p-center e diameter. Além disso, em análises separadas nós estudamos a sua extensão para critérios específicos de domínio, como custos de roteamento e redistritamento. A nossa heurística é com petitiva quando comparada com outros métodos que são desenvolvidos com foco em uma única variante, e melhora os melhores bounds conhecidos em muitos casos. Um problema particular que tem origem no planejamento de territórios de recolhimento de resíduos chama-se o Maximum Dispersion Problem. Diferentemente dos proble mas de distritamento clássicos, ele pede partições com dispersão máxima em vez de compactas. A terceira parte desta tese foca na resolução do Maximum Dispersion Pro blem. Propomos uma heurística híbrida que combina uma série de componentes que se mostraram eficazes na literatura, e um novo esquema para obter upper bounds. Apesar de ser heurístico, nosso método encontra mais frequentemente soluções óti mas do que métodos exatos da literatura, e pode lidar com instâncias muito maior.