Local search algorithms for political districting

Federica Ricca and Bruno Simeone

European Journal of Operational Research, 2008, vol. 189, issue 3, 1409-1426

Abstract: Electoral district planning plays an important role in a political election, especially when a majority voting rule is adopted, because it interferes in the translation of votes into seats. The practice of gerrymandering can easily take place if the shape of electoral districts is not controlled. In this paper we consider the following formulation of the political districting problem: given a connected graph (territory) with n nodes (territorial units), partition its set of nodes into k classes such that the subgraph induced by each class (district) is connected and a given vector of functions of the partition is minimized. The nonlinearity of such functions and the connectivity constraints make this network optimization problem a very hard one. Thus, the use of local search heuristics is justified. Experimentation on a sample of medium-large real-life instances has been carried out in order to compare the performance of four local search metaheuristics, i.e., Descent, Tabu Search, Simulated Annealing, and Old Bachelor Acceptance. Our experiments with Italian political districting provided strong evidence in favor of the use of automatic procedures. Actually, except for Descent, all local search algorithms showed a very good performance for this problem. In particular, in our sample of regions, Old Bachelor Acceptance produced the best results in the majority of the cases, especially when the objective function was compactness. Moreover, the district maps generated by this heuristic dominate the institutional district plan with respect to all the districting criteria under consideration. When properly designed, automatic procedures tend to be impartial and yield good districting alternatives. Moreover, they are remarkably fast, and thus they allow for the exploration of a large number of scenarios.

Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00627-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:189:y:2008:i:3:p:1409-1426

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().