## 1. Introduction

## 2. Modeling Concerns

## 3. Capacitated Double p-Median Problem with Preference

- $i,j,k=\mathrm{index}\mathrm{of}\mathrm{basic}\mathrm{spatial}\mathrm{units},i,j,k=1,\dots ,n$,
- $l=\mathrm{index}\mathrm{of}\mathrm{potential}\mathrm{facilities},l=1,\dots ,m$,
- ${a}_{i}=\mathrm{demand}\mathrm{of}\mathrm{basic}\mathrm{spatial}\mathrm{unit}i$,
- ${d}_{ik}=\mathrm{distance}\mathrm{between}\mathrm{basic}\mathrm{spatial}\mathrm{unit}i\mathrm{and}k\mathrm{selected}\mathrm{as}\mathrm{the}\mathrm{center}\mathrm{of}\mathrm{a}\mathrm{precinct}$,
- ${d}_{kl}=\mathrm{distance}\mathrm{between}\mathrm{basic}\mathrm{spatial}\mathrm{unit}\mathrm{selected}\mathrm{as}\mathrm{a}\mathrm{center}k\mathrm{and}\mathrm{a}\mathrm{facility}l$,
- $p{r}_{l}=\mathrm{preference}\mathrm{of}\mathrm{facility}l$,
- $\beta =\mathrm{preference}\mathrm{impact}\mathrm{factor}$,
- $p=\mathrm{number}\mathrm{of}\mathrm{precincts}\mathrm{to}\mathrm{be}\mathrm{delineated}$,
- ${C}_{min}=\mathrm{lower}\mathrm{bound}\mathrm{of}\mathrm{population}$,
- ${N}_{i}=\left\{j|{c}_{ij}=1\right\},\mathrm{a}\mathrm{set}\mathrm{of}\mathrm{spatial}\mathrm{units}\mathrm{that}\mathrm{are}\mathrm{adjacent}\mathrm{to}i$,
- ${c}_{ij}=\{\begin{array}{c}1,\mathrm{basic}\mathrm{spatial}\mathrm{units}i\mathrm{and}j\mathrm{are}\mathrm{adjacent}\\ 0,\mathrm{otherwise}\end{array}$,
- ${f}_{ijk}=\mathrm{the}\mathrm{amount}\mathrm{of}\mathrm{unit}\mathrm{flow}\mathrm{from}i\mathrm{to}j\mathrm{in}\mathrm{a}\mathrm{precinct}\mathrm{centered}\mathrm{on}k$,
- ${x}_{ik}=\{\begin{array}{c}1,\mathrm{if}\mathrm{spatial}\mathrm{unit}i\mathrm{is}\mathrm{assigned}\mathrm{to}\mathrm{center}k\\ 0,\mathrm{otherwise}\end{array}$,
- ${w}_{ik}=\{\begin{array}{c}1,\mathrm{if}\mathrm{spatial}\mathrm{unit}i\mathrm{is}\mathrm{selected}\mathrm{as}\mathrm{a}\mathrm{sink}\mathrm{of}\mathrm{precinct}\mathrm{centered}\mathrm{on}\mathrm{spatial}\mathrm{unit}k\\ 0,\mathrm{otherwise}\end{array}$,
- ${\mathrm{y}}_{ikl}=\{\begin{array}{c}1,\mathrm{if}\mathrm{precinct}\mathrm{with}\mathrm{sink}i\mathrm{and}\mathrm{center}k\mathrm{is}\mathrm{assigned}\mathrm{to}\mathrm{facility}l\\ 0,\mathrm{otherwise}\end{array}$,
- ${z}_{l}=\{\begin{array}{c}1,\mathrm{if}\mathrm{facility}l\mathrm{is}\mathrm{selected}\\ 0,\mathrm{otherwise}\end{array}$.

- $i,k=\mathrm{index}\mathrm{of}\mathrm{basic}\mathrm{spatial}\mathrm{units},i,k=1,\dots ,n$,
- $l=\mathrm{index}\mathrm{of}\mathrm{potential}\mathrm{facilities},l=1,\dots ,m$,
- ${a}_{i}=\mathrm{population}\mathrm{of}\mathrm{basic}\mathrm{spatial}\mathrm{unit}i$,
- ${d}_{ik}=\mathrm{distance}\mathrm{between}\mathrm{basic}\mathrm{spatial}\mathrm{units}i\mathrm{and}k\mathrm{selected}\mathrm{as}\mathrm{the}\mathrm{center}\mathrm{of}\mathrm{a}\mathrm{precinct}$,
- ${d}_{kl}=\mathrm{distance}\mathrm{between}\mathrm{basic}\mathrm{spatial}\mathrm{unit}\mathrm{selected}\mathrm{as}\mathrm{a}\mathrm{center}k\mathrm{and}\mathrm{facility}l$,
- $p{r}_{l}=\mathrm{preference}\mathrm{of}\mathrm{facility}l$,
- $\beta =\mathrm{preference}\mathrm{impact}\mathrm{factor}$,
- $p=\mathrm{number}\mathrm{of}\mathrm{precincts}\mathrm{to}\mathrm{be}\mathrm{delineated}$,
- ${C}_{min}=\mathrm{lower}\mathrm{bound}\mathrm{of}\mathrm{population}$,
- ${x}_{ik}=\{\begin{array}{c}1,\mathrm{if}\mathrm{spatial}\mathrm{unit}i\mathrm{is}\mathrm{assigned}\mathrm{to}\mathrm{basic}\mathrm{spatial}\mathrm{unit}k\mathrm{selected}\mathrm{as}\mathrm{a}\mathrm{center}\\ 0,\mathrm{otherwise}\end{array}$,
- ${w}_{k}=\{\begin{array}{c}1,\mathrm{if}\mathrm{spatial}\mathrm{unit}k\mathrm{is}\mathrm{selected}\mathrm{as}\mathrm{a}\mathrm{center}\\ 0,\mathrm{otherwise}\end{array}$,
- ${\mathrm{y}}_{kl}=\{\begin{array}{c}1,\mathrm{if}\mathrm{selected}\mathrm{center}k\mathrm{is}\mathrm{assigned}\mathrm{to}\mathrm{facility}l\\ 0,\mathrm{otherwise}\end{array}$,
- ${z}_{l}=\{\begin{array}{c}1,\mathrm{if}\mathrm{facility}l\mathrm{is}\mathrm{selected}\\ 0,\mathrm{otherwise}\end{array}$.

## 4. Computational Results

^{2}, the maximum was 0.052 km

^{2}, and the average was 0.008 km

^{2}. The Euclidean distance between the centroids of the basic spatial units and between the basic spatial units and potential facilities were used for analysis. Using network distance may be more realistic. However, the spatial extent of the case area was small (the maximum distance between the basic spatial units was 2990 m and the average distance was 751 m), demand was aggregated into polygons, and most people walk to polling places. For these reasons, alongside the ease of calculation, we used the linear distance. Figure 2 shows the distribution of the voters and the locations of potential facilities within an administrative unit (Seokyo-dong, Mapo-gu, Seoul) that can be itself a single precinct or can be divided into several precincts in Korea. In this figure, the preference of potential facilities was evaluated by considering their histories as polling places in previous elections, the sizes of facilities, and whether facilities were public. The preferences in this map were normalized to values between one and two. As of April 1, 2016, 24,128 voters were in this area. In previous elections, the area was divided into seven precincts and seven polling places were established. The spatial distribution of the voters was represented by reallocating the voters of each precinct proportionally to the number of households in basic spatial units. This approach is similar to the dasymetric technique of estimating the values of small spatial units [34].

_{min}was greater than or equal to 2800.

**A**was reduced. Thus,

**A**was chosen as a polling facility for this precinct instead of

**B**, which was selected from other ß values. That is, when the preference was emphasized, the location of the selected polling facilities could be changed, which could affect the centers of precincts and the allocation of basic spatial units. This change was possible because the reduction in the second term in the minimization objective function was greater than the increase in the first term, which was caused by the allocation of basic spatial units to the non-closest center. These results show that determining the locations of polling facilities and delineating precincts can interact with each other. Therefore, both tasks should be processed simultaneously rather than independently or sequentially.

## 5. Discussion

_{min}= 2800 (in Table 2, seven falling places were selected, spatial contiguity was not violated, and C

_{min}was the largest). As a result, the population range of the precincts ranged from 2800 to 4119. The population deviation was significantly reduced compared to the existing system. In addition, the average distance to the polling places was reduced to 185 m compared to the existing 250 m, resulting in improved access to the polling places. These results suggest that the spatial optimization model developed could support better decision-making regarding election administration.

## 6. Summary and Conclusions

## Funding

## Conflicts of Interest

## References

- Kinsella, C.; McTague, C.; Raleigh, K.N. Unmasking geographic polarization and clustering: A micro-scalar analysis of partisan voting behavior. Appl. Geogr.
**2015**, 62, 404–419. [Google Scholar] [CrossRef] - Shambon, L.; Abouchar, K. Trapped by Precincts? The Help America Vote Act’s Provisional Ballots and the Problem of Precincts. NYUJ Legis. & Pub. Pol’y.
**2006**, 10, 133–194. [Google Scholar] - Dyck, J.J.; Gimpel, J.G. Distance, turnout, and the convenience of voting. Soc. Sci. Q.
**2005**, 86, 531–548. [Google Scholar] [CrossRef] - Stein, R.M.; Vonnahme, G. Voting at non-precinct polling places: A review and research agenda. Elect. Law J.
**2011**, 10, 307–311. [Google Scholar] [CrossRef] - Williams, J.C. Political redistricting: A review. Pap. Reg. Sci.
**1995**, 74, 13–40. [Google Scholar] [CrossRef] - Brady, H.E.; McNulty, J.E. Turning out to vote: The costs of finding and getting to the polling place. Am. Political Sci. Rev.
**2011**, 105, 115–134. [Google Scholar] [CrossRef] - Haspel, M.; Knotts, H.G. Location, location, location: Precinct placement and the costs of voting. J. Politics
**2005**, 67, 560–573. [Google Scholar] [CrossRef] - McNulty, J.E.; Dowling, C.M.; Ariotti, M.H. Driving saints to sin: How increasing the difficulty of voting dissuades even the most motivated voters. Political Anal.
**2009**, 17, 435–455. [Google Scholar] [CrossRef] - Bhatti, Y. Distance and voting: Evidence from Danish municipalities. Scand. Political Stud.
**2012**, 35, 141–158. [Google Scholar] [CrossRef] - Orford, S.; Railings, C.; Thrasher, M.; Borisyuk, G. Changes in the probability of voter turnout when resiting polling stations: A case study in Brent, UK. Environ. Plan.
**2011**, 29, 149–169. [Google Scholar] [CrossRef] - Webb, G. Precinct Size Matters-The Large Precinct Bias in US Presidential Elections. arXiv
**2014**, arXiv:1410.8868. [Google Scholar] - Ghiani, G.; Guerriero, F.; Musmanno, R. The capacitated plant location problem with multiple facilities in the same site. Comput. Oper. Res.
**2002**, 29, 1903–1912. [Google Scholar] [CrossRef] - Konishi, K. Voting simulation for improving voter turnout and reducing the number of polling places. J. Jpn. Soc. Fuzzy Theory Intell. Inform.
**2010**, 22, 203–210. [Google Scholar] - Murata, T.; Konishi, K. Making a practical policy proposal for polling place assignment using voting simulation tool. SICE J. Control Meas. Syst. Integr.
**2013**, 6, 124–130. [Google Scholar] [CrossRef] - Cantoni, E. A precinct too far: Turnout and voting costs. Am. Econ. J.
**2020**, 12, 61–85. [Google Scholar] [CrossRef] - Ross, G.T.; Soland, R.M. A branch and bound algorithm for the generalized assignment problem. Math. Program.
**1975**, 8, 91–103. [Google Scholar] [CrossRef] - Kim, H.; Kim, K. Spatial Optimization Problem for Locating Polling Facilities and Stations and Policy Implications. In Optimal Districting and Territory Design; Ríos-Mercado, R.Z., Ed.; Springer: Cham, Switzerland, 2020; pp. 173–190. [Google Scholar]
- Hanjoul, P.; Peeters, D. A facility location problem with clients’ preference orderings. Reg. Sci. Urban Econ.
**1987**, 17, 451–473. [Google Scholar] [CrossRef] - Vasilyev, I.L.; Klimentova, K.B. The branch and cut method for the facility location problem with client’s preferences. J. Appl. Ind. Math.
**2010**, 4, 441–454. [Google Scholar] [CrossRef] - Camacho-Vallejo, J.F.; Casas-Ramírez, M.S.; Miranda, P. The p-Median bilevel problem under preferences of the customers. In Recent Advances in Theory, Methods and Practice of Operations Research; Ríos-Mercado, R., Camacho-Vallejo, J.-F., Gonzalez-Velarde, J., Laguna, M., Eds.; UANL: Monterrey, Mexico, 2014; pp. 121–127. [Google Scholar]
- Brunner, J.A.; Mason, J.L. The influence of driving time upon shopping center preference. J. Mark.
**1968**, 32, 57–61. [Google Scholar] [CrossRef] - Duque, J.C.; Anselin, L.; Rey, S.J. The max-p-regions problem. J. Reg. Sci.
**2012**, 52, 397–419. [Google Scholar] [CrossRef] - Kalcsics, J. Districting Problems. In Location Science; Laporte, G., Nickel, S., Saldanha da Gama, F., Eds.; Springer: Cham, Switzerland, 2015; pp. 595–622. [Google Scholar]
- Kim, H.; Chun, Y.; Kim, K. Delimitation of Functional Regions Using a p-Regions Problem Approach. Int. Reg. Sci. Rev.
**2015**, 38, 235–263. [Google Scholar] [CrossRef] - Shirabe, T. A model of contiguity for spatial unit allocation. Geogr. Anal.
**2005**, 37, 2–16. [Google Scholar] [CrossRef] - Shirabe, T. Districting modeling with exact contiguity constraints. Environ. Plan. B Plan. and Des.
**2009**, 36, 1053–1066. [Google Scholar] [CrossRef] - Pirkul, H.; Schilling, D.A. The siting of emergency service facilities with workload capacities and backup service. Manag. Sci.
**1988**, 34, 896–908. [Google Scholar] [CrossRef] - Hakimi, S.L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper. Res.
**1965**, 13, 462–475. [Google Scholar] [CrossRef] - Church, R.L. The Regionally Constrained p-Median Problem. Geogr. Anal.
**1990**, 22, 22–32. [Google Scholar] [CrossRef] - Gerrard, R.A.; Church, R.L. A general construct for the zonally constrained p-median problem. Environ. Plan. B
**1995**, 22, 213–236. [Google Scholar] [CrossRef] - Murray, A.T.; Gerrard, R.A. Capacitated service and regional constraints in location-allocation modeling. Locat. Sci.
**1997**, 5, 103–118. [Google Scholar] [CrossRef] - Public Official Election Act. Available online: https://elaw.klri.re.kr/ (accessed on 7 October 2019).
- Christaller, W. Die Zentralen Orte in Süddeutschland. Central Places in Southern Germany; Baskin, C.W., Translator; Prentice-Hall: Englewood Cliffs, NJ, USA, 1966. [Google Scholar]
- Pavía, J.M.; Cantarino, I. Dasymetric distribution of votes in a dense city. Appl. Geogr.
**2017**, 86, 22–31. [Google Scholar] [CrossRef] - Openshaw, S.; Rao, L. Algorithms for reengineering 1991 Census geography. Environ. Plan. A
**1995**, 27, 425–446. [Google Scholar] [CrossRef] - Macmillan, W.; Pierce, T. Optimization modelling in a GIS framework: The problem of political redistricting. In Spatial analysis and GIS; Fotheringham, S., Rogerson, P., Eds.; Taylor & Francis: London, UK, 1994; pp. 221–246. [Google Scholar]
- Macmillan, W. Redistricting in a GIS environment: An optimisation algorithm using switching-points. J. Geogr. Syst.
**2001**, 3, 167–180. [Google Scholar] [CrossRef] - Kim, K.; Dean, D.J.; Kim, H.; Chun, Y. Spatial optimization for regionalization problems with spatial interaction: A heuristic approach. Int. J. Geogr. Inf. Sci.
**2016**, 30, 451–473. [Google Scholar] [CrossRef] - D’Amico, S.J.; Wang, S.J.; Batta, R.; Rump, C.M. A simulated annealing approach to police district design. Comput. Oper. Res.
**2002**, 29, 667–684. [Google Scholar] [CrossRef] - Bozkaya, B.; Erkut, E.; Laporte, G. A tabu search heuristic and adaptive memory procedure for political districting. Eur. J. Oper. Res.
**2003**, 144, 12–26. [Google Scholar] [CrossRef] - Bacao, F.; Lobo, V.; Painho, M. Applying genetic algorithms to zone design. Soft Comput.
**2005**, 9, 341–348. [Google Scholar] [CrossRef] - Murray, A.T. Advances in location modeling: GIS linkages and contributions. J. Geogr. Syst.
**2010**, 12, 335–354. [Google Scholar] [CrossRef] - Caro, F.; Shirabe, T.; Guignard, M.; Weintraub, A. School redistricting: Embedding GIS tools with integer programming. J. Oper. Res. Soc.
**2004**, 55, 836–849. [Google Scholar] [CrossRef]

**Figure 1.**Double location-allocation process of the capacitated double p-median problem with preference (CDPMP-P).

**Figure 3.**Role of the contiguity constraints in the CDPMP-P: (

**a**) without contiguity constraints; (

**b**) with contiguity constraints.

Contiguity Constraints | ß | C_{min} | Objective Value | Time (s) | Node | Iteration | IDs of Selected Facilities |
---|---|---|---|---|---|---|---|

Without | 3 | 750 | 95.601 | 0.12 | 0 | 46 | 2, 6 |

With | 3 | 750 | 97.151 | 2.54 | 1467 | 69,818 | 2, 6 |

ß | C_{min} | Objective Value | Time (s) | Node | Iteration | Contiguity Violation | IDs of Selected Polling Facilities |
---|---|---|---|---|---|---|---|

0 | 2500 | 3645.116 | 8.82 | 71 | 3,250 | No | 15, 18, 24, 26, 28, 32, 38 |

0 | 2600 | 3657.363 | 7.58 | 2 | 2,603 | No | 15, 18, 24, 26, 28, 32, 38 |

0 | 2700 | 3679.259 | 4.98 | 0 | 337 | No | 15, 18, 24, 26, 28, 32, 38 |

0 | 2800 | 3714.938 | 10.05 | 149 | 12,479 | No | 15, 18, 24, 26, 28, 32, 38 |

0 | 2900 | 3756.439 | 17.72 | 129 | 34,111 | Yes | 15, 18, 24, 26, 28, 32, 38 |

0 | 3000 | 3863.127 | 3007.76 | 26,212 | 3,975,306 | Yes | 15, 18, 24, 26, 28, 32, 38 |

1 | 2500 | 3631.458 | 11.12 | 193 | 11,411 | Yes | 15, 18, 24, 26, 28, 31, 32 |

1 | 2600 | 3644.737 | 7.91 | 18 | 1,095 | No | 15, 18, 24, 26, 28, 32, 38 |

1 | 2700 | 3666.633 | 6.33 | 0 | 487 | No | 15, 18, 24, 26, 28, 32, 38 |

1 | 2800 | 3702.053 | 9.92 | 161 | 9,086 | No | 15, 18, 24, 26, 28, 32, 38 |

1 | 2900 | 3743.593 | 21.56 | 283 | 58,893 | Yes | 15, 18, 24, 26, 28, 32, 38 |

1 | 3000 | 3846.118 | 1999.23 | 13,909 | 2,325,943 | Yes | 15, 18, 24, 26, 28, 32, 38 |

2 | 2500 | 3616.215 | 10.14 | 84 | 6,127 | No | 15, 18, 24, 26, 28, 31, 32 |

2 | 2600 | 3634.916 | 9.39 | 59 | 4,945 | No | 15, 18, 24, 26, 28, 32, 38 |

2 | 2700 | 3656.812 | 8.53 | 17 | 1,341 | No | 15, 18, 24, 26, 28, 32, 38 |

2 | 2800 | 3691.677 | 11.22 | 190 | 10,177 | No | 3, 15, 18, 24, 26, 28, 32 |

2 | 2900 | 3731.337 | 30.42 | 465 | 57,041 | Yes | 3, 15, 18, 24, 26, 28, 32 |

2 | 3000 | 3883.495 | 3883.54 | 26,220 | 4,289,912 | Yes | 3, 15, 18, 24, 26, 28, 32 |

3 | 2500 | 3600.918 | 8.33 | 65 | 3,864 | No | 3, 15, 18, 24, 26, 31, 32 |

3 | 2600 | 3622.543 | 10.39 | 114 | 9,520 | No | 3, 15, 18, 24, 26, 31, 32 |

3 | 2700 | 3648.490 | 11.97 | 136 | 18,020 | No | 3(2), 15, 18, 24, 26, 32 |

3 | 2800 | 3682.106 | 11.15 | 96 | 6,631 | No | 3(2), 15, 18, 24, 26, 32 |

3 | 2900 | 3718.859 | 31.68 | 512 | 93,063 | Yes | 3(2), 15, 18, 24, 26, 32 |

3 | 3000 | 3822.775 | 3181.55 | 20,225 | 4,089,337 | Yes | 3(2), 15, 18, 24, 26, 32 |

4 | 2500 | 3589.139 | 9.67 | 235 | 11,585 | No | 3(2), 15, 18, 26, 31, 32 |

4 | 2600 | 3608.441 | 9.59 | 93 | 4,713 | No | 3(2), 15, 18, 26, 31, 32 |

4 | 2700 | 3635.920 | 12.75 | 226 | 14,650 | Yes | 3(2), 15, 18, 26, 31, 32 |

4 | 2800 | 3671.420 | 16.49 | 303 | 27,371 | No | 3(3), 15, 18, 26, 32 |

4 | 2900 | 3706.331 | 16.54 | 230 | 36,502 | Yes | 3(3), 15, 18, 26, 32 |

4 | 3000 | 3810.764 | 2025.94 | 18,905 | 2,923,362 | No | 3(3), 15, 17, 18, 32 |

© 2020 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).