Redistricting by Square Cells | SpringerLink
Skip to main content
Springer Nature Link
Log in

Redistricting by Square Cells

  • Conference paper
MICAI 2009: Advances in Artificial Intelligence (MICAI 2009)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 5845))

Included in the following conference series:

  • 1622 Accesses

Abstract

The design of electoral zones is a complex problem in which democracy of the electoral processes is promoted by some constraints such as population balance, contiguity and compactness. In fact, the computational complexity of zone design problems has been shown to be NP-Hard. This paper propose the use of a new measure of compactness, which uses a mesh formed with square cells to measure the quality of the electoral zones. Finally, a practical real case was chosen, which topographical settings causes some traditional measures of compactness to give very poor quality results, and was designed an algorithm based on simulated annealing that realizes a search in the space of feasible solutions. The results show that the new measure favors the creation of zones with straight forms and avoids twisted or dispersed figures, without an important effect to the population balance, which are considered zones of high quality.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Caro, F., Shirabe, T., Guignard, M., Weintraub, A.: School Redistricting: Embedding GIS Tools with Integer Programming. Journal of the Operational Research Society 55, 836–849 (2004)

    Article  MATH  Google Scholar 

  2. DesJardins, M., Bulka, B., Carr, R., Jordan, E., Rheingans, P.: Heuristic Search and Information Visualization Methods for School Redistricting. AI Magazine 28(3), 59–72 (2006)

    Google Scholar 

  3. Ríos-Mercado, R.Z., Fernández, E.: A Reactive GRASP for Comercial Territory Design Problem with Multiple Balancing Requirements. Computers & Operations Research 36, 755–776 (2009)

    Article  MATH  Google Scholar 

  4. Tavares-Pereira, F., Rui, J., Mousseau, V., Roy, B.: Multiple Criteria Districting Problems: The Public Transportation Network Pricing System of the Paris Region. Ann. Oper. Res. 154, 69–92 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  5. D’Amico, S., Wang, S., Batta, R., Rump, C.: A Simulated Annealing Approach to Police District Design. Computers & Operations Research 29, 667–684 (2002)

    Article  MATH  Google Scholar 

  6. Blais, M., Lapierre, S.D., Laporte, G.: Solving a Home-Care Districting Problem in an Urban Setting. Journal of the Operational Research Society 54, 1141–1147 (2003)

    Article  MATH  Google Scholar 

  7. Shortt, N.K., Moore, A., Coombes, M., Wymer, C.: Defining Regions for Locality Health Care Planning: A Multidimensional Approach. Social Science & Medicine 60, 2715–2727 (2005)

    Article  Google Scholar 

  8. Macmillan, W.: Redistricting in a GIS environment: An Optimisation Algorithm Using Switching-Points. Journal of geographical systems 3, 167–180 (2001)

    Article  Google Scholar 

  9. Williams, J.C.: A Zero-One Programming Model for Contiguous Land Acquisition. Geographical Analysis 34(4), 330–349 (2002)

    Article  Google Scholar 

  10. Bong, C.W., Wang, Y.C.: A Multi-Objective Hybrid Metaheuristic for Zone Definition Procedure. Int. J. Services Operations and Informatics. 1(1/2), 146–164 (2006)

    Google Scholar 

  11. Bozkaya, B., Erkut, E., Laporte, G.: A Tabu Search Heuristic and Adaptive Memory Procedure for Political Districting. European Journal of Operational Research 44, 12–26 (2003)

    Article  Google Scholar 

  12. Altman, M.: Is Automation the Answer: The Computational Complexity of Automated Redistricting. Rutgers Computer and Law Technology Journal 23(1), 81–141 (1997)

    Google Scholar 

  13. Gilbert, K.C., Holmes, D.D., Rosenthal, R.E.: A Multiobjective Discrete Optimization Model for Land Allocation. Management Science 31(12), 1509–1522 (1985)

    Article  Google Scholar 

  14. Vickrey, W.: On The Prevention of Gerrymandering. Political Science Quarterly 76(1), 105–110 (1961)

    Article  Google Scholar 

  15. Weaver, J.B., Hess, S.W.: A Procedure for Nonpartisan Districting: Development of Computer Techniques. The Yale Law Journal 73(2), 288–308 (1963)

    Article  Google Scholar 

  16. Hess, S.W., Weaver, J.B., Siegfeldt, H.J., Whelan, J.N., Zitlau, P.A.: Nonpartisan Political Redistricting by Computer. Operations Research 13(6), 998–1006 (1965)

    Article  Google Scholar 

  17. Niemi, R.G., Grofman, B., Carlucci, C., Hofeller, T.: Measuring Compactness and the Role of a Compactness Standard in a Test for Partisian and Racial Gerrymandering. Journal of Politics 52(4), 1155–1181 (1990)

    Article  Google Scholar 

  18. Young, H.P.: Measuring the Compactness of Legislative Districts. Legislative Studies Quarterly 13(1), 105–115 (1988)

    Article  Google Scholar 

  19. Shirabe, T.: A Model of Contiguity for Spatial Unit Allocation. Geographical Analysis 37, 2–16 (2005)

    Article  Google Scholar 

  20. Kirkpatrick, S., Gellat, C.D., Vecchi, M.P.: Optimization by Simulated Annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  Google Scholar 

  21. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of State Calculation by Fast Computing Machines. Journal of Chemistry Physics 21, 1087–1091 (1953)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Ingeniería Eléctrica, 1 Universidad Autónoma Metropolitana, Av. San Rafael Atlixco 186 Col. Vicentina, 09340, México, D.F.

    Miguel Ángel Gutiérrez Andrade

  2. Facultad de Ingeniería, DIMEI - Departamento de Sistemas, Universidad Nacional Autónoma de México, Ciudad Universitaria, 04510, México, D.F.

    Eric Alfredo Rincón García

Authors
  1. Miguel Ángel Gutiérrez Andrade
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eric Alfredo Rincón García
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Centro de Investigación en Matemáticas, AC. (CIMAT), Area de Computación, Calle Jalisco S/N, Mineral de Valenciana, Guanajuato, CP 36250, Guanajuato, México

    Arturo Hernández Aguirre

  2. Ciencias de la Computación, Tecnológico de Monterrey, Campus Estado de México, Carretera al lago de Guadalupe Km 3,5, Col. Margarita Maza de Juárez, Atizapán de Zaragoza,, CP 52926, Estado de México, México

    Raúl Monroy Borja

  3. Instituto Nacional de Astrofísica, Optica y Electrónica (INAOE), Ciencias Computacionales, Luis Enrique Erro No. 1, Santa María Tonantzintla, CP 72840, Puebla, México

    Carlos Alberto Reyes Garciá

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Andrade, M.Á.G., García, E.A.R. (2009). Redistricting by Square Cells. In: Aguirre, A.H., Borja, R.M., Garciá, C.A.R. (eds) MICAI 2009: Advances in Artificial Intelligence. MICAI 2009. Lecture Notes in Computer Science(), vol 5845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05258-3_59

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-05258-3_59

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-05257-6

  • Online ISBN: 978-3-642-05258-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation