A bi-objective model for territorial design

Abstract

The clustering of spatial-geographic units, zones or areas has been used to solve problems related to Territorial Design. Clustering adapts to the definition of territorial design for a specific problem, which demands spatial data processing under clustering schemes with topological requirements for the zones. For small sized instances, once the geographical compactness is attended to as an objective function, this problem has been solved by exact methods with an acceptable response time. However, for larger instances and due to the combinatory nature of this problem, the computational complexity increases and the use of approximated methods becomes a necessity, in such a way that when geographical compactness was the only cost function a couple of approximated methods were incorporated giving satisfactory results. A particular case of this kind of problems that has had our attention in recent years is the classification by partitioning of AGEBs (Basic Geographical Units by its initials in Spanish). Some work has been made related to the formation of compact groups of AGEBs, but additional re-strictions were often not considered. A very interesting and highly demanded application problem is to extend the compact clustering to form groups with for some of its descriptive variables. This problem translates to a multi-objective approach that has to pursue two objectives to attain a balance between them. At this point, to reach a set of non-dominated and non-comparable solutions, a method has been included that allows obtaining the Pareto front through the Hasse diagram, which implies proposing a mathematical programming model and the synthetic resulting between compactness and homogeneity.

Keywords

Territorial design compactness homogeneity multi-objective

ï»¿

1. Introduction

Partitioning problems have been widely studied in the literature, however, their combinatorial nature makes their resolution difficult using exact methods due to the computational complexity associated with the hard NP category. When only one objective is treated, is possible to obtain good results in acceptable computational time. However, when partitioning is multiobjective partitioning problem, The difficulty lies in solving at least two aspects: (a) the generation of a set of suboptimal and non-dominated solutions and (b) the design of a partitioning algorithm that builds groups (clusters), simultaneously satisfying two objective functions. In other words, the existence of clustering problems for spatial data implies proposing solutions within the framework of partitioning with the use of heuristic methods, even with the incorporation of multi-objective techniques when dealing with more than one objective. In this sense, and especially for census grouping problems, the resolution focuses on obtaining compact and homogeneous groupings for population/census scenarios.

The grouping of census data with their respective variants presents serious problems given the selection of variables that will intervene in the grouping. On the other hand, the cluster must also be compact considering the spatial location of these data. This gives rise to proposing a method that groups census data with population characteristics to respond to homogeneity and, in parallel, geometrically compact groupings are achieved by taking the spatial position in $R^{2}$ .

To solve this problem, we have taken advantage of previous results on geographic partitioning [1], basic multi-objective theory [2], the Variable Neighborhood Search VNS heuristic [3], and Maxima properties [4].

At this point, the main contribution of this work is to integrate within the multi-objective partitioning algorithm both VNS to achieve approximate solutions and the multi-objective method based on order theory, which will choose from these solutions the ones that are not dominated.

In the territory design problem that is addressed, the objective is to obtain a partition of geographics objects (Basic Geostatistical Areas). Its composition is given by 2 components: geographic coordinates in the $R^{2}$ plane and a vector of 171 descriptive characteristics of a census character. The first component allows a distance matrix to be obtained for the geometric compactness calculation process, one of the objective functions to minimize. The description vector is used to optimize the second objective function, which consists of minimizing the homogeneity of some of the census variables, chosen based on some particular interest [5].

A set of solutions is sought, made up of partitions, where each element of the partition is geographically very close to each other such that the intra-group geometric compactness is satisfied. For the homogeneity objective, the balance is calculated for some census variables that define the problem and it is incorporated into the Variable Environment Search within the optimization process to achieve approximate solutions that conform to the process of identifying the non-dominated solutions (Minima) [3, 4].

This work is organized as follows: Introduction in Section 1. In Section 2 the definitions, basic concepts and brief state of the art are exposed. The model for compactness is described in Section 3. Section 4 presents the modeling for homogeneity. Section 5 deals with introducing multiobjective concepts and order theory. Finally, Section 6 exposes the application on a drainage problem and shows the set of solutions not dominated through the Minimum that are reflected in the associated Pareto Front. Finally the conclusions and references are presented.

2. Preliminaries

In science and engineering problems, the cost of evaluating the functions that describe them is high, specifically in optimization processes when the dimensions of the multi-objective search space are expanded, that cost rises exponentially.

Analytical optimization methods have been used for decades and for real problems, the number of variables that must be taken into account and the mathematical nature of the models require simplifications that allow the application of multi-objective strategies that support committed optimization with more than one criterion cost or fitness, which optimize objectives simultaneously by putting them in competition with each other, so that for each value of a fitness or cost function the best of the other objectives is obtained. Thus, the solution of the general problem is a combination of the optimal solutions of each objective, so said solution is not unique.

2.1 Related works

For the labor problems that we are presenting, some articles present different solutions, for example [6], have focused on improving an evolutionary metaheuristic based on vector evaluation to solve two multi-objective problems 1) environmental-economic dispatch and 2) portfolio optimization. The purpose is to deal with two populations independently and exchange information between them. The first population evolves according to the best individual of the second population and vice versa. The algorithmic choice will be executed in each generation stochastically between three evolutionary algorithms. To evaluate the results, the authors use an established metric in multi-objective evolutionary algorithms called hypervolume [6].

Multi-objective evolutionary algorithms (MOEA) optimize objectives by registering the solutions on the Pareto front. On the other hand, for the performance of the MOAS, the rate of convergence and the diversity of the population are used. In multi-objective clustering problems, to design a good algorithm with a high rate of convergence and diversity, k-means clustering is used because it provides diversity in the decision search space, then it is combined with a real-parameter version of the enhanced environmental adaptation method (IEAM-RP) because IEAM-RP converge very fast [7].

Vehicular networks have unique capabilities and are associated with vehicle communications to specific infrastructure to reduce traffic dynamics and support providers and the driver, then, it is possible to rely on security and communication alerts. Although the authors do not treat the problem as multi-objective, a subtle optimization/clustering way is identified in the location-allocation context to solve the neighborhood location registration and communications problem. The information of these messages in the communications is optimized and only important information is transmitted to the relevant vehicles and for the optimization of communication, an Artificial Bee Colony (ABC) swarm intelligence algorithm is used with a diffuse component with which, they achieve greater precision of optimization in the transmission of information with the minimum delay and with the lowest energy consumption [8].

For our work, we agree that the sets involved in this section are immersed in a metric space $(Z,\ d)$ (space where a metric or symmetric distance or triangular inequality $d$ is defined). Let $A$ be a subset of $Z$ , the power set of a set $A$ is denoted by $2^{A}$ and its cardinality by card(A).

A partition of a set $Z$ is a collection $P=\{G_{\alpha}:$ $\alpha\in I\}$ (where $I$ is the index of $i$ a $n$ ), of nonempty subsets, disjoint two by two, such that $Z=\cup_{\alpha}{G_{\alpha}}$ .

A k-partition of a set $Z$ is a partition of $Z$ of cardinality $k$ . If $P$ is a k-partition we denote $P=P_{k}$ . The class of all partitions of $Z$ is denoted by $P$ and the class of all k-partitions by $P_{k}$ .

It should be noted that the power set contains all the subsets, therefore, all the classes or groups that can be formed from $Z$ are subset of the power set.

The distance between two nonempty sets of objects $F$ and $G$ is defined as $d\left(F,\ G\right)=\min\{d\left(s,t\right):s\in F$ , $t\in G\}$ . It is convenient to point out that $s^{*}$ , $t^{*}$ are the set but they are distinguished elements. If $s$ , $t$ must be on the boundary then the distance would be zero. This idea gives rise to the following: the distance from an object $t$ to a nonempty set of objects $G$ is defined as $\left(t,G\right)=d\left(\left\{t\right\},G\right)$ . An object $\ t\in G$ is central, if its greatest distance to any other object is as small as possible, formally if we define the radius of $G$ as:

$\displaystyle\textit{rad}\left(G\right)={\min}_{t\in G}\left\{{\max}_{x\in G}% \left\{d\left(t,x\right)\right\}\right\}$

then $t\in G$ is central if for any $x\in G\ d\left(x,t\right)\leqslant\textit{rad}\left(G\right)$ . Given a set of objects $G$ , its diameter is defined as $\textit{diam}\left(G\right)={{\max}\left\{d\left(t,t^{\prime}\right):t,t^{% \prime}\in G\right\}\ }$ and it is interpreted as 2 times the radius and implies that there is intra-group connection.

By consistency for each $G$ we define $d\left(G,\emptyset\right)=\textit{diam}(G)y\textit{diam}\left(\emptyset\right)=0$ .

Considering that an object can be represented in the plane under a graph, the following is defined: An undirected graph is a pair of sets $G=\left(V,\ E\right)$ where $E=E(G)$ (set of edges of $G$ ) is a subset of the set of binary subsets of $V=V\ (G)$ (set of vertices or nodes of $G$ ).

The order of $G$ is the cardinality of $V$ and is denoted by $G$ . A graph $G$ is connected if for any two different nodes $u,wV(G)$ there is a path or path that connects them, that is, a sequence of edges of $G$ of the form $\left\{v_{0},v_{1}\right\},\left\{v_{1},v_{2}\right\},\ldots,\left\{v_{n-1},v_% {n}\right\}$ , donde $u=v_{0}yw=v_{n}$ [9].

If a graph is not connected, we say that it is disjointed or disconnected. If the distance between $v_{1},v_{2}$ is different from zero, it is understood that the line joining $v_{1}$ and $v_{2}$ keeps them within the class or group and the intragroup connection is indirectly satisfied.

Statement 1. A component of $G$ is a maximally connected subgraph of $G$ .

Statement 2. A subset $X$ separates $G$ if $G-X$ is disjointed. A graph $G$ is said k-connected $\left(k\in\mathbb{N}\right)$ , if $\left|G\right|>k$ and $G-X$ is connected for all $X\subseteq V$ with $\textit{card}\left(X\right)<k$ . The connectivity of a graph $G$ , denoted by $k(G)$ , is the maximum integer $k$ such that $G$ is k-connected (there is a graph $G$ and inside of it is $X$ where $k$ speaks of the degree of connection of the graph).

3. Compactness

Geometric compactness in land design has not been precisely defined. In this context, the researchers have concentrated on describing the measure quantitatively based on the problem, which has implied the existence of many compactness proposals [10].

Intuitively, geometric compactness can be understood when we imagine that the shape of each area grouping resembles a square, a circle or a convex geometric figure, this means that in some cases the measurements are not totally convincing [11]. In other words, geometric compactness has been expressed as a condition that seeks to avoid the creation of areas of irregular or non-polygonal shape. It is also considered that the compactness constitutes clarity in the delimitation of the zones and it has been appreciated that the compact zones are easier to administer and evaluate due to the reduction of transfer times and communication difficulties [12].

According to the above, we have defined compactness as follows:

Definition 1. We say that there is compactness when several objects are brought together very closely so that there are no gaps or few are left in such a way that the idea that the objects towards a center that represents a group have a minimum distance is fulfilled.

To formalize this idea when the objects are AGEBs, the distance between groups is first defined.

Definition 2. Compactness

If we denote by $Z=\{1,2\ldots,n\}$ the set of $n$ objects to be classified, we try to divide $Z$ into $k$ groups $G_{1},G_{2},{\ldots,G}_{k}$ , with $k<n$ , in such a way that:

$\displaystyle\bigcup\nolimits^{k}_{i=1}{G_{i}=Z}$ $\displaystyle G_{i}\bigcap{G_{j}=\emptyset}\ \ \ \ i\neq j$ $\displaystyle\left|G_{i}\right|\geqslant 1\ \ \ \ \ \ \ \ \ \ i=1,2,\dots,k$

A group $G_{m}$ with $\left|G_{i}\right|>1$ it is compact if for each object $t\in G_{m}$ it meets the following inequality called for this problem as neighborhood criterion (NC), that is, the NC between objects to achieve compactness is given by the pairs of distances

$\displaystyle{{\min}\ d\left(t,i\right)\ }<{{\min}\ d\left(t,j\right)\ }$ $\displaystyle i{\in}G_{m}\ \ \ \ \ \ \ \ \ \ j{\in}Z{-}G_{m}$ $\displaystyle i{\neq}t$

A group $G_{m}$ with $\left|G_{m}\right|=1$ is compact if its object $t$ fulfills:

$\displaystyle{{\min}\ d\left(t,i\right)\ }<{{\max}\ d\left(j,l\right)\ }$ $\displaystyle i{\in}Z{-}\left\{t\right\}\ \ \ \ \ \ \ j,l{\in}G_{f}\ \ {% \forall}f{\neq}m$

An example of how two objects meet the above constraints is shown in Fig. 1.

Figure 1.

Four compact groups.

Considering the previous, a group $G$ is compact if it is better to move to a central object of the same group than to go to any object of another group $F$ . In formal terms, the following definition is available:

Definition 3. A set of objects $G\in 2^{Z}$ is compact if for any central object

$\displaystyle z\in Z-G\textit{holds rad(G)}\leqslant d(G,z)$ (1)

A partition $P$ is compact if for any $G\in P$ Eq. (1) is satisfied in every central object $z$ of the elements of the participation $P$ .

Note that with this definition the space $Z$ is compact, this may suggest that the trivial input $P_{1}=\left\{Z\right\}$ satisfies the desired characteristics since it is clear that $\textit{rad(G)}<\textit{diam(G)}$ (see Fig. 2).

Figure 2.

Compactness representation.

Another useful way of looking at the compactness of a group $G$ is to think that its elements are “close together”, that is, as close as possible. In more formal terms, its radius is close to zero, that is, the radii are very small.

$\displaystyle\textit{rad(G)}\to 0$

Taking into account the previous observation, it is define the compactness of a partition as follows:

Definition 4. Given a partition $P$ of $Z$ , its compactness is defined as

$\displaystyle\textit{compac}\left(P\right)=\sum\limits_{G\in P}{\textit{rad(G)}}$ (2)

The following proposition establishes an equivalence with Definition 1.

Proposition 1. The partition $P_{0}$ is compact if and only if

$\displaystyle\textit{compac}(P_{0})=\min\left\{\textit{compac}\left(p\right):P% \in\mathbb{P}\right\}$ (3)

Demostration. If $P_{0}$ is compact, then for $G\in P_{0}$ , is fulfilled $\textit{diam(G)}\leqslant d\left(G,Z-G\right)$ . For sufficiency, if the partition $P_{0}$ is not compact, then there exists $G^{\prime}\in P_{0}$ such that $\textit{diam}\left(G^{\prime}\right)>\ d\left(G^{\prime},Z-G^{\prime}\right)$ , let $g_{1},g_{2}\in G^{\prime}$ such that $\textit{diam}(G^{\prime})=d(g_{1},g_{2})yr=d\left(G^{\prime},Z-G^{\prime}\right)$ . If $G^{\prime\prime}=\left\{g\in G^{\prime}:d\left(g,g_{1}\right)<r/2\right\}$ hence

$\displaystyle\sum\limits_{G\in P}\textit{diam}\left(G\right)>d\left(G^{\prime}% ,Z-G^{\prime}\right)$ $\displaystyle\quad+\sum\limits_{G\in P-\{G^{\prime}\}}{\textit{diam}(G)}$

4. Homogeneity

There is an imprecision in terms of homogeneity and balance. What we are trying to find is that the groups of zones have equilibrium or balance with respect to one or more properties of the geographical units that form them. For example, zones can be designed that have the same workload, the same travel times, or the same percentages of socio-economic representation. In general, it is not possible to achieve the exact equilibrium, therefore, it is chosen to calculate the deviation with respect to the ideal arrangement. The greater the deviation, the worse the equilibrium of the zone.

4.1 Population balance

In the design of zones for a logistical problem, for example, it is desirable that all zones contain the same amount of population or at least that the population difference between each zone is the minimum possible to optimize transfers. Different measures can be defined to calculate the population balance of zones, how-ever, each measure depends on the specific problem and all of them lead to very similar results.

The formulas for homogeneity are listed below:

1.
The simplest way to measure the population balance is to add the absolute values of the difference between the population of each area and the population average per area

$\displaystyle\sum{\left|P_{i}-P\right|}$

where $P_{i}=$ population of the zone $i$ , $\overline{P}=$ average population per area given by $\overline{P}={\sum_{k\in K}{P_{k}}}/{n}$ , $n=$ number of zones to create, $K=$ set of all geographic units, $P_{k}=$ Population of geographic unit $k$ .
2.
The difference in population between the most populated area and the least populated area $\frac{P_{i}}{\textit{MAX}}-\frac{P_{k}}{\textit{MIN}}$

Sometimes this difference is divided by the population average $\frac{P_{i}}{\textit{MAX}}-\frac{P_{k}}{\textit{MIN}}\ /\overline{P}$
3.
The division of the most populated area by the least populated ${\frac{P_{i}}{\textit{MAX}}}/{\frac{P_{k}}{\textit{MIN}}}$
4.
The following method is given by the function

$\displaystyle\sum_{j\epsilon J}\max\{P_{j}-(1+\beta)\overline{P},$ $\displaystyle\quad(1-\beta)\overline{P}-P_{j},0\}/P$

Where: $J=$ set of all zones, $P_{j}=$ population of the zone, $\beta=$ Population standard deviation percentage.

In this way, it is sought that the population of each area is within the interval $\left[\left(1-\beta\right)\overline{P,}\ \left(1+\beta\right)\overline{P}\right]$ with $0\leqslant\beta\leqslant 1$ .

It is observed that this function will take the value of 0 if the population of each zone is in the interval $\left[\left(1-\beta\right)\overline{P,}\ \left(1+\beta\right)\overline{P}\right]$ . Otherwise, it will take a positive value equal to the sum of the deviations with respect to these levels [13].
4.2 Homogeneity for variables

Homogeneity for spatial data of a population makes sense when the values of the population variables in a grouping process have “more or less” the same values, that is, homogeneous groups are those that want the groups to maintain ap-proximately the same amount of a population variable, for example, each group having roughly the same number of inhabitants.

Homogeneous grouping has many applications; It is useful when you want to obtain groups of zones to which workloads or resources must be assigned equally.

For example, assume that it is necessary to supply a state of the republic with a service $x$ that is provided by machine $m$ ; if the machine $m$ can only supply houses $v$ , then totalhomes/v machines would be needed to supply the entire state, then it is possible to divide the state into groups that maintain homogeneity regarding the population variable “number of dwellings” and thus assign each group or zone a machine.

4.3 Homogeneity over agebs for population variables

If we denote by $Z=\left\{1,2,\ldots,n\right\}$ the set of n objects to be classified and $V_{1},V_{2},\ldots,V_{n}$ the set of values of the variable of which we want to keep the groups homogeneous, we try to divide $Z$ in $k$ groups $G_{1},G_{2},\ldots,G_{k}$ with $k<n$ , such that:

$\displaystyle\bigcup\nolimits^{k}_{i=1}{G_{i}=}Z$ $\displaystyle G_{i}\bigcap{G_{j}=\emptyset}\ \ i\neq j$ $\displaystyle\left|G_{i}\right|\geqslant 1\ i=1,2,\ldots,k$

A group $G_{m}$ is homogeneous if it meets:

$\displaystyle\sum\limits_{j{\in}G_{m}}{V_{j}}{\approx}\frac{{1}}{k}\sum\limits% ^{n}_{i{=1}}{V_{i}}$

When only homogeneity is considered, the results are not practical since in the absence of compacidade, the dispersion of the objects is an expected consequence (see Fig. 3) [14].

Figure 3.

The solution to the homogeneous classification in which the objects that make up each of the four groups are scattered throughout the state. Each group has roughly the same number of dwellings.

According to the above, a desirable characteristic is that the groups in an area have a balance with respect to one or more properties of the geographic units that form them. A population variable can be considered as a function $X$ with domain a subset $G$ of a population $Z$ and with values in the real numbers $X:2^{Z}\to\bm{{R}}$ .

For example, $X(G)$ can be the number of inhabitants in zone $G$ , or it could represent the number of dwellings in zone $G$ among many other population parameters.

Definition 5. A partition $P$ is homogeneous with respect to the population variable $X$ if $X\left(F\right)=X(G)$ for any $F$ ; $G\in P$ .

Note that Definition 5, in practice, turns out to be an ideal condition, since in many territorial design problems this condition is clearly impossible. To cite an example, if $X$ is a variable that represents the number of economically active women in an area, it is difficult to obtain a homogeneous non-trivial partition with this condition. However, Definition 6 gives us the guideline to propose a definition with a more practical utility.

Definition 6. A partition $P$ is $(\leftthreetimes,\mu)-\textit{homog\'{e}nea}$ or quasi-homogeneous with respect to the population variable $X$ if for all $G\in P$ it is fulfilled

$\displaystyle\left|X(G)-\mu(G)\right|\leqslant\leftthreetimes$ (4)

where $\leftthreetimes$ is a real no negative number and $Î ¼$ is a function $\mu:2^{Z}\to\textbf{R}$ .

Note that a $(\leftthreetimes,\mu)-\textit{homogenuos}$ partition is homogeneous if we choose $\leftthreetimes=0$ and $\mu$ a constant function over the elements of $P$ . Also $\leftthreetimes$ is a bound for the homogeneity error. The determination of the parameter $\leftthreetimes$ and the function $\mu$ are determined depending on the characteristics of the problem and the opinion of the expert.

If a partition $P$ is $(\leftthreetimes,\mu)-\textit{homogeneuos}$ and $F,G\in P$ , from the triangle inequality we have

$\displaystyle\left|X\left(F\right)-X(G)\right|\leqslant 2\leftthreetimes+\left% |\mu\left(F\right)-\mu(G)\right|$ (4.1)

Then if the bound for the homogeneity error is small and the function $Î ¼$ is close to a constant function, which implies that $X(F)$ and $X(G)$ are considered to be “very similar”.

In many problems of territorial design, more than one population variable may intervene, for example, it may be desirable to consider an area $G$ where the population variables are considered: $X$ and $Y$ , where $X(G)$ represents the number of inhabitants in the area and $Y(G)$ the number of economically active residents. Then Definition 5 can be given in more general terms as follows.

Definition 7. A partition $P$ is $(\leftthreetimes,\mu)-\textit{homogeneous}$ or quasi-homogeneous with respect to the population variable vector

$\displaystyle X\left(G\right)=(X_{1}\left(G\right),\ldots,X_{n}\left(G\right))% \ \text{if for all}G\in P\left|X_{i}\left(G\right)-\mu_{i}(G)\right|\leqslant{% \leftthreetimes}_{i}\text{ is satisfied}$ (5)

for each $i\ =\ 1,2,\ldots,n$ where $\leftthreetimes={\leftthreetimes}_{1},{\leftthreetimes}_{2},\ldots,{% \leftthreetimes}_{n}$ and for each $i=$ 1,2, $\ldots,n,{\leftthreetimes}_{i}$ is a real no negative number and $\mu\left(G\right)=(\mu_{1}\left(G\right),\ldots,\mu_{n}\left(G\right))$ where $\mu_{i}$ are real valued functions over the subsets of $Z$ to each $i=1,2,\ldots,n$ . Notice that if $\left.X\left(G\right)-\mu(G)\right.\leqslant\leftthreetimes$ , then Definition 6 is fulfilled, although this would be a more simplified way of defining quasi-homogeneous partitions, there is the disadvantage that the bounds of the homogeneity errors would be uniform. However, if for all ${G}\in{P}$ the modulus of each component of the vector $X\left(G\right)-\mu(G)$ is zero, then the partition $P$ is $(\leftthreetimes,\mu)-\textit{homogenueous}$ for any $\leftthreetimes$ vector with non-negative components.

Definition 8. The $\mu-\textit{homogeneity}$ of a partition $P$ with respect to the population variable vector $X\left(G\right)$ is defined by

$\displaystyle\textit{hom}_{\mu}\left(P\right)=\left.X\left(G\right)-\mu(G)\right.$ (6)

where $\mu$ , is like in Definition 4. Notice that if $\textit{hom}_{\mu}$ $\left(P\right)=0$ , $\mu=\left(c,c,\ldots,c\right),c$ and non-negative integer, then $P$ partition is homegenueous.

5. Understanding a multi-objective problem

In the search for strategies that support the simultaneous optimization of more than one cost or aptitude criterion, multi-object optimization arises, which seeks to optimize objectives simultaneously and in competition, in such a way that for each value of a cost function it is obtained the best combination of objectives. This situation indicates that the solution of this type of problem is a combination of the optimal solutions for each objective, so this solution is not unique [15, 16].

It is possible to say that the implementation of algorithms to solve multiobjective optimization problems is divided into two categories that obey the type of objective functions used. The first group assumes low computational cost objective functions and the overall efficiency of the optimization algorithms is pursued. The second group focuses on building algorithms where the computational cost is high. In this situation it is assumed that the biggest problem is centered on the space of solutions and the competition between the objective functions, therefore, it is interesting that the algorithmic procedure in the optimization reduces the number of evaluations of the cost functions since it has been experienced that computationally, these govern the duration and process of the optimization.

In general, it is true that most of the optimization problems in the real world are non-linear and multimodal, with more than one objective to solve, which are contradictory to each other and subject to various complex constraints. Even for single-objective problems, it is common that there are no optimal solutions that will satisfy them. Consequently, multi-objective optimization is defined as the problem of finding a vector of decision variables that satisfies certain restrictions and optimizes a vector of functions whose elements represent the objective functions [17]. Multi-objective optimization is not restricted to the search for a single solution, but for a set of solutions called Non-Dominated solutions. Each solution of this set is said to be a Pareto Optimum and they are represented in the space of the values of the objective functions, which make up what is known as the Pareto Front.

In a specific problem, obtaining the Pareto Front is the main purpose of Multiobjective Optimization. Multi-objetive scheme.

Multi-objective problems can be made clearer by identifying the relationships between the characteristics of the problem, its constraints, and the main objectives to be improved together. For these types of problems, it is possible to have an expression as a mathematical function. When referring to the improvement as a whole, it is said that all functions must be optimized simultaneously, thus defining a problem of the type described below:

Definition 9. A multiobjective problem (MOP) can be defined in the minimization case (and analogously for the maximization case) as

Minimize $f(x)$

Given the $f:F\subseteq R^{n}\to R^{q},q\geqslant 2$

and is evaluated in

$\displaystyle A=\{a\in F:g_{i}(a)<=0,i\in 1,\ldots,\}\}\neq\emptyset$

5.1 Pareto front

Definition 10. Pareto Dominance DP. It is said that a vector $\overrightarrow{u}=\left(u_{1}\ldots,u_{k}\right)$ dominates to $\overrightarrow{v}=$ $\left(v_{1}\ldots,v_{k}\right)$ (denotes by $\overrightarrow{u}\preccurlyeq\overrightarrow{v}$ if and only if is partially less than $\overrightarrow{v}$ . Therefore, if $u_{i}\leqslant v_{i}\forall i\in\left\{1,\ldots,k\right\}\ y\ \exists i\in% \left\{1,\ldots,k\right\}:u_{i}<v_{i}$

Another common option to be used as Pareto dominance is expressed as:

Definition 11. Given the multi-objetive problem to minimize:

$\displaystyle f_{x}\ \text{where}\ f:F\subseteq R^{n}\to R^{q}q\geqslant 2$

with $A\subseteq F$ the factible area. It is said that a vector $x^{*}\in A$ it is not dominated by a Pareto optimal if there is not a vector $x\in A$ such as $f_{\left(x\right)}<f_{\left(x^{*}\right)}$ .

In this way, the answer to the problem of finding non-dominated solutions is known as the solution set of the problem. In the other hand, the group of values of the objective function with domain restricted to the vectors of the solution set (the non-dominated vectors), is what is well know as the Pareto front.

In summary, the Pareto optimal set is the solution space of the problem and the Pareto Front is its image with respect to the function $f:F\subseteq R^{n}\to R^{q}q\geqslant 2$ to optimize.

The Pareto optimal for a given multiobjective problem is a partially ordered set, seen formally. In multiobjective problems, we look for the minimal elements of the solution space $R^{n}$ seen as a post-set, in the relation $\leqslant$ defined in a natural way [5].

5.2 Order relations

Definition 12. Let $A$ be an non-empty set and $R$ a binary relation defined in $A$ , it is said that $R$ is a order relation if meets.

Reflexivity: Every element of A is related to itself, that is to say $\forall x\in A,xRx$

Antisymmetry: If two elements of $A$ are related to each other, then they are equal, that is, $\forall x,y\in A,xRy,\ yRx\Rightarrow x=y$

Transitivity: $\forall x,y,z\in A,xRy,yRx\Rightarrow x=y$

A relation of order R on a set A can be denoted by the ordered pair $\left(A,\leqslant\right).$

Definition 13. A binary relation that satisfies being reflexive, antisymmetric, and transitive is called a partial order relation and is commonly represented by the symbol $\left(\preccurlyeq\right)$ .

Definition 14. A partial order is a binary relation R on a set A that is reflexive, antisymmetric, and transitive, that is, for any a, b, and z in A we have:

$a R a$ (reflexivity).

If $a R b$ y $b R a$ , then $a=b$ (antisymmetric).

If $a R b$ y $b R z$ , then aRz (transitivity).

Definition 15. Given $A$ a set and $\left(\preccurlyeq\right)$ a partial order relation on it, we call the pair $\left(A,\preccurlyeq\right)$ a partially ordered set also referred to as Poset.

Definition 16. Given $\left(A,\preccurlyeq\right)$ a Poset, the subset $X\subseteq A$ is said to be a total order or chain with respect to $\left(\preccurlyeq\right)$ , if and only if, it is satisfied that $x\prec y$ or $y\prec x$ for all x, $y\in X$ . In this case it is said that $\left(X,\preccurlyeq\right)$ is a totally ordered set.

If we have $\left(x\preccurlyeq y\right)$ for all $\left(x,y\right)\in X$ , we say that $X$ is an antistring. Chains can be finite or infinite and can also be stationed at one end like:

$\displaystyle x_{0}\prec x_{1}\prec x_{2}\ldots\prec x_{i-1}\prec x_{i}\prec x% _{i+1}\prec\ldots$ $\displaystyle\ldots\prec x_{i+1}\prec x_{i}\prec x_{i-1}\prec\ldots\prec x_{2}% \prec x_{1}\prec x_{0}$

The following statement is of vital importance to generate non-dominated solutions:

From a partial order, the dominance relationship $\left(\prec\right)$ can be defined as follows:

$\displaystyle x\prec y\Longleftrightarrow x\preccurlyeq y\wedge x\neq y$

When it happens that $\left(x\preccurlyeq\!\!\!\!\!/\ y\right)$ and $\left(y\preccurlyeq\!\!\!\!\!/\ x\right)$ are said to be non-comparable, which is denoted by $x||y.$

Lemma 1. Zorn Lemma (Kuratowski-Zorn). Every non-empty partially ordered set in which every chain (fully ordered subset) has an upper bound, contains at least one maximal element.

A maximal element of a partially ordered set $P$ is an element of $P$ that is not less than any other. The term minimal element is defined in a dual way.

Let $\left(P,\ \leqslant\right)$ be a partially ordered set; $m\in P$ is a maximal element of $P$ if the only $x\in P$ such that $m\leqslant x$ is $x\leqslant m$ . The definition of minimal element is obtained by replacing $\leqslant$ por $\geqslant$ .

Definition 17. An element $x^{*}\in A$ is called the minimal element of the poset $\left(A,{\preccurlyeq}\right)$ if there is no element $x\in A$ such that $x\prec x^{*}$ . The set of all minimal elements is denoted $M\left(A,{\preccurlyeq}\right)$ .

Definition 18: The set $M\left(A,{\preccurlyeq}\right)$ .of all minimal elements of $\left(A,{\preccurlyeq}\right)$ is said to be complete if for each $x\in A$ there is at least one element $x^{*}\in M\left(A,{\preccurlyeq}\right)$ such that $x^{*}\prec x$ .

Lemma 2. Given a poset $\left(A,{\preccurlyeq}\right)$ such that A is finite, it is true that its set of minimal elements $M\left(A,{\preccurlyeq}\right)$ is complete.

Proof:

Let $x_{0}\in A$ . If $x_{0}\in M\left(A,{\preccurlyeq}\right)$ , the lemma is true because of the reflectivity property $\preccurlyeq$ . Suppose then that $x_{0}\notin M\left(A,{\preccurlyeq}\right)$ .This implies that there exists an element $x_{1}\in A$ such that $x_{1}\preccurlyeq x$ . Since $A$ is finite, there exists an element $x_{n}$ for some string $x_{n}\preccurlyeq\ldots\preccurlyeq x_{1}\preccurlyeq x_{0}$ with $n\leqslant\left|A\right.$ in which the transitive chain stops, this means that no element of A dominates $x_{n}$ and therefore it follows directly that $x_{n}\in M\left(A,{\preccurlyeq}\right)$ .

Lemma 3. Let $M\left(A,{\preccurlyeq}\right)\neq\emptyset$ be the set of minimal elements of some partially ordered set $(A,\preccurlyeq)$ . Let $x\in A$ also be the set

$\displaystyle G\left(x\right):=\left\{y\in A:y\preccurlyeq x\right\}:$

So it fulfills the following implications:

(a) $x\in M\left(A,{\preccurlyeq}\right){\Leftrightarrow}G\left(x\right)\diagdown% \left\{x\right\}=\emptyset$

If $M\left(A,{\preccurlyeq}\right)$ is completed and $x\notin M\left(A,{\preccurlyeq}\right)$ then $\left(G\left(x\right)\diagdown\left\{x\right\}\right)\cap M\left(A,{% \preccurlyeq}\right)\neq\emptyset$

Proof:

By definition $x\in M\left(A,{\preccurlyeq}\right){\Leftrightarrow}\left({\nexists}{}y{\in}A;% y\prec x\right)$ ${\Leftrightarrow}\left({\nexists}{}y{\in}A;y{\preccurlyeq}x\mathrm{\wedge}y{% \neq}x\right)$

They are certain implications. The last expression can be written as $\left(\nexists y\in G\left(x\right):y\neq x\right)$ . This is equivalent to saying that $G\left(x\right)\diagdown\left\{x\right\}=\emptyset$ .

Let $\epsilon\ A$ such that $x\notin\epsilon M\left(A,{\preccurlyeq}\right)$ . Considering part, a) it is a fact that $G\left(x\right)\diagdown\left\{x\right\}=\emptyset$ . Since $M\left(A,{\preccurlyeq}\right)$ is complete we can say that there exists an element $x^{*}\epsilon\ M\left(A,{\preccurlyeq}\right)$ such that $x^{*}\neq x\wedge x^{*}\prec x$ . Then, using the definition, we conclude that necessarily $x^{*}\in G\left(x\right)\diagdown\left\{x\right\}$ , therefore, $\left(G\left(x\right)\diagdown\left\{x\right\}\right)\cap M\left(A,{% \preccurlyeq}\right){\neq}{\emptyset}$ .

