Geographical Rezoning as a Combinatorial Game: Case Study of the Australian Statistical Geography Standard

Abstract

Geographical rezoning is a combinatorial optimization problem of assigning basic spatial units into regions for statistical analysis and the publication of official government statistics, such as the Census. We propose a novel approach by reframing this problem into a single-player, deterministic, fully-informative, finite combinatorial game; or simply, a single-player puzzle. This definition allows effective and systematic exploration of state-space, and offers perfect information guarantees, as well as decouples the problem definition from a specific solver algorithm. We take an existing combinatorial algorithm called HeLP (Hierarchical Land Parcel Aggregation), and combine its rezoning heuristic with a game-playing algorithm, Monte Carlo tree search, to create three new game-playing solvers for the geographical rezoning problem. A case study was conducted on a real-world data set in Canberra, Australia, on the Australian Statistical Geography Standard (ASGS). Our Monte Carlo implementations, HeLP-MCTS, HeLP-RAVE, and HeLP-RHEA, were tested on simulated data and have yielded a 50.25%, 28.77%, and 57.02% increase in the mean value of the partitioning heuristic function, respectively, compared to a combinatorial solver HeLP. We have also computationally improved the original HeLP algorithm, offering significant speed increases.

Keywords

Monte Carlo tree search game theory general game playing rezoning spatial analysis

1. Introduction to Rezoning

Geographical rezoning (also known as districting, spatial partitioning, and regionalization) is an important data aggregation procedure for conducting spatial statistical analysis. It is a process of constructing geographical regions from basic spatial units (points or polygons) into contingent, uniquely identifiable, and non-overlapping regions. Rezoning facilitates privacy protection when the release of individual point pattern data is not feasible, and when community-level insights or inferences over a population are of interest to the spatial analyst.

1.1. Formal Definition

Consider a building block geography $b_{i} \in M_{1}$ , where $M_{1}$ is a set of uniquely identifiable, contingent, and non-overlapping geographies—that is, $M_{1} = {b_{1}, b_{2}, \dots, b_{k}}_{\neq}, k \leq n$ , such that $n$ is the total number of building blocks. Now consider a membership function defined by

χ_{M_{1}} (b) = {\begin{matrix} 1 & b \in M_{1} \\ 0 & b \notin M_{1} . \end{matrix}

(1)

Essentially, the function $χ_{M_{1}} (b)$ maps elements of the universe $X$ to either $0$ or $1$ depending on the membership of $b$ to $M_{1}$ , conditional on some value $θ$ of a heuristic function, $I (\cdot)$ , formally expressed as

χ_{M_{1}} (b) = {\begin{matrix} 1 & I (\cdot) \geq θ \\ 0 & otherwise . \end{matrix}

(2)

Moreover, the membership of a building block to a region is unique. Consider a family of all regions in a universe $X$ , $M = {(M_{1, i})}_{i \in I}$ , where $I$ is the index set. The uniqueness of membership can be defined in terms of set intersections and unions,

\underset{i = 1}{⋂^{n}} M_{1, i} = Ø, \underset{i = 1}{⋃^{n}} M_{1, i} \equiv X .

(3)

The proposition above holds for regions of the same aggregation level; however, regions may have hierarchical properties—smaller regions comprise larger ones. Thus, consider some region $M_{2} = {M_{1, 1}, \dots M_{1, k}}, k \leq n$ , where $n$ is the total number of regions of type $M_{1}$ . We can further extend this by considering $M_{3} = {M_{2, 1}, \dots M_{2, k}}, k \leq n$ , ad infinitum. Although, with an imposed restriction that the hierarchical property is bounded above by the universe $X$ (a collection of all building blocks)—the largest possible region is defined by $M_{n} = {x | x \in X}$ . From these propositions we can infer, by using a modification of the nested interval property, that given some region $M_{i} = {m_{1}, \dots, m_{k}}, k \leq n$ , so that $M_{i}$ is fully contained within $M_{i + 1}$ , as defined above, then the following holds if and only if a set of regions has the hierarchical property:

M_{1} \supseteq M_{2} \supseteq M_{3} \dots \supseteq M_{n} \to \underset{i = 1}{⋂^{n}} M_{i} \neq Ø

(4)

Thus, a solution for a given level of aggregation is a combination of elements of the universe $X$ that maximizes the mean value of the heuristic $I (\cdot)$ . A set of all combinations, or subsets, is a powerset of $X$ , that is, $P (X)$ . We denote it more formally as

P^{*} = \underset{P \in O}{\arg \max} \frac{\sum_{y \in P} I (y)}{| P |},

(5)

where $O$ in Equation (5) is defined as:

O = {P^{'} \subseteq P (X) ∣ (\underset{i = 1}{⋂^{| P^{'} |}} P_{i}^{'} = Ø) \land (\underset{i = 1}{⋃^{| P^{'} |}} P_{i}^{'} \equiv X)}

(6)

1.2. Background

The rezoning problem is relevant to a multitude of study areas such as in Census and government statistics (national statistics frameworks)—(Juricev-Martincev et al. 2023; Martin 2002, 2003, 2004; Mimis et al. 2012; Openshaw 1977; Openshaw and Rao 1995), travel-to-work areas (Coombes 2000; Watts 2009, 2013), and health and ecology (disease mapping; Adu-Prah and Oyana 2015; AssunÇão et al. 2006; Guo 2008; Guo and Wang 2011; Wang et al. 2012). Moreover, rezoning algorithms have been used to inform public service policy (McAndrews and Voith 1993), as well as affect transport (Gao et al. 2022), and politics (Almeida and Manquinho 2022), including elections (Guo and Jin 2011; Levin and Friedler 2019; Polsby and Popper 1991). Particular emphasis must be placed on the methodology’s accuracy as these tools play an important role in supporting decision-making processes. Poor regionalization can affect statistical inference due to the Modifiable Areal Unit Problem (Openshaw 1977) or ecological fallacy (Robinson 2009), both sources of bias. An additional inherent difficulty lies in the very definition of what constitutes an “optimal” region (Watts 2009), with different countries, and even different agencies imposing varying requirements which limits comparative analysis (Eagleson et al. 2002).

We highlight several types of algorithms that have been used to tackle the optimal rezoning problem, noting that these examples are not exhaustive of the wider regionalization literature, rather they are an indication of different streams of thought taken to tackle this complex problem. We discuss the benefits and shortcomings of these approaches. The first domain consists of general clustering algorithms such as Ward’s or $k$ -means being prominent examples. These methods are data-independent indicating wide applicability, however, these approaches are not utilized in automated rezoning literature as they do not consider the geographic domain of the problem—regionalization follows natural and urban boundaries. Moreover, they have an issue of being trapped in a local sub-optima, and finally, these algorithms depend on a good definition of “distance.” Hierarchical algorithms (combinatorial) such as the AZTool (Martin 2002, 2003, 2004), which is an implementation of a method initially developed by Openshaw (1977), and built upon by Openshaw and Rao (1995) and Mimis et al. (2012), or the newly developed algorithm HeLP (Juricev-Martincev et al. 2023), operate on iterative principles, greedy heuristics, and provide good results on small scales, but are consequently computationally expensive. Similarly, SAGE (Haining et al. 2000) is an example of an iterative swapping algorithm. These algorithms see great use in building national statistical frameworks (e.g., AZTool) as these systems are updated infrequently, thus the high computational costs are acceptable. Conversely, trading higher accuracy for high-speed, graph-based methods such as SKATER (AssunÇão et al. 2006), and REDCAP (Guo 2008) with modifications by Guo and Wang (2011) and Wang et al. (2012) have seen great applications in health studies. The benefits of these approaches lie in the foundations rooted in graph theory. Leveraging well-studied mathematical results yields quick results but may prove insufficient in applications where heuristic accuracy is needed more than computational speed. Another stream of algorithms in regionalization relies on fuzzy set theory such as those by Coombes (2000), Watts (2009, 2013), and Feng (2009). These methods have seen notable applications in creating travel-to-work areas and urban planning. The idea of fuzzy decisions relies on a membership function being an interval between $0$ and $1$ rather than a binary decision. This in turn allows better mimicking of human decisions. A downside of these approaches, and by extension, hierarchical algorithms, is that they cannot undo a decision once it has been made. This is in a sense, Markovian behavior, as every subsequent decision is solely dependent on the prior one. The final methodology stream we highlight relies on stochasticity such as genetic/evolutionary algorithms by Tucker et al. (2005), Flórez-Revuelta et al. (2008), and Demetriou et al. (2013). Genetic algorithms are excellent in their exploration of complex decision spaces as they allow evolving a decision, or a set of decisions through mechanisms such as crossover and mutation. This facilitates the serendipitous discovery of solutions that otherwise might be overlooked by standard heuristic approaches. The downsides are high computational costs and no guarantee of an optimal solution, as well as extensive hyperparameter tuning.

1.3. Knowledge Gap

From preceding sections we have seen that many automated rezoning approaches have been tried and tested. In a classical sense, the optimization process involves finding a single best solution that maximizes or minimizes a heuristic function that represents the human operator’s criteria and intentions to the fullest extent (Rao 2019). In addition, the decision-space, and the size of the combinatorial space would make rezoning an NP-hard problem, meaning that finding a globally optimal solution is effectively impossible.

Proposition 1. Geographical rezoning problem is NP-hard.

Proof: Let the rezoning problem be $Q$ . Based on the specifications outlined in Section 1.1, the rezoning problem corresponds to a graph partition problem. Hence, for a graph $G (V, E)$ , the vertex set $V$ is subdivided into multiple $V^{'}$ subsets such that the Equation (3) is satisfied. Let $k$ be the number of elements of $V^{'}$ . If we are given some prescribed $k$ then this problem becomes a $k$ -partite graph problem, denoted as $Q^{'}$ . Since it is a well-known problem, we can axiomatically accept that $k$ -partition is NP-complete (Diestel 2017). However, since $Q^{'}$ is a many-one reduction of $Q$ , meaning $Q^{'} \leq_{p} Q$ (Cormen et al. 2009), then we have $Q \equiv ⋃ Q^{'} (k) \forall k \in {i ∣ i \leq | V |, \forall i \in N}$ (where $| V |$ is the vertex set cardinality). Since NP is closed under union, that means $Q$ is also in NP. Since we have shown that a reduced problem is NP-complete, and the larger problem is NP, then it must be true that $Q$ is also NP-hard. □

Re-framing the rezoning problem into a combinatorial game-theoretic setting will allow us to balance exploration and exploitation to arrive at multiple solutions as opposed to traditional one-shot heuristics. The key difference here is that classical optimization, which solely optimizes the heuristic, would propagate the agent’s biases, whereas a game-theoretic approach, would enable potential solution discovery that the agent otherwise would not consider. Alas, this process is still limited by the heuristic function definition. Lastly, this refined framework is solver-agnostic, meaning it defines the game state and legal moves, not how to search the space. Classical heuristics often greedily merge until no improvement is possible, risking entrapment in local optima; this also oftentimes means once a decision is made it cannot be undone, which is a common occurrence in hierarchical agglomeration algorithms as they are Markovian in nature. A game setting allows systematic exploration, and some solvers, like the one we leverage here (Monte Carlo tree search) also offer perfect information guarantees.

2. Rezoning as a Combinatorial Game

We will re-frame the rezoning process as a finite, combinatorial, perfectly informative, single-agent game, mainly from a graph-theoretic perspective. This will be followed by an overview of Monte Carlo tree search algorithm which we use herein.

2.1. Formal Definition

Osborne and Rubinstein (1994) defines a game as a description of strategic interaction that includes the constraints on the actions the players (agents) can take. In addition, a solution systematically describes the outcomes that may emerge. A game is considered “perfectly informative” when every player at any time has complete knowledge of the game’s history and current state (Swiechowski et al. 2023). Moreover, a single-agent game implies that the success in solving a game depends only on the agent and not on external factors such as chance or opponents. We can use these definitions to describe the rezoning process as a game with the following properties. The goal of the game, in general terms, is to take a graph $G (V, E)$ , where $V$ is the vertex set and $E$ is the edge set, and perform a series of $n$ edge contractions to construct a new graph $G^{*} (V^{*}, E^{*})$ . The starting state of the game is an unweighted directed graph, such that every edge is bidirectional to its end vertices. In this instance, “bidirectional” means

\forall e \in E, e = (v_{i}, v_{j}) \Rightarrow \exists e^{'} \in E : e^{'} = (v_{j}, v_{i}), s . t . \forall v \in V .

(7)

Every vertex in this graph is a representation of a building block geography. Edges represent spatial relationships of building block geographies to boundaries. If two building blocks share a border, or if they border the same boundary (a non-building block geography), then they are considered connected, and thus have an edge. The agent (player) represents a human operator who can conditionally perform only one action—“merge” (edge contraction). This game is a sequential discrete decision-making process. Consider a vertex $A$ with the value of the heuristic $I (\cdot) = a$ , and another vertex $B$ with value $b$ , such that $A \neq B$ , and $a > b$ . We wish to perform a merge action $A \to B$ . This operation is conditioned on the value of the heuristic, $I (\cdot)$ , such that if $I ({A, B}) \geq I (A)$ we perform a “merge,” otherwise, we do nothing. The merge operation is essentially an edge contraction which takes some graph $G (V, E)$ , and an edge $e \in E; e_{1} = (v_{A}, v_{B}); v \in V$ , and creates a new vertex $ψ$ . Then, $\forall v \in V ∖ {v_{A}, v_{B}} \cup {ψ}$ are mapped from $V \to \hat{V}$ . Similarly, $\forall e \in E ∖ {e_{1}}$ are mapped from $E \to \hat{E}$ , with the addition of incident edges of both $v_{A}, v_{B}$ that now map to the vertex $ψ$ . A new graph is then created, $\hat{G} (\hat{V}, \hat{E})$ . This process is hierarchical, which means it “merges” vertices in turns. The terminating condition of the game is when no successful “merge” action is available, or $| V | = 1$ . Consider some unweighted bi-directed graph $G (V, E)$ . We can now formulate this process as guided by some function $f : G \to \hat{G}$ which performs an edge contraction. Now consider the following construction,

G = ⋃_{i \in I} (\underset{j = 0}{⋃^{J_{i}}} G_{i, j}),

(8)

where $I$ is the index set, and $J_{i}$ is the set of all distinct graphs that can be obtained by performing edge contractions $f (G_{i})$ of length $j$ . The number of contractions is defined as ${j | 0 \leq j \leq | V | - 1}, \forall j \in N$ , where $| V |$ is the cardinality of the vertex set of the original graph $G (V, E)$ . After the search has been completed, that is, $| V | = 1$ , we pick the optimal solution by selecting a graph $G^{*}$ such that

G^{*} = \underset{G \in G}{\arg \max} \exp (\frac{\sum_{v \in V_{G}} \log I (v)}{| V_{G} |}) .

(9)

The Equation (9) is an alternative representation of the geometric mean that reduces the risk of float overflow in computer implementation. We have selected the mean value as the solution because it has been proven to be the most robust and effective statistic in many domains of MCTS (e.g., the game of Go; Gelly and Silver 2011), which we discuss in the next section. The choice of mean used herein is used without loss of generality. The conditions of the uniqueness of membership via set intersection, the equivalence to the universe $X$ via the set union, and the hierarchical property definition still hold in this definition.

2.2. Monte Carlo Tree Search

Monte Carlo tree search (MCTS) has gained popularity primarily in combinatorial turn-based games, most notably chess and Go (Coulom 2007; Kocsis and Szepesvári 2006), as well as video games such as Sokoban (Crippa et al. 2022). Two extensive reviews done by Browne et al. (2012) and Swiechowski et al. (2023) can attest to the utility of such methods. In recent years it has seen expansion beyond game-playing in a literal sense, such as in road network planning (Darvariu et al. 2023) or railway management (G. Wang et al. 2024).

MCTS is an iterative, anytime, decision-making algorithm that searches combinatorial spaces, represented by trees, to build statistical evidence about the decisions available in particular states of the game. A state is the current configuration of the problem (game), whereas an edge is a transition (action) from the current state to the next (Swiechowski et al. 2023). However, it is important to note that the current literature stipulates that the MCTS must be enhanced from its “vanilla” version to deliver the expected performance. To understand this better, we must first examine the basic idea behind MCTS. Markov Decision Process (MDP) is a process described by a tuple $(S, A_{s}, T_{a}, R_{a})$ such that $S$ is the set of all states of the game. $A_{s}$ is an action available from the state $s$ . $T_{a}$ is the transition function modeled by the probability that an action $a$ in $s$ will lead to $s_{0}$ . Lastly, $R_{a}$ is the immediate payoff for reaching the state $s$ via an action $a$ . With these concepts in mind, we can divide the MCTS method into four phases:

Selection—starts from the root node and, at each level, the algorithm selects the next node according to the tree policy. The selection phase ends when a leaf node is reached or the terminating condition is fulfilled.

Expansion—adds at least one new child node to the tree. The new node is a state reached by the last action of the selection phase.

Simulation—performs a complete random game simulation.

Backpropagation—propagates the payoffs back to all nodes from the leaf node to the root.

We will now explore a few enhancements to the MCTS method relevant to the rezoning game. These alterations of the original algorithm target one or more of the four phases of the process to reduce computational time and improve the results. Kocsis et al. (2006), Gelly and Wang (2006), and Kocsis and Szepesvári (2006) tackle the exploitation-exploration trade-off problem in the selection phase of the MCTS. This improvement allows the algorithm to balance exploring new unidentified actions with the best actions tried. Kocsis et al. (2006) propose the UCB1 priority formula:

a^{*} = \underset{a \in A (s)}{\arg \max} {Q (s, a) + C \sqrt{\frac{\ln N (s)}{N (s, a)}}} .

(10)

Further modifications have been proposed, for example, Gelly and Wang (2006) account for action variance, among others. The UCB1, and its tuned counterpart, are an attractive approach, as discussed by Kocsis and Szepesvári (2006), in the bandit-arm statistic context. These rollout-based algorithms build a look-ahead tree from the game’s initial state. Hence, if some state is re-encountered, we can bias the action to follow, consequently speeding up the convergence. This is exactly what the $Q (s, a)$ parameter in the UCB1 formula allows us to do; it denotes the average result of playing action $a$ in state $s$ in the simulation stage. Moreover, as the number of simulations grows, $s \to \infty$ , the probability of the UCB1 selecting a sub-optimal action converges to zero (Gelly and Silver 2011). Parameter $C$ controls the exploration-exploitation trade-off and Swiechowski et al. (2023) suggests the value $\sqrt{2}$ as a common choice, but a higher value will encourage exploration. The number of times action $a$ has been sampled in state $s$ is denoted by $N (s, a)$ , whereas $N (s)$ is the total number of visits to that state. In addition, Coulom (2007) discusses optimizing the simulation step by pruning “bad” simulations. They note that this should be done carefully, as some concepts from “classical” simulation approaches do not apply to tree searches. In random simulations a move may appear poor at first, but could be followed up by a “great” move, its evaluation may be increased when searched more deeply. This is particularly relevant to combinatorial games such as chess (e.g., sacrificing a valuable piece to set up a more advantageous position in the next move), or even our rezoning game—adding a sub-optimal vertex into a partition so that in the next move high-value adjacent vertices could be considered. This is one mechanic that the current HeLP algorithm does not have since it traverses the graph via locally optimal vertices. The next modification is a class of evolutionary algorithms called Rolling Horizon Evolutionary Algorithm (RHEA) by Perez et al. (2014), and more recently by Gaina et al. (2022). Instead of the traditional selection and simulation steps, RHEA evolves sequences of actions from the current state up to a specified horizon $h$ . One sequence of steps represents one individual within the population. The RHEA principle has been applied to MCTS to create the so-called Evolutionary MCTS. This includes, but is not limited to, Lucas et al. (2014), Perez et al. (2014), Hendrik et al. (2016), and Gaina et al. (2017). We now offer an overview of the applications of this methodology to the regionalization game. Evolutionary algorithms (EA) consider some population, in this case, a graph $G (V, E)$ with an edge contraction (merge) being a legal move in the game. There are three distinct phases performed over this population across a specified number of generations:

Selection—algorithm chooses the best candidates from the population based on some fitness function. Common strategies include tournament (used herein), roulette wheel, and rank-based selection.

Crossover—randomly pick a sub-sample of individuals from the tournament-selected sample. Exchange information randomly. In this context, we exchange the merge history. We use uniform crossover herein, whilst another viable option is $k$ -point crossover.

Mutation—algorithm makes a small random change. In this context, we exchange a percentage of merge operations with a random substitution.

This type of algorithm, as mentioned before, can be incorporated with the MCTS. There are several benefits of this hybrid approach. Firstly, we will experience faster convergence since we are performing multiple merges per time step, unlike one at a time in classical MCTS. The crossover and mutation parameters enable and improve more comprehensive exploration than the standard MCTS approach. Thus, the four new phases are as follows:

Selection—MCTS—algorithm selects the next node according to the tree policy, such as UCB1. The selection phase ends when a leaf node is reached or the terminating condition is fulfilled.

Expansion—RHEA—apply standard EA procedure of edge contractions up to some horizon $h$ (look-ahead). Output best candidates as children in the MCTS tree.

Simulation—MCTS—performs a complete random game simulation.

Backpropagation—MCTS—propagates the payoffs back to all nodes along the path from the leaf node to the root.

The final modification we will consider is the Rapid Action Value Estimation (RAVE) by Gelly and Silver (2011)—the first method that defeated a human Go player. This enhancement is improving the expansion phase so that instead of adding only one node it considers all nodes that belong to the optimal path. This will in turn minimize the chaotic effects of cold start. Thus, the new proposed formula for an action’s value is:

a^{*} = \underset{a \in A (s)}{\arg \max} {β (s, a) Q_{RAVE} (s, a) + Q (s, a) (1 - β (s, a))} .

(11)

When combined with MCTS, RAVE enables knowledge share between related nodes, thus resulting in faster, albeit biased estimates of action values. This is made possible by the all-moves-as-first heuristic that RAVE utilizes. Classical MCTS separately estimates the value of each state and each action in the search tree. By combining the two algorithms, we attain the fast learning benefits of RAVE and the accuracy and convergence guarantee of the MCTS. The value $Q_{RAVE} (s, a)$ keeps track of all actions taken in the simulation phase as well as the selection phase. The parameter $β (s, a)$ is the weighting parameter between the Monte Carlo value and the all-moves-as-first heuristic value. It is defined as

β (s, a) = \sqrt{\frac{k}{3 N (s) + k}},

(12)

where $k$ is the RAVE equivalence constant. Gelly and Silver (2011) suggest values of at least $1000$ or more for this parameter.

2.3. Modifications to the Monte Carlo Tree Search

In this section, we address and propose solutions to mitigating the negative side effects of the MCTS algorithm. These modifications relate to the computational complexity of the rezoning problem. We consider the works of Chaslot et al. (2008) who leveraged “progressive bias” and “progressive unpruning.” What this means is that they use a heuristic function H(⋅) in their selection strategy, combined with aggressive pruning of the game state tree, which tapers off as the number of simulations grows, which in turn enables the more commonly used UCT selection algorithm to pick optimal results. First, we must address the rezoning process’ branching factor, which, if sufficiently large, can make the use of the MCTS retractable. The branching factor is a tree property that defines the number of node’s children at each depth level $d$ . Devarapalli and Biswas (2023) provide a formula for some graph $G (V, E)$ where

b (G, s) = \frac{\sum_{d = 0}^{D} \frac{T_{c}}{T_{d}}}{D},

(13)

is the branching factor of graph $G$ with some starting node $s$ . The total number of children for nodes at depth $d$ is $T_{c}$ , whereas $T_{d}$ is the total number of non-leaf nodes. A node in a tree refers to the state of the game. If we observe Equation (13) we can derive an approximation to the branching factor. The depth $D$ is bounded by $| V | - 1$ since we perform one edge contraction per level. Thus, the smallest a graph can become is having $1$ vertex. At every depth $d$ we can have $\frac{| E |}{2} - d$ children, which is an arithmetic sequence since there is a common difference of $- 1$ . Thus the sum is

\sum_{d = 0}^{D} \frac{T_{c}}{T_{d}} = \frac{D}{2} (| E | - D + 1) .

(14)

Since we know the upper bound of $D$ , and due to the bidirectional nature of the graph, and the fact there are no disconnected vertices, we can say that the minimum number of edges is $| E | \geq 2 (| V | - 1)$ , which is $| E | \geq 2 D$ . This way, we can evaluate the branching factor to be:

b (G, s) \geq \frac{| V |}{2} .

(15)

We now must prove two conditions, to validate the branching factor proposed in Equation (15).

Proposition 2. $| V | > 1, | E | \geq | V |, \forall G \in G$ .

Proof: An edge contraction operation requires $| V | \geq 2$ , as a vertex cannot be merged with itself, thus the case $| V | = 1, | E | = 0$ can be ignored. The next step is to show that the neighborhood of $v \in V$ must be nonzero, that is, $N (v) > 0$ . By definition of a basic spatial unit and a statistical region, as shown in Section 2.4, there can be no gaps or overlaps, so all vertices must be connected, which means that $\forall v \in V, N (v) \geq 1$ since every vertex must share a border with another. Lastly, since every edge is bidirectional, at the very least, there are $2 (| V | - 1)$ edges, so it is clear that $| E | \geq | V |$ . □

The next step relates to picking a starting point of the rezoning process. In the original HeLP algorithm (Juricev-Martincev et al. 2023) this is done based on internal indexing of objects in a set (i.e., no heuristic rule). Instead, we can use the starting point heuristic:

SPH = \max {‖ n (v) - I (v) ‖} \forall v \in V,

(16)

where $n (v)$ is the number of neighbors of vertex $v$ , and $I (v)$ is the value of the heuristic. Thus, we will append a weighted min-max normalized $SPH$ value to all three of our Monte Carlo algorithms. We can treat this heuristic as progressive bias so that up to a graph size $g$ , the algorithm favors $SPH$ over UCB1. The normalized SPH operator will be used for larger graphs up to a threshold $b$ , that is user-specified; this will limit the exploration abilities at first. In turn, it will reduce computational resources and slow down branching. We also need to account for pruning strength. We consider:

p = ⌈ \frac{c}{\sqrt{| V |}} ⌉,

(17)

where $c$ in Equation (17) is a user-defined constant indicating how often we prune the search tree. For our use-case, we prune all nodes with value $0$ when $i \equiv 0 (modp)$ is satisfied, where $i$ is the iteration of the Monte Carlo simulation. This is predominantly dependent on hardware limitations.

2.4. Computational Improvements to HeLP

This section outlines the computational improvements conducted on the original HeLP algorithm that have made its fusion into a Monte Carlo framework feasible and computationally tractable. During preliminary analysis and profiling of the original HeLP heuristic implementation, it was found that the bottleneck lies in the explicit calculations of geometric properties of building block geographies and the associated overhead of accessing the necessary GIS libraries. The focus of this subsection will be on the development of a random forest model (Breiman 2001) to approximate the geometric compactness of a shape, or more precisely the geometric compactness of merging two shapes without overlap; in rezoning, there should be no overlaps or gaps to satisfy the requirement of geographic contiguity (Juricev-Martincev et al. 2023). Other improvements such as code optimization have been omitted since they are trivial in novelty and considered standard practice in computer science. We will use an existing implementation of Random Forest Regressor in the $scikit - learn$ package in Python (Pedregosa et al. 2011). We define geometric compactness as the ratio of a shape’s area to the perimeter. One such measure is the Polsby-Popper test (Polsby and Popper 1991). To implement a Random Forest model, we must consider several factors. The obvious choices are the two shapes’ area and perimeter measures. Each shape’s bounding box’s width and height will give us insight into the shape’s aspect ratio and convexity. Lastly, we must consider the joining angle between two shapes, as depicted in Figure 1, as this can affect the compactness of the merged shape. This value is calculated as $θ = atan 2 (c_{x}, c_{y})$ , where $c_{x}, c_{y}$ are centroids of shapes $x, y$ . We constructed a training data set of $125, 000$ Thiessen polygons for this model’s training. We have then created the “results” such that a polygon would be merged with the adjacent polygon along the longest border. Polygon pairs are unique, that is, no polygon can merge with more than one other. This would result in some polygons not having a pair to merge with; these data were deleted. The final output had approximately $50, 000$ observations. We have split the data into an $80 - 20$ training and testing split. We conducted hyper-parameter tuning using $k$ -fold cross-validation, as implemented in scikit-learn’s Randomized Search. This yielded a model with a Mean Squared Error (MSE) of $0.0024$ , and a Mean Absolute Percentage Error (MAPE) of 5.05% indicating highly accurate forecasting. For testing purposes, we have created a data set shown in Figure 2 which resulted in a network of $393$ nodes, where each node is a thematic unit as specified by Juricev-Martincev et al. (2023). The original HeLP algorithm was applied to this data and executed in $3048.88$ seconds, whereas the HeLP++ took only $4.72$ seconds. All results were recorded on a Windows 11 desktop machine with an Intel i7-13700K chip, 32 GB RAM, and an Nvidia GTX 4090 graphics card. The primary reason for this speed-up is driven by the approximation of geometric properties, meaning the need for Feature Layers (tables that handle geographic information) was eliminated. This consequently removed the abundance of calls to the GIS libraries and the associated computational overhead. This way, the algorithm implementation would only rely on traditional data structures. We eliminated all iterative constructs, specifically for loops, in favor of adopting a functional programming paradigm that leverages higher-order functions, comprehensions, and recursive techniques. The HeLP algorithm exhibited a tendency or inherent challenge in generating excessive output regions as seen in Juricev-Martincev et al. (2023). This problem lies in the intersection between computational and methodological improvements. In the initial implementation of the HeLP algorithm, the redistricting process was divided into two distinct stages—the greedy heuristic that conducts edge contractions on locally optimal pairs, and the second stage that deals with those nodes that have not participated in a successful contraction. These nodes (source) were then merged on the “least damage” principle, that is, merged with a neighbor (target) that would cause the least amount of decrease in the region’s quality, $I (H)$ . HeLP++ handles this process more efficiently since we are creating a mapping between node pairs weighted by the value $Δ I (H)$ with respect to the target. This way we can assess the relative decrease of the regions’ values.

Figure 1.

The effect of position on overall geometric compactness. Each shape, orange (x) and blue (y), comprises four unit squares. In Scenario A, their positioning yields compactness of $0.31$ , which is lower than the positioning in Scenario B, which yields $0.51$ .

Figure 2.

Simulated data set used to test the original HeLP algorithm against its modifications. The data is constructed from $1000$ randomly generated Thiessen polygons, where 25% shares the same land use category.

3. Simulation Study

This section gives a toy example of our new automated rezoning method being applied over simulated data, and compared with a deterministic, hierarchical HeLP++ approach. We can now outline our basic Monte Carlo tree search implementation. The selection phase utilizes the UCB1 formula as specified in Equation (10). The expansion phase takes in an exploration parameter, expressed as the percentage of $| V |$ , that constructs $n$ child nodes based on the SPH heuristic in Equation (16). The simulation step specifies a horizon parameter that tells the MCTS algorithm how many steps to look ahead in the simulation rather than playing the entire game. This is to save resources and reduce computational time. We have constructed a simulated data set as specified in Figure 3 to compare the HeLP++ algorithm against the Monte Carlo approaches—MCTS, RAVE, and RHEA. The conditions of the simulation study are as follows: $(ω_{C}, ω_{H}, ω_{E}) = (0, 0.25, 0.75)$ with the attribute of interest target set to $15$ . Hyperparameter tuning was initially conducted via a Latin Hypercube (McKay et al. 1979). Then, a subset of these results was selected as a starting point from which we performed a one-at-a-time sensitivity analysis to motivate the final parameter selection. The best result for each method was then selected. Monte Carlo tree search and RAVE considered 25% of nodes for each step and had a ten step look-ahead horizon. The use of a horizon is also known as “truncated MCTS,” and it increases simulation speed and reduces the variance of the Monte Carlo evaluation (Gelly and Silver 2011). HeLP-RAVE had the RAVE equivalence parameter set to $k = 1000$ , as recommended by Gelly and Silver (2011). HeLP-RHEA’s hyperparameter selection is more involved. This approach is an evolutionary MCTS algorithm, where a truncated genetic algorithm controls the evolution via a rolling horizon. For this example, we considered a twenty generation-long evolution, 25% elitism (tournament selection), and a 20% mutation chance with a five-step horizon. The pruning strength parameter for all approaches was set to $c = 100$ as specified in Equation (17). The SPH heuristic was not used herein as the graph size was relatively small. HeLP++ followed its standard greedy heuristic with all smoothing features excluded. Table 1 summarizes the findings. We see that HeLP++ is much faster than the Monte Carlo tree search/RAVE approaches, but falls short without the smoothing functionality, which is meant to absorb the negative effects of the algorithm’s chain-like (Markovian) nature. This smoothing functionality re-assigns regions of index value less than the user-specified threshold. Monte Carlo approaches do not require this and utilize exploration-exploitation to check more solutions. This allows higher median results to be discovered and removes the need for threshold-subjective re-assignment. The Genetic Monte Carlo method (RHEA) has shown faster convergence than other Monte Carlo approaches. This is due to the ability to conduct multiple edge contractions simultaneously; these initially random contractions evolved over several generations to yield effective results.

Figure 3.

Simulated data set used to compare the performance of the original HeLP algorithm against its modifications—MCTS, RAVE, RHEA. The data is constructed from forty-five gridded units, evenly split between two categories, thus creating a graph of sixteen nodes (thematic units/clusters, as specified by Juricev-Martincev et al. (2023)). Every attribute (point of interest) has a value of 1.

Table 1.

Comparison of Regionalization Schemas Split by Method, Outlining the Summary Statistics of the Heuristic, $I (\cdot)$ , the Computational Time, the Total Number of Regions Created, $N$ , and the $Δ$ % Difference in the Mean Value of $I (\cdot)$ and Execution Time, $t$ , to the Base HeLP ++ Algorithm.

Method	Min. $I (\cdot)$	Mean $I (\cdot)$	Med. $I (\cdot)$	Max. $I (\cdot)$	S.D. $I (\cdot)$	$Δ I (\cdot)$ %	N	$t / \sec$	$Δ t / \sec$ %
HeLP++	0.344	0.591	0.603	0.813	0.229	—	4	3.049	—
MCTS	0.859	0.888	0.867	0.937	0.043	50.254	3	6.954	−128.075
RAVE	0.638	0.761	0.783	0.841	0.090	28.765	4	8.010	−162.709
RHEA	0.892	0.928	0.933	0.960	0.034	57.022	3	3.311	−8.593

4. Case Study: Australian Capital Territory

For this case study, we utilized publicly available data sets provided by the Australian Government. In particular, the Geospatial Data Catalogue (Land Administration) by the Environment, Planning, and Sustainable Directorate (ACT Government) (2023). From this portal, we attained the address information, the cadastral land parcels, road center lines, and road reserves parcels. Mesh Block boundaries were obtained from the Australian Bureau of Statistics (2021). Environment, Planning, and Sustainable Directorate (2023) provided the educational facilities’ locations. ACT Government (2023) provided the locations of Canberran hospitals and health centers. A cadastral land parcel is defined as a continuous area, or more appropriately volume, identified by a unique set of homogeneous property rights (Dale and McLaughlin 2000). From these building blocks, we can create a statistical region schema—a collection of distinct, non-overlapping, contiguous geographic areas on which analysis is conducted; more specifically, a collection of Mesh Blocks—smallest statistical regions in Australia, defined by homogeneous land use across one of the eight categories (residential, medical, educational, industrial, agricultural, parklands, commercial, other) and each containing thirty to sixty dwellings. Thus, we had to remap the cadastral classification into the ABS categories. The majority of hyperparameters are shared across methods (HeLP++, MCTS, RAVE, RHEA), and these have been tuned via the same strategy as mentioned in the simulation study to attain results as close as possible to the manual ABS results whilst respecting contextual restrictions, which we later discuss. It is important to note that any comparisons of our methods to the ABS solution are solely with respect to the heuristic, $I (\cdot)$ . We have also imposed a one-hour resource limit on Monte Carlo-based methods. This design choice prioritizes the tool’s usability for spatial analysts in their day-to-day workflows. Spatial analysis often involves iterative exploration and decision-making, which needs to be conducted multiple times within a workday. This limit ensures that analysts can receive results expeditiously and conduct rapid iterations, enabling efficient spatial data exploration and informed decision-making. We weighted the rezoning criteria of compactness, homogeneity, and equinumeriosity of the heuristic $I (\cdot)$ , as $(ω_{C}, ω_{H}, ω_{E})$ = ( $0.14, 0.77, 0.09$ ). These results were derived from historical ABS partitions. We will apply a no-merge condition on the “educational,” and “medical” categories, meaning that these building blocks cannot merge with any other, and remain as individual regions. We consider no-cross conditions on the following road types—highway, urban arterial, urban distributor, rural arterial, and rural distributor—meaning that any edges intersecting such boundaries will be deleted, to prevent a region from occupying space on both sides of the boundary. Finally, we set a lower threshold of $I (\cdot) = 0.5$ , so that any region with the heuristic value lower than the threshold is re-evaluated. Figure 4 illustrates the study area more closely.

Figure 4.

2016 Australian Capital Territory Mesh Block structure (omitted water Mesh Blocks). Out of the total $6334$ Mesh Blocks, only $64$ experienced significant population growth, thus requiring rezoning. The ABS have partitioned these regions into $334$ new Mesh Blocks in the 2021 ASGS schema.

Table 2 shows a summary of the results of this case study. All methods are compared respectively of a manual solution created by the ABS. Firstly, we notice, that the HeLP algorithm completed the rezoning process of the study area well within the one-hour resource limit; this, alongside the fact that the mean difference of the heuristic is under 1%, can attest to its potential to be applied in real-world geospatial analysis. Next, we notice the “vanilla” MCTS algorithm with a much greater execution time of $3116.714$ seconds, and a larger number of regions created $519$ . These shortcomings align with what the literature tells us about an unmodified MCTS approach. This method explored the search space inefficiently, which did not allow for serendipitous discovery of alternative good solutions. The RAVE modification took slightly longer than the MCTS, at $3493.635$ seconds, but it discovered a better solution, which only created $475$ regions. This is due to the RAVE heuristic ability to minimize the negative effects of cold start when insufficient simulations are played out, as in the MCTS approach. Finally, we observe the genetic Monte Carlo approach—RHEA. This method had a slightly longer execution time than the HeLP++ approach by 19.83%. We see that it created the number of regions closest to the manual ABS solution, with similar mean and median values of the heuristic function. This is thanks to its ability to conduct multiple edge contractions at a time, at random, which solves both the problem of the Markovian nature of the HeLP++ algorithm, as well as the problem of the MCTS/RAVE relating to the branching factor or the search tree size. The genetic capabilities allow us to evolve these random contractions into more promising combinations due to the evolutionary crossover/mutation mechanisms. Overall, the genetic Monte Carlo approach can efficiently tackle the automated rezoning problem like a greedy heuristic algorithm and explore complex spaces like a game-playing algorithm. Lastly, this method offers easy and attractive expansions into the reinforcement learning domain, which we will discuss in the next section.

Table 2.

Comparison of Regionalization Schemas Over the Real World ACT Data, Split by Method, Outlining the Summary Statistics of the Heuristic, $I (\cdot)$ , the Computational Time, the Total Number of Regions Created, $N$ , and the $Δ %$ Difference in the Mean Value of $I (\cdot)$ Compared to the Manual ABS Partitioning.

Method	Min. $I (\cdot)$	Mean $I (\cdot)$	Med. $I (\cdot)$	Max. $I (\cdot)$	S.D. $I (\cdot)$	$Δ I (\cdot)$ %	N	$t / \sec$
ABS	0.603	0.883	0.885	0.975	0.075	—	334	—
HeLP++	0.658	0.889	0.909	0.973	0.069	0.679	387	541.857
MCTS	0.716	0.883	0.882	0.978	0.039	0	519	3,116.714
RAVE	0.576	0.882	0.881	0.973	0.040	−0.113	475	3,493.635
RHEA	0.677	0.887	0.883	0.981	0.046	0.453	314	649.331

5. Conclusion

In this study, we have taken a problem of spatial aggregation known as rezoning and reframed it from a combinatorial and graph-traversal problem into a finite, single-agent, fully-informative game. This shift into a game-theoretic setting enabled us to leverage a popular game-playing algorithm—Monte Carlo tree search. In turn, this enables greater exploration capabilities of complex decision spaces, and the discovery of alternative solutions to an NP-hard problem, such as rezoning. We considered standard MCTS, alongside a popular modification RAVE, and a genetic/evolutionary approach—RHEA. We combined these game-playing algorithms with a rezoning heuristic, HeLP, which we first computationally optimized to make this algorithmic fusion tractable. We have tested our three new methods on a simulated data set, where we have seen initial evidence of the benefits and drawbacks of Monte Carlo approaches; these were improved exploration abilities to discover alternative solutions, rather than a deterministic one, but at the cost of increased computational time. We reinforced this by conducting a case study on the Australian Statistical Geography Standard, where in a complex scenario, the “vanilla” MCTS delivered sub-par results, as in line with literature. The RAVE approach was promising albeit less restrictive resources are needed. Finally, a genetic approach, RHEA, seemed feasible in real-world applications due to the benefits discussed in the preceding section. This area of automated rezoning is a promising branch of spatial analytics. The ability to define this problem as a game, facilitated an expansion in methodology, particularly from hierarchical, graph-traversal, combinatorial algorithms into game-playing algorithms such as Monte Carlo tree search, as well as reinforcement learning such as deep Q learning, NEAT (Neuro Evolution of Augmenting Topologies), proximal policy optimization, and other advanced methods in a broader context of machine learning.

Footnotes

Acknowledgements

The authors would like to thank the Australian Bureau of Statistics for the support of the project. In particular Mr Edwin Lu from the Data Science and Emerging Methods Branch, Methodology and Data Science Division, and Mr Jarrod Lange from the Geospatial Research & Design, Location Infrastructure Branch, Statistical Infrastructure Division, for providing valuable answers to questions about the current rezoning methodology employed in Australia. Lastly, the lead author extends his thanks to Dr Rob Salomone for valuable mentoring.

Funding

The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This project was co-funded by the Australian Bureau of Statistics and the Queensland University of Technology under the Australian Bureau of Statistics (ABS) / QUT Centre for Data Science Scholarship.

ORCID iDs

Filip Juricev-Martincev

Helen Thompson

Gentry White

Data and Codes Availability Statement

The algorithm codebase is deployed as a Conda Python package ‘helprezone’ available at https://anaconda.org/filipjm/helprezone. The data that supports the findings of this study, as well as any additional materials are available in Figshare at .

Received: July 2, 2025

Accepted: February 17, 2026

References

ACT Government. 2023. “Hospitals and Health Centres.”https://www.health.act.gov.au/hospitals-and-health-centres (accessed June 20, 2023).

Adu-Prah

Oyana

T. J.

2015. “Regionalization of Youth and Adolescent Weight Metrics for the Continental United States Using Contiguity-Constrained Clustering and Partitioning.” Cartographica 50 (2): 61–70. DOI: https://doi.org/10.3138/cart.50.2.2507.

Almeida

Manquinho

2022. “Constraint-Based Electoral Districting Using a New Compactness Measure: An Application to Portugal.” Computers & Operations Research 146: 105892. DOI: https://doi.org/10.1016/j.cor.2022.105892.

AssunÇão

R. M.

Neves

M. C.

Câmara

Freitas

C. D. C.

2006. “Efficient Regionalization Techniques for Socio-Economic Geographical Units Using Minimum Spanning Trees.” International Journal of Geographical Information Science 20 (7): 797–811. DOI: https://doi.org/10.1080/13658810600665111.

Australian Bureau of Statistics. 2021. “Australian Statistical Geography Standard (ASGS): Volume 1 - Main Structure and Greater Capital City Statistical Areas.”https://www.abs.gov.au/statistics/standards/australian-statistical-geography-standard-asgs-edition-3/jul2021-jun2026/access-and-downloads/digital-boundary-files (accessed October 1, 2023).

Breiman

2001. “Random Forests.” Machine Learning 45 (1): 5–32. DOI: https://doi.org/10.1023/A:1010933404324.

Browne

C. B.

Powley

Whitehouse

, et al. 2012. “A Survey of Monte Carlo Tree Search Methods.” IEEE Transactions on Computational Intelligence and AI in Games 4 (1): 1–43. DOI: https://doi.org/10.1109/TCIAIG.2012.2186810.

Chaslot

Winands

Van Den Herik

H. J.

Uiterwijk

Bouzy

2008. “Progressive Strategies for Monte Carlo Tree Search.” New Mathematics and Natural Computation 4 (3): 343–57. DOI: https://doi.org/10.1142/S1793005708001094.

Coombes

2000. “Defining Locality Boundaries with Synthetic Data.” Environment and Planning A: Economy and Space 32 (8): 1499–518. DOI: https://doi.org/10.1068/a29165.

10.

Cormen

T. H.

Leiserson

C. E.

Rivest

R. L.

Stein

2009. Introduction to Algorithms. MIT Press.

11.

Coulom

2007. “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search.” In Computers and Games, edited by Herik

H. J.

Ciancarini

Donkers

H. H. L. M. J.

Springer. DOI: https://doi.org/10.1007/978-3-540-75538-8_7.

12.

Crippa

Lanzi

P. L.

Marocchi

2022. “An Analysis of Single-Player Monte Carlo Tree Search Performance in Sokoban.” Expert Systems with Applications 192: 116224. DOI: https://doi.org/10.1016/j.eswa.2021.116224.

13.

Dale

McLaughlin

2000. Land Administration. Oxford University Press.

14.

Darvariu

V.-A.

Hailes

Musolesi

2023. “Planning Spatial Networks with Monte Carlo Tree Search.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 479 (2269): 20220383. DOI: https://doi.org/10.1098/rspa.2022.0383.

15.

Demetriou

See

Stillwell

2013. “A Spatial Genetic Algorithm for Automating Land Partitioning.” International Journal of Geographical Information Science 27 (12): 2391–409. DOI: https://doi.org/10.1080/13658816.2013.819977.

16.

Devarapalli

R. K.

Biswas

2023. “Processing Large Graphs with an Alternative Representation.” In Principles of Big Graph: In-Depth Insight, 1st ed., edited by Patgiri

Deka

G. Chandra

Biswas

Elsevier Science & Technology.

17.

Diestel

2017. Graph Theory. Springer Berlin. DOI: https://doi.org/10.1007/978-3-662-53622-3.

18.

Eagleson

Escobar

Williamson

2002. “Hierarchical Spatial Reasoning Theory and GIS Technology Applied to the Automated Delineation of Administrative Boundaries.” Computers, Environment and Urban Systems 26 (2–3): 185–200. DOI: https://doi.org/10.1016/S0198-9715(01)00040-0.

19.

Environment, Planning, and Sustainable Directorate. 2023. “ACTGOV Priority Enrolment Areas Current.” Education Directorate (ACT Government). https://services1.arcgis.com/E5n4f1VY84i0xSjy/arcgis/rest/services/ACTGOV_Priority_Enrolment_Areas_Current/FeatureServer (accessed October 1, 2023).

20.

Environment, Planning, and Sustainable Directorate (ACT Government). 2023. “ACT Government Geospatial Data Catalogue (Land Administration).”https://actmapi-actgov.opendata.arcgis.com/search?tags=Land%20Administration (accessed October 1, 2023).

21.

Feng

2009. “Fuzziness of Travel-to-Work Areas.” Regional Studies 43 (5): 707–20. DOI: https://doi.org/10.1080/00343400801922806.

22.

Flórez-Revuelta

Casado-Díaz

J. M.

Martínez-Bernabeu

Gómez-Hernández

2008. “A Memetic Algorithm for the Delineation of Local Labour Markets.” In Parallel Problem Solving from Nature – PPSN X, edited by G. Rudolph

T. Jansen

Beume

Lucas

Poloni

Springer.

23.

Gaina

R. D.

Devlin

Lucas

S. M.

Perez-Liebana

2022. “Rolling Horizon Evolutionary Algorithms for General Video Game Playing.” IEEE Transactions on Games 14 (2): 232–42. DOI: https://doi.org/10.1109/TG.2021.3060282.

24.

Gaina

R. D.

Lucas

S. M.

Pérez-Liébana

2017. “Population Seeding Techniques for Rolling Horizon Evolution in General Video Game Playing.”Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC), Donostia - San Sebastián, Spain, June 5–8. DOI: https://doi.org/10.1109/CEC.2017.7969540.

25.

Gao

Tang

2022. “Effects of Spatial Units and Travel Modes on Urban Commuting Demand Modeling.” Transportation 49: 1549–75. DOI: https://doi.org/10.1007/s11116-021-10219-y.

26.

Gelly

Silver

2011. “Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go.” Artificial Intelligence 175 (11): 1856–75. DOI: https://doi.org/10.1016/j.artint.2011.03.007.

27.

Gelly

Wang

2006. “Exploration Exploitation in Go: UCT for Monte-Carlo Go.” NIPS: Neural Information Processing Systems Conference On-line Trading of Exploration and Exploitation Workshop, Canada. https://hal.science/hal-00115330.

28.

Guo

2008. “Regionalization with Dynamically Constrained Agglomerative Clustering and Partitioning (REDCAP).” International Journal of Geographical Information Science 22(7): 801–23. DOI: https://doi.org/10.1080/13658810701674970.

29.

Guo

Jin

2011. “iRedistrict: Geovisual Analytics for Redistricting Optimization.” Journal of Visual Languages & Computing 22 (4): 279–89. DOI: https://doi.org/10.1016/j.jvlc.2011.03.001.

30.

Guo

Wang

2011. “Automatic Region Building for Spatial Analysis.” Transactions in GIS 15: 29–45. DOI: https://doi.org/10.1111/j.1467-9671.2011.01269.x.

31.

Haining

Wise

2000. “Designing and Implementing Software for Spatial Statistical Analysis in a GIS Environment.” Journal of Geographical Systems 2: 257–86. DOI: https://doi.org/10.1007/PL00011458.

32.

Hendrik

Vanessa

Diego

P.-L.

Mike

2016. “MCTS/EA Hybrid GVGAI Players and Game Difficulty Estimation.”Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (CIG), Santorini, Greece, September 20–23.

33.

Juricev-Martincev

Giuffrida

Thompson

White

2023. “A Novel Hierarchical Aggregation Algorithm for Optimal Repartitioning of Statistical Regions.” International Journal of Geographical Information Science 37 (7): 1640–66. DOI: https://doi.org/10.1080/13658816.2023.2204347.

34.

Kocsis

Szepesvári

2006. “Bandit Based Monte-Carlo Planning.” In Machine Learning: ECML 2006, edited by Fürnkranz

Scheffer

Spiliopoulou

Springer. DOI: https://doi.org/10.1007/11871842_29.

35.

Kocsis

Szepesvari

Willemson

2006. “Improved Monte-Carlo Search.”https://api.semanticscholar.org/CorpusID:9831567 (accessed October 1, 2023).

36.

Levin

H. A.

Friedler

S. A.

2019. “Automated Congressional Redistricting.” Journal of Experimental Algorithmics 24: 1–24. DOI: https://doi.org/10.1145/3316513.

37.

Lucas

S. M.

Samothrakis

Perez

2014. “Fast Evolutionary Adaptation for Monte Carlo Tree Search.” In Applications of Evolutionary Computation, edited by Esparcia-Alcázar

Mora

Springer. DOI: https://doi.org/10.1007/978-3-662-45523-4_29.

38.

Martin

2002. “Geography for the 2001 Census in England and Wales.” Population Trends 108: 7–15. https://pubmed.ncbi.nlm.nih.gov/12138615/

39.

Martin

2003. “Extending the Automated Zoning Procedure to Reconcile Incompatible Zoning Systems.” International Journal of Geographical Information Science 17 (2): 181–96. DOI: https://doi.org/10.1080/713811750.

40.

Martin

2004. “Neighbourhoods and Area Statistics in the Post 2001 Census Era.” Area 36 (2): 136–45. DOI: https://doi.org/10.1111/j.0004-0894.2004.00210.x.

41.

McAndrews

Voith

1993. “Can Regionalization of Local Public Services Increase a Region’s Wealth?” Journal of Regional Science 33 (3): 279–301. DOI: https://doi.org/10.1111/j.1467-9787.1993.tb00227.x.

42.

McKay

M. D.

Beckman

R. J.

Conover

W. J.

1979. “A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code.” Technometrics 21 (2): 239–45. https://www-jstor-org-443.web.bisu.edu.cn/stable/1271432

43.

Mimis

Rovolis

Stamou

2012. “An AZP-ACO Method for Region-Building.” In Artificial Intelligence: Theories and Applications, edited by Maglogiannis

Plagianakos

Vlahavas

Springer. DOI: https://doi.org/10.1007/978-3-642-30448-4_11.

44.

Openshaw

1977. “A Geographical Solution to Scale and Aggregation Problems in Region-Building, Partitioning and Spatial Modelling.” Transactions of the Institute of British Geographers 2: 459–72. DOI: https://doi.org/10.2307/622300.

45.

Openshaw

Rao

1995. “Algorithms for Reengineering 1991 Census Geography.” Environment and Planning A: Economy and Space 27 (3): 425–46. DOI: https://doi.org/10.1068/a270425.

46.

Osborne

M. J.

Rubinstein

1994. A Course in Game Theory. The MIT Press.

47.

Pedregosa

Varoquaux

Gramfort

, et al. 2011. “Scikit-Learn: Machine Learning in Python.” Journal of Machine Learning Research 12 (85): 2825–30. DOI: https://doi.org/10.5555/1953048.2078195

48.

Perez

Samothrakis

Lucas

2014. “Knowledge-Based Fast Evolutionary MCTS for General Video Game Playing.”Proceedings of the 2014 IEEE Conference on Computational Intelligence and Games, Dortmund, Germany, August 29–26.

49.

Polsby

D. D.

Popper

R. D.

1991. “The Third Criterion: Compactness as a Procedural Safeguard Against Partisan Gerrymandering.” Yale Law & Policy Review 9: 301–53. https://www-jstor-org-443.web.bisu.edu.cn/stable/40239359

50.

Rao

S. S.

2019. “Classical Optimization Techniques.” In Engineering Optimization Theory and Practice, edited by Rao

S. S.

John Wiley & Sons, Ltd. DOI: https://doi.org/10.1002/9781119454816.ch2.

51.

Robinson

W. S.

2009. “Ecological Correlations and the Behavior of Individuals.” International Journal of Epidemiology 15: 351–7. DOI: https://doi.org/10.1093/ije/dyn357.

52.

Swiechowski

Godlewski

Sawicki

Mańdziuk

2023. “Monte Carlo Tree Search: A Review of Recent Modifications and Applications.” Artificial Intelligence Review 56: 2497–562. DOI: https://doi.org/10.1007/s10462-022-10228-y.

53.

Tucker

Crampton

Swift

2005. “RGFGA: An Efficient Representation and Crossover for Grouping Genetic Algorithms.” Evolutionary Computation 13 (4): 477–99. DOI: https://doi.org/10.1162/106365605774666903.

54.

Wang

Guo

McLafferty

2012. “Constructing Geographic Areas for Cancer Data Analysis: A Case Study on Late-Stage Breast Cancer Risk in Illinois.” Applied Geography 35 (1): 1–11. DOI: https://doi.org/10.1016/j.apgeog.2012.04.005.

55.

Wang

Song

, et al. 2024. “A 3D Monte Carlo Tree Search Method for Railway Alignment Optimization.” Applied Soft Computing 151: 111158. DOI: https://doi.org/10.1016/j.asoc.2023.111158.

56.

Watts

2009. “Rules Versus Hierarchy: An Application of Fuzzy Set Theory to the Assessment of Spatial Grouping Techniques.” In Adaptive and Natural Computing Algorithms, edited by Kolehmainen

Toivanen

Beliczynski

Springer. DOI: https://doi.org/10.1007/978-3-642-04921-7_53.

57.

Watts

2013. “Assessing Different Spatial Grouping Algorithms: An Application to the Design of Australia’s New Statistical Geography.” Spatial Economic Analysis 8 (1): 92–112. DOI: https://doi.org/10.1080/17421772.2012.753637.