Heuristic algorithms for districting problems

Abstract

In this thesis we study districting, a general class of optimization problem which asks for the grouping of small geographical units into disjoint clusters, called districts. Districting problems appear in a wide variety of applications, ranging from political districting for elections, to service districting for the distribution of commercial prod ucts or the provision of urban services, to the allocation of parcels of farmland into lots. Across the many domains three core requirements are almost always present: that districts be contiguous, geometrically compact, and mutually balanced with re spect to attributes associated to the units. Given the broad range of applications, however, these and other planning criteria have been modelled mathematically in different ways, which has led to many distinct optimization problems. In the first part of this thesis, we review in detail the different formulations and common solution methods found in the districting literature. Since the core problem of finding balanced and connected partitions is NP-hard, so lution methods for districting have so far focused on heuristics. However, upon review we find that methods are typically developed independently, with a focus on appli cations. In the second part of this thesis we look at districting from an application independent point of view. We propose an extendable heuristic framework that can solve a large set of districting problem variants, and apply it to the three versions of the problem that consider different objective functions for minimizing dispersion, namely a p-median, a p-center and diameter function. In separate analyses, we fur ther extend it towards domain-specific criteria, like routing costs and redistricting. Our heuristic is competitive when compared to other methods which are tailored to a single variant, and improves best known bounds in many cases. One particular problem which originates in the design of waste collection territo ries is called the Maximum Dispersion Problem. Differently from classical districting problems, it asks for maximally dispersed rather than compact partitions. The third part of this thesis focuses on solving the Maximum Dispersion Problem. We propose a hybrid heuristic for it which combines a number of components with proven effec tiveness in the literature, as well as a new upper bounding scheme. Despite being a heuristic our method finds optimal solutions more often than a current exact ap proach, and can handle much larger instances.

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.