{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T05:11:12Z","timestamp":1739941872640,"version":"3.37.3"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Spatial aggregation is essential for applications where data at low level spatial units such as census blocks are grouped into larger regions. This type of problem can be formulated as spatial optimization problems where the goal is to minimize the difference between the grouped regions. These problems are difficult to solve because of their computational intensity. In addition, these problems often have multiple, instead of singular, optimal solutions that have the same or similar objective function values but exhibit different spatial configurations. Existing solution methods often aim to find single solutions to these problems. In this paper, we discuss a new heuristic method that can be used to find a set of unique optimal or near-optimal solutions to spatial aggregation problems. The algorithm consists of two phases. A multistart phase first generates a pool of random solutions to a problem. The size of the pool is specified by the user and contains the number of solutions desired to be found. Each random solution is then improved using an efficient algorithm called give-and-take. The second phase uses a recombination algorithm to create new solutions based on solutions randomly selected from the pool. The worst solution in the pool will be replaced by the new solution if the latter is better and does not exist in the pool. We test this multistart and recombination algorithm (MSRA) using a variety of problems with different sizes and the results suggest the effectiveness of the algorithm in finding multiple unique optimal or near-optimal solutions.<\/jats:p>","DOI":"10.1007\/s10707-024-00520-0","type":"journal-article","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:03:35Z","timestamp":1716275015000},"page":"53-91","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A multistart and recombination algorithm for finding many unique solutions to spatial aggregation problems"],"prefix":"10.1007","volume":"29","author":[{"given":"Ningchuan","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Myung Jin","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Yue","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,21]]},"reference":[{"key":"520_CR1","volume-title":"Political Redistricting and Geographic Theory","author":"RL Morrill","year":"1981","unstructured":"Morrill RL (1981) Political Redistricting and Geographic Theory. Association of American Geographers, Washington, D. C"},{"issue":"1","key":"520_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/j.1435-5597.1995.tb00626.x","volume":"74","author":"JC Williams Jr","year":"1995","unstructured":"Williams JC Jr (1995) Political redistricting: a review. Pap Reg Sci 74(1):13\u201340","journal-title":"Pap Reg Sci"},{"key":"520_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S1344-6223(02)00033-0","volume":"36","author":"PK Bergey","year":"2003","unstructured":"Bergey PK, Ragsdale CT, Hoskote M (2003) A decision support system for the electrical power districting problem. Decis Support Syst 36:1\u201317","journal-title":"Decis Support Syst"},{"key":"520_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cor.2013.08.002","volume":"41","author":"LS De Assis","year":"2014","unstructured":"De Assis LS, Franca PM, Usberti FL (2014) A redistricting problem applied to meter reading in power distribution networks. Comput Oper Res 41:65\u201375","journal-title":"Comput Oper Res"},{"issue":"1","key":"520_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1287\/opre.38.1.15","volume":"38","author":"JA Ferland","year":"1990","unstructured":"Ferland JA, Gu\u00e9nette G (1990) Decision support system for the school districting problem. Oper Res 38(1):15\u201321","journal-title":"Oper Res"},{"unstructured":"Biswas S (2022) Spatial optimization techniques for school redistricting. PhD thesis, Virginia Tech","key":"520_CR6"},{"doi-asserted-by":"crossref","unstructured":"Benzarti E, Sahin E, Dallery Y (2013) Operations management applied to home care services: analysis of the districting problem. Decis Support Syst 55(2):587\u2013598","key":"520_CR7","DOI":"10.1016\/j.dss.2012.10.015"},{"unstructured":"U.S. Census Bureau (2021) TIGER\/Line shapefiles technical documentation. Tech Rep","key":"520_CR8"},{"doi-asserted-by":"crossref","unstructured":"Kalcsics J, R\u00edos-Mercado RZ (2019) Districting problems. In: Laporte, G., Nickel, S., Saldanha\u00a0da Gama, F. (eds.) Location Science, Springer, Cham, pp 705\u2013743","key":"520_CR9","DOI":"10.1007\/978-3-030-32177-2_25"},{"issue":"4","key":"520_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/IJAGR.2017100101","volume":"8","author":"MJ Kim","year":"2017","unstructured":"Kim MJ, Xiao N (2017) Contiguity-based optimization models for political redistricting problems. Int J Appl Geospatial Res 8(4):1\u201318","journal-title":"Int J Appl Geospatial Res"},{"key":"520_CR11","doi-asserted-by":"publisher","first-page":"208","DOI":"10.7208\/chicago\/9780226159409.001.0001","volume-title":"Bushmanders & Bullwinkles","author":"M Monmonier","year":"2001","unstructured":"Monmonier M (2001) Bushmanders & Bullwinkles. The University of Chicago Press, Chicago, p 208"},{"unstructured":"Toobin J (2003) The great election grab: When does gerrymandering become a threat to democracy? New Yorker (December 8):63\u201380","key":"520_CR12"},{"unstructured":"Epstein RJ (2021) Possible Map For Illinois Aims to Grab G.O.P. Seats. The New York Times (October 16):15","key":"520_CR13"},{"unstructured":"McKinley J (2022) Man Behind the Maps: New York\u2019s Most Unexpected Power Broker. The New York Times (May 29):13","key":"520_CR14"},{"key":"520_CR15","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1287\/mnsc.16.8.B495","volume":"16","author":"RS Garfinkel","year":"1970","unstructured":"Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Manage Sci 16:495\u2013508","journal-title":"Manage Sci"},{"issue":"1","key":"520_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1111\/j.1538-4632.2005.00605.x","volume":"37","author":"T Shirabe","year":"2005","unstructured":"Shirabe T (2005) A model of contiguity for spatial unit allocation. Geogr Anal 37(1):2\u201316","journal-title":"Geogr Anal"},{"issue":"1","key":"520_CR17","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1111\/j.1538-4632.2010.00810.x","volume":"43","author":"JC Duque","year":"2011","unstructured":"Duque JC, Church RL, Middleton RS (2011) The $$p$$-regions problem. Geogr Anal 43(1):104\u2013126","journal-title":"Geogr Anal"},{"doi-asserted-by":"publisher","unstructured":"Duque JC, Ramos R, Suri\u00f1ach J (2007) Supervised regionalization methods: a survey. Int Reg Sci Rev 30(3):195\u2013220. https:\/\/doi.org\/10.1177\/0160017607301605","key":"520_CR18","DOI":"10.1177\/0160017607301605"},{"issue":"6","key":"520_CR19","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1068\/b34104","volume":"36","author":"T Shirabe","year":"2009","unstructured":"Shirabe T (2009) Districting modeling with exact contiguity constraints. Environment and Planning B, Planning & Design 36(6):1053\u20131066","journal-title":"Environment and Planning B, Planning & Design"},{"key":"520_CR20","doi-asserted-by":"publisher","first-page":"288","DOI":"10.2307\/794769","volume":"73","author":"JB Weaver","year":"1963","unstructured":"Weaver JB, Hess S (1963) A procedure for non-partisan districting. Yale Law J 73:288\u2013309","journal-title":"Yale Law J"},{"key":"520_CR21","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1287\/opre.13.6.998","volume":"13","author":"SW Hess","year":"1965","unstructured":"Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Nonpartisan political redistricting by computer. Oper Res 13:998\u20131006","journal-title":"Oper Res"},{"key":"520_CR22","doi-asserted-by":"publisher","first-page":"863","DOI":"10.2307\/1226994","volume":"17","author":"SS Nagel","year":"1965","unstructured":"Nagel SS (1965) Simplified bipartisan computer redistricting. Stanford Law Review 17:863\u2013899","journal-title":"Stanford Law Review"},{"key":"520_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1111\/j.1749-6632.1973.tb41402.x","volume":"219","author":"JM Liittschwager","year":"1973","unstructured":"Liittschwager JM (1973) The iowa redistricting system. Ann N Y Acad Sci 219:221\u2013235","journal-title":"Ann N Y Acad Sci"},{"key":"520_CR24","first-page":"221","volume-title":"Spatial Analysis and GIS","author":"W Macmillan","year":"1994","unstructured":"Macmillan W, Pierce T (1994) Optimization modelling in a GIS framework: the problem of political redistricting. In: Fotheringham S, Rogerson P (eds) Spatial Analysis and GIS. Taylor & Francis, London, pp 221\u2013246"},{"key":"520_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1068\/a270425","volume":"27","author":"S Openshaw","year":"1995","unstructured":"Openshaw S, Rao L (1995) Algorithms for reengineering 1991 census geography. Environ Plan A 27:425\u2013446","journal-title":"Environ Plan A"},{"issue":"4","key":"520_CR26","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1080\/00045600802232458","volume":"98","author":"N Xiao","year":"2008","unstructured":"Xiao N (2008) A unified conceptual framework for geographical optimization using evolutionary algorithms. Ann Assoc Am Geogr 98(4):795\u2013817","journal-title":"Ann Assoc Am Geogr"},{"doi-asserted-by":"crossref","unstructured":"Guo D, Jin H (2011) iredistrict: geovisual analytics for redistricting optimization. Journal of Visual Languages & Computing 22(4):279\u2013289","key":"520_CR27","DOI":"10.1016\/j.jvlc.2011.03.001"},{"key":"520_CR28","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.swevo.2016.04.004","volume":"30","author":"YY Liu","year":"2016","unstructured":"Liu YY, Cho WKT, Wang S (2016) PEAR: a massively parallel evolutionary computation approach for political redistricting optimization and analysis. Swarm Evol Comput 30:78\u201392","journal-title":"Swarm Evol Comput"},{"issue":"1","key":"520_CR29","first-page":"81","volume":"23","author":"M Altman","year":"1995","unstructured":"Altman M (1995) Is automation the answer? - the computational complexity of automated redistricting. Rutgers Comput Technol Law J 23(1):81\u2013142","journal-title":"Rutgers Comput Technol Law J"},{"doi-asserted-by":"crossref","unstructured":"Altman M, MacDonald K, McDonald M (2005) From crayons to computers: the evolution of computer use in redistricting. Soc Sci Comput Rev 23(3):334\u2013346","key":"520_CR30","DOI":"10.1177\/0894439305275855"},{"issue":"12","key":"520_CR31","doi-asserted-by":"publisher","first-page":"2729","DOI":"10.1016\/j.socscimed.2004.11.005","volume":"60","author":"S Cockings","year":"2005","unstructured":"Cockings S, Martin D (2005) Zone design for environment and health studies using pre-aggregated data. Soc Sci Med 60(12):2729\u20132742","journal-title":"Soc Sci Med"},{"issue":"4","key":"520_CR32","doi-asserted-by":"publisher","first-page":"3300","DOI":"10.1214\/23-AOAS1763","volume":"17","author":"C McCartan","year":"2023","unstructured":"McCartan C, Imai K (2023) Sequential monte carlo for sampling balanced and compact redistricting plans. Ann Appl Stat 17(4):3300\u20133323","journal-title":"Ann Appl Stat"},{"doi-asserted-by":"crossref","unstructured":"DeFord D, Duchin M, Solomon J (2021) Recombination: a family of markov chains for redistricting. Harvard Data Sci Rev 3(1):3","key":"520_CR33","DOI":"10.1162\/99608f92.eb30390f"},{"doi-asserted-by":"crossref","unstructured":"Dobbs KW, King DM, Jacobson SH (2023) Redistricting optimization with recombination: a local search case study. Comput Oper Res 160:106369","key":"520_CR34","DOI":"10.1016\/j.cor.2023.106369"},{"issue":"5","key":"520_CR35","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s41324-019-00254-4","volume":"27","author":"MJ Kim","year":"2019","unstructured":"Kim MJ (2019) Give-and-take heuristic model to political redistricting problems. Spat Inf Res 27(5):539\u2013552","journal-title":"Spat Inf Res"},{"issue":"2","key":"520_CR36","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/jcph.1999.6413","volume":"159","author":"G Schrimpf","year":"2000","unstructured":"Schrimpf G, Schneider J, Stamm-Wilbrandt H, Dueck G (2000) Record breaking optimization results using the ruin and recreate principle. J Comput Phys 159(2):139\u2013171","journal-title":"J Comput Phys"},{"key":"520_CR37","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"520_CR38","first-page":"336","volume-title":"GIS Algorithms","author":"N Xiao","year":"2016","unstructured":"Xiao N (2016) GIS Algorithms. SAGE Publications, London, p 336"},{"doi-asserted-by":"crossref","unstructured":"Hagberg A, Swart P, S\u00a0Chult D (2008) Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th python in science conference, Pasadena, CA, pp 11\u201316","key":"520_CR39","DOI":"10.25080\/TCWV9851"},{"issue":"2","key":"520_CR40","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/MCSE.2007.35","volume":"9","author":"PF Gorder","year":"2007","unstructured":"Gorder PF (2007) Multicore processors for science and engineering. Comput Sci Eng 9(2):3\u20137","journal-title":"Comput Sci Eng"},{"unstructured":"Bolender D, Cook E (2000) Second redistricting plan. Report to secretary of the iowa senate, Iowa Legislative Service Bureau. Online. https:\/\/www.legis.iowa.gov\/docs\/resources\/redist\/2001\/June2001report.htm. Accessed 11 Feb 2023","key":"520_CR41"},{"unstructured":"Kim MJ (2011) Optimization approaches to political redistricting problems. PhD thesis, The Ohio State University, Columbus, OH","key":"520_CR42"},{"doi-asserted-by":"crossref","unstructured":"Kenny CT, Kuriwaki S, McCartan C, Rosenman ET, Simko T, Imai K (2021) The use of differential privacy for census data and its impact on redistricting: the case of the 2020 us census. Sci Adv 7(41):3283","key":"520_CR43","DOI":"10.1126\/sciadv.abk3283"},{"unstructured":"Kenny CT, McCartan C, Fifield B, Imai K (2022) redist: simulation methods for legislative redistricting. R package. https:\/\/alarm-redist.org\/redist\/","key":"520_CR44"},{"issue":"8","key":"520_CR45","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1016\/S0962-6298(98)00015-8","volume":"17","author":"M Altman","year":"1998","unstructured":"Altman M (1998) Modeling the effect of mandatory district compactness on partisan gerrymanders. Polit Geogr 17(8):989\u20131012","journal-title":"Polit Geogr"},{"issue":"3","key":"520_CR46","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1111\/ajps.12603","volume":"65","author":"AR Kaufman","year":"2021","unstructured":"Kaufman AR, King G, Komisarchik M (2021) How to measure legislative district compactness if you only know it when you see it. Am J Polit Sci 65(3):533\u2013550","journal-title":"Am J Polit Sci"},{"doi-asserted-by":"crossref","unstructured":"Rossiter KM, Wong DW, Delamater PL (2018) Congressional redistricting: keeping communities together? Prof Geogr 70(4):609\u2013623","key":"520_CR47","DOI":"10.1080\/00330124.2018.1443477"},{"key":"520_CR48","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1146\/annurev-polisci-041719-102107","volume":"25","author":"DT Canon","year":"2022","unstructured":"Canon DT (2022) Race and redistricting. Annu Rev Polit Sci 25:509\u2013528","journal-title":"Annu Rev Polit Sci"},{"doi-asserted-by":"crossref","unstructured":"Xiao N (2018) Considering diversity in spatial decision support systems. In: Thill J-C, Dragi\u0107evi\u0107 S (eds) geocomputational analysis and modeling of regional systems. Springer, Cham, pp 23\u201335","key":"520_CR49","DOI":"10.1007\/978-3-319-59511-5_3"},{"key":"520_CR50","volume-title":"Genetic Algorithms in Search","author":"DE Goldberg","year":"1989","unstructured":"Goldberg DE (1989) Genetic Algorithms in Search. Optimization and Machine Learning. Addison-Wesley, Reading, MA"},{"issue":"3","key":"520_CR51","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1111\/j.1538-4632.2006.00684.x","volume":"38","author":"N Xiao","year":"2006","unstructured":"Xiao N (2006) An evolutionary algorithm for site search problems. Geogr Anal 38(3):227\u2013247","journal-title":"Geogr Anal"},{"issue":"1\u20134","key":"520_CR52","first-page":"35","volume":"35","author":"AE Eiben","year":"1998","unstructured":"Eiben AE, Schippers CA (1998) On evolutionary exploration and exploitation. Fund Inform 35(1\u20134):35\u201350","journal-title":"Fund Inform"},{"doi-asserted-by":"crossref","unstructured":"Crepin\u0161ek M, Liu S-H, Mernik M (2013) Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput Surv 45(3):1\u201333","key":"520_CR53","DOI":"10.1145\/2480741.2480752"},{"issue":"1","key":"520_CR54","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/net.10010","volume":"39","author":"JC Williams","year":"2001","unstructured":"Williams JC (2001) A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs. Networks 39(1):53\u201360","journal-title":"Networks"},{"volume-title":"The Grid 2: Blueprint for a New Computing Infrastructure","year":"2003","unstructured":"Foster I, Kesselman C (eds) (2003) The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Francisco","key":"520_CR55"},{"key":"520_CR56","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84996-241-4","volume-title":"Cloud Computing","author":"N Antonopoulos","year":"2010","unstructured":"Antonopoulos N, Gillam L (2010) Cloud Computing. Springer, London"},{"key":"520_CR57","first-page":"41","volume-title":"The Modifiable Areal Unit Problem","author":"S Openshaw","year":"1983","unstructured":"Openshaw S (1983) The Modifiable Areal Unit Problem. Geo Books, Norwich, p 41"},{"unstructured":"Longley PA, Goodchild MF, Maguire DJ, Rhind DW (eds) (1997) Geographic Information Systems: Princeples, Techniques. Applications and Management. Wiley, New York","key":"520_CR58"},{"issue":"7","key":"520_CR59","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1080\/136588198241590","volume":"12","author":"D Martin","year":"1998","unstructured":"Martin D (1998) Optimizing census geography: the separation of collection and output geographies. Int J Geogr Inf Syst 12(7):673\u2013685","journal-title":"Int J Geogr Inf Syst"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-024-00520-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-024-00520-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-024-00520-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T09:19:30Z","timestamp":1739870370000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-024-00520-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["520"],"URL":"https:\/\/doi.org\/10.1007\/s10707-024-00520-0","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"type":"print","value":"1384-6175"},{"type":"electronic","value":"1573-7624"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"12 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}