To conclude this subsection, minimal and maximal are cited as components of a Hasse diagram.

5.3 Maximal and minimal elements in a Hasse diagram

Let $(A\leqslant)$ be a CPO. Let $m,n\in A$ . Then,

1.
$n$ is a maximal element in $A$ if and only if $(\forall x)(n\ \leqslant x\Longrightarrow n=x)$ .
2.
$m$ is a minimal element in $A$ if and only if $(\forall x)(x\leqslant m\Longrightarrow x=m)$ .

Intuitively, an element n of a CPO $(A\leqslant)$ is maximal of $A$ if there is no element in $A$ that is strictly greater than $n$ .

Similarly, an element $m$ of $A$ is a minimal of $A$ if there is no element of $A$ that is strictly less than $m$ [18, 19].
6. Metodology

A partition of spatial data is sought whose composition is given by 2 components: geographic coordinates in the $R^{2}$ plane and a vector of 144 descriptive characteristics of a census character.

The first component determines a distance matrix to optimize geometric compactness (goal 1: minimization of Euclidean distances). The vector of population variables is used to optimize homogeneity (second objective: minimize some of the census variables). The problem to be solved must be described based on the population variables, therefore, before optimizing the objective functions, a selection of the variables of interest is necessary [20].

In this sense, the partition that is sought is a set of solutions such that each one is made up of objects that are geographically very close and balanced for some census variable. Under these conditions, we are facing a bi-objective problem of territory design and high computational complexity, a situation that requires the use of heuristic methods to achieve approximate solutions and multi-objective techniques to find a set of pairs of non-dominated solutions that form the front of Pareto.

