IDEAS home Printed from
   My bibliography  Save this article

Local search algorithms for political districting


  • Ricca, Federica
  • Simeone, Bruno


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.

Suggested Citation

  • Ricca, Federica & Simeone, Bruno, 2008. "Local search algorithms for political districting," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1409-1426, September.
  • Handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:1409-1426

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Pierre Hansen & Brigitte Jaumard & Christophe Meyer & Bruno Simeone & Valeria Doring, 2003. "Maximum Split Clustering Under Connectivity Constraints," Journal of Classification, Springer;The Classification Society, vol. 20(2), pages 143-180, September.
    2. R. S. Garfinkel & G. L. Nemhauser, 1970. "Optimal Political Districting by Implicit Enumeration Techniques," Management Science, INFORMS, vol. 16(8), pages 495-508, April.
    3. Anuj Mehrotra & Ellis L. Johnson & George L. Nemhauser, 1998. "An Optimization Based Heuristic for Political Districting," Management Science, INFORMS, vol. 44(8), pages 1100-1114, August.
    4. Bozkaya, Burcin & Erkut, Erhan & Laporte, Gilbert, 2003. "A tabu search heuristic and adaptive memory procedure for political districting," European Journal of Operational Research, Elsevier, vol. 144(1), pages 12-26, January.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Yanık, Seda & Sürer, Özge & Öztayşi, Başar, 2016. "Designing sustainable energy regions using genetic algorithms and location-allocation approach," Energy, Elsevier, vol. 97(C), pages 161-172.
    2. repec:spr:annopr:v:258:y:2017:i:2:d:10.1007_s10479-016-2255-8 is not listed on IDEAS
    3. Photis, Yorgos N., 2012. "Redefinition of the Greek electoral districts through the application of a region-building algorithm," MPRA Paper 42398, University Library of Munich, Germany, revised Oct 2012.
    4. repec:spr:coopap:v:69:y:2018:i:1:d:10.1007_s10589-017-9936-3 is not listed on IDEAS
    5. repec:spr:cejnor:v:25:y:2017:i:4:d:10.1007_s10100-016-0454-7 is not listed on IDEAS
    6. María Salazar-Aguilar & Roger Ríos-Mercado & Mauricio Cabrera-Ríos, 2011. "New Models for Commercial Territory Design," Networks and Spatial Economics, Springer, vol. 11(3), pages 487-507, September.
    7. Bruno, Giuseppe & Genovese, Andrea & Piccolo, Carmela, 2017. "Territorial amalgamation decisions in local government: Models and a case study from Italy," Socio-Economic Planning Sciences, Elsevier, vol. 57(C), pages 61-72.
    8. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.

    More about this item


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:1409-1426. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.