6.1 Solution strategy

The problem to be solved is partitioning in TD, it is discrete, combinatorial, integer-mixed where the partitioning takes geographic objects as objects to be grouped and the algorithm considers a cost function that minimizes distances between objects and centroids and that according to the partitioning by medoids, compactness is indirectly satisfied provided that Definitions 1–3 and/or Proposition 1 of Section 3 are incorporated into the construction of the groups in the implementation. On the homogeneity side, this is optimized by seeking a balance between a census variable of interest. Both homogeneity and compactness are optimized at the same time to obtain the set of non-dominated solutions.

The grouping strategy consists of randomly choosing objects as centroids that identify the number of groups. Those non-centroid objects that have the shortest distance to a given centroid are the members of a group. This idea together meets the convenient compactness properties and is implemented in the creation of groups under the minimization of distances. At the same time, the homogeneity of the created grouping is calculated since the domain in this problem is a partition, that is, in multi-objective problems the function to be optimized has the same domain for all objectives, thus on the same partition compactness and homogeneity are optimized [21]. At this point it is important to observe that in multi-objective optimization problems the best alternative $x$ is chosen from a set $X$ with respect to a broad and imprecise objective. A hierarchy of objectives is then introduced, the lowest level $m$ being sufficiently precise to allow the results of each alternative to be measured. Thus, one has to choose the best alternative with respect to the m objectives. Mathematically, we have a set $X$ subset $R^{n}$ of space of alternatives and $m$ applications $f_{i}:X\to R,i=1,\ldots,m$ that represent the $m$ objectives.

The heuristics incorporated into the grouping algorithm should focus on finding a random initial solution (current solution), which is a partition where compactness and homogeneity have been minimized, obtaining a pair $\left(c_{i}h_{i}\right)$ . The following solution $\left(c_{i}+1,h_{i}+1\right)$ is generated and compared with the previous one according to Pareto order. If this new solution $\left(c_{i}+1,h_{i}+1\right)$ is not comparable with respect to $\left(c_{i}h_{i}\right)$ it is labeled as minimal and becomes the current solution to be compared with the “next” iteratively until the parameters of the heuristics meet the stop criterion, then the set of non-dominated and non-comparable solutions is obtained, understood in the order theory as minimals that form a Hasse diagram and consequently construct the Pareto Front.

7. Application

The goal is obtaining a set of groups of spatial data which composition is given by two components: geographical coordinates on the plane ${R}^{2}$ and a vector of census descriptive characteristics. The first component allows obtaining a distances matrix to process the geometric compactness calculus, one of the objective functions to minimize.

The description vector is used to optimize the second objective function and consists in minimizing the homogeneity of a given census variable. The selection of the variables will be made over the data that relates the population to the tap water and drainage network services [22].

According to the National Institute of Statistics and Goegraphy (INEGI) their census data have allowed making diagnoses about sufficiency or deficit of services at home. These indicators have been the base to develop construction, expansion, improvement, financing and characterization strategies for houses. With the census variables it will be possible to carry out studies about the deterioration of houses, the access to basic services that provide comfort, ease the domestic work and improve the quality of life.

We focus in offering a partitioning of 2 groups of population related to tap water and drainage network services. These groups are formed by spatial objects known as Agebs. Each Ageb consists of a vector of variables, which represent geostatistical data from a census.

An important factor is making a decision about the viability of assigning resources to vulnerable population sector. We have chosen the population with partial tap water and drainage network services as study case. This means that the variables described on the list below are the ones that participate in the grouping and to make sure all of the Agebs are involved; we have filtered the variables with values between 0 and 100%.

Assuming that there is a government program to support this population sector, they need a set of groupings that show the distribution of this population regarding the following census variables, which are strongly related with each other:

Z119 Total of inhabited houses. Z120 Inhabited private houses. Z137 Private houses with drainage connected to the septic tank, ravine, crack, river, lake or sea. Z138 Private houses without drainage network service. Z140 Private houses with tap water inside the building. Z141 Private houses with tap water within the land. Z142 Private houses with tap water available by transportation (public water tap or from another home) Z143 Private houses that only have tap water and drainage network services. Z144 Private houses that only have drainage network and electricity services. Z145 Private houses that only have tap water and electricity services. Z146 Private houses that have tap water, drainage network and electricity services. Z147 Private houses that don’t have tap water, drainage network nor electricity services. Z136 Private houses with drainage connected to the public network [22, 23].

7.1 Application description

A model prior to the one presented in this work was developed and applied to the variables related to water and drainage described in the previous paragraph. It was considered that 8, 32 and 64 groups maintaining homogeneity in the variable private houses that don’t have tap water, drainage nor electricity services (Z147) [19].

Since in this work we have proposed a new model with the objective functions of Sections 3 and 4, we present here a different test with two groups but without altering the Pareto dominance strategy for the non-dominated solutions.

The first column of Table 1 belongs to the cost of the homogeneity function $(H)$ and the second, to the cost of compactness $(C)$ . These solutions are the non-dominated set, that is, we have reached the Pareto Frontier where we use 14 variables related to the services of running water and the drainage network, trying to balance the homogeneity in the variable Z147 and respecting the geometric compactness.

7.2 Result of a bi-objective partition with two groups

Table 1
Maximum solutions that form the pareto front

Compactness	Homogeneity
4040111	135
4596369	5
4308580	11
4065591	131
4130026	73
3940426	273
4832540	1
3842965	551
3861364	455
3881083	359

In Fig. 4 it can be seen that the Pareto front has been formed according to the non-dominated solution method applied to the problem of water and drainage.

Figure 4.

Pareto chart for the problem about houses with drainage and water problems.

8. Conclusions

If the decision maker is interested in sacrificing compactness or homogeneity he must choose a solution from the marked points of the graph.

Since it is a minimization problem, the values in Table 1 of the previous section correspond to the minimums for the objectives of compactness and homogeneity.

An important contribution is that the multiobjective technique in this work has overcome the problems where Pareto dominance through minimals did not achieve an adequate set of solutions and some pairs of dominated solutions lagged behind minimals [5, 23].

However, this problem was solved with another modeling although, it generated satisfactory results, it has been important to express homogeneity and compactness in another way to determine if the implementation of the measures that we have included in this manuscript are better than in past implementations, which it is translated as future work, however, the authors estimate that the current modeling exceeds our previous contributions. On the other hand, the model for compactness and homogeneity is innovative, however, other restrictions still need to be addressed and the model faithfully implemented, which translates into future work.

References

Bernábe

M.B.

Ramírez

R.J.

and Espinosa

R.J.

, Evaluación de un Algoritmo de Recocido Simulado con Superficies de Respuestas, Revista de Matemáticas Teoría y Aplicaciones 16(1) (2009), 159–177.

Marler

R.T.

and Arora

J.S.

, Survey of multi-objective optimization methods for engineering, Structural and Multidisciplinary Optimization 26 (2004), 369–395.

Mladenovic

and Hansen

, Variable Neighborhood Search, Computers & Operations Research 24(11) (1997), 1097–1100.

Kung

Luccio

and Preparata

, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM) 22(4) (1975), 469–476.

Bernábe

M.B.

Pinto

Ruiz-Vanoye

J.A.

Espinosa

and Olivares

, A multi-objective proposal for the aggregation of economically inactive population, International Journal of Combinatorial Optimization Problems and Informatics 3(1) (2012), 70–79.

Corrêa

F.L.

Cortes

O.A.

and Costa

J.P.

, An enhanced auto adaptive vector evaluated-based metaheuristic for solving real-world problems, International Journal of Hybrid Intelligent Systems 2021; Pre-press(Pre-press): 1–12.

Tribhuvan

, Handling multiple objectives using k-means clustering guided multiobjective evolutionary algorithm, Expert Systems 39(4) (2022).

Arifa

Wanga

Penga

Balasb

V.E.

Gemanc

and Chena

, Optimization of communication in VANETs using fuzzy logic and artificial Bee colony, Journal of Intelligent & Fuzzy Systems 38 (2020), 6145–6157.

Diestel

, Graph Theory. Springer, 4th ed., 2010.

10.

Niemi

R.G.

Grofman

Carlucci

and Hofeller

, Measuring Compactness and the Role of a Compactness Standard in a Test for Partisian and Racial Gerrymandering, Journal of Politics 52(4) (1990), 1155–1181.

11.

Young

H.P.

, Measuring the Compactness of Legislative Districts, Legislative Studies Quarterly 13(1) (1988), 105–115.

12.

Bélanger

and Eagles

, The compactness of federal electoral districts in Canada in the 1980s and 1990s: an exploratory analysis, Canadian Geographer 45(4) (2001), 450–460.

13.

Rincón

, Diseño de zonas geométricamente compactas utilizando celdas cuadradas, Tesis Doctoral, Posgrado de Ingeniería, Investigación de Operaciones, UNAM (2009), 19–22.

14.

Bernóbe

M.B.

Pinto

Olivares

B.E.

González

V.R.

Martinez

F.J.

and Ruiz-Vanoye

J.A.

, A hybrid metaheuristic for the partitioning problem with homogeneity constraints on the number of objects, ICAOR 2012 (2012), 202–211.

15.

Deb

, Multi-Objective Optimization using Evolutionary Algorithms, John Wiley & Sons, Inc. Marler. 1st ed. Chichester, England. 2001.

16.

Marler

R.T.

and Arora

J.S.

, Survey of multi-objective optimization methods for engineering, Structural and Multidisciplinary Optimization 26 (2004), 369–395.

17.

Osyczka

, Multicriteria Optimization for Engineering Design, In Design Optimization. Academic Press. 1985, pp. 193–227.

18.

Gierz

Hofmann

K.H.

Keimel

Lawson

J.D.

Mislove

and Scott

D.S.

, A Compendium of Continuous Lattices, Springer Berlin, Heidelberg, 1980.

19.

Balakrishnan

V.K.

, Introductory Discrete Mathematics (Dover Books on Computer Science). Dover Publication, 2010.

20.

Bernábe

, Desarrollo de un modelo para la Zonificación Óptima, Tesis Doctoral, Posgrado de Ingeniería, Investigaciónn de Operaciones, UNAM, 2010, pp. 108–119.

21.

Ríos

, Sobre soluciones optimas en problemas de optimización multiobjetivo, Trabajos de Investigación Operativa 2(1) (2008), 49–67.

22.

INEGI Sistema para la consulta de información censal 2000, XII Censo General de Población y Vivienda del año2000, 2000.

23.

Bernábe

M.B.

Ruiz-Vanoye

J.A.

González

and Estrada

, A bi-objective proposal to group population without tap water or drainage network services, Proc. of The Third Intl. Conf. on Advances in Computing, Electronics and Communication – ACEC 2015 Institute of Research Engineers and Doctors, USA, 2015.

A bi-objective model for territorial design

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1 Related works

3. Compactness

4.1 Population balance

4.3 Homogeneity over agebs for population variables

5.1 Pareto front

5.2 Order relations

5.3 Maximal and minimal elements in a Hasse diagram

6.1 Solution strategy

7. Application

7.1 Application description

7.2 Result of a bi-objective partition with two groups

Table 1 Maximum solutions that form the pareto front

References

Table 1
Maximum solutions that form the pareto front