Step 1. Define the demand population and the educational profile of each census unit

For each of the J census units, it is specified:

• Demand population: the resident population aged between 12 and 17 years. We use this information to build the demand vector, where each element of the vector represents the amount of the ‘demand population’ in the census unit j.
• Educational profile: the percentage of the population for each of the educational groups (primary, secondary, and higher education). We consider the educational level of the primary provider in each household to create a matrix of size J x 3 (number of education categories), where each row sums to 1.

This information is assigned to the centroid of each census unit, as it is considered to represent the average distance travelled by each potential student.

Step 2. Define the educational capacity of each school

We identify the number of available places for each school using the number of students enrolled in the previous year as a proxy. The supply vector is created, where each element represents the maximum number of students that each school k can accommodate.

Step 3. Define the distance matrix between census units and schools

A cost matrix C is generated using distance of the street network between the centroid of each census unit and each school. For each school/census unit, the straight-line distance to the nearest street is calculated, and a new node is created in the network (if necessary). Then, we compute the street network distance between these two points of the network. We add (a) the two straight-line distances and (b) the in-network distances; to get the total distance between the census unit and the school. The resulting matrix C has a dimension of J x K, where each row represents one of the J census units and each column represents one of the K schools. The element \(c_{jk}\), belonging to matrix C, indicates the distance between the centroid of census unit j and school k.

Step 4. Constructing the Allocation Matrix (linear programming)

This is the central step of the proposed method. Our goal is to find the allocation matrix A (with dimension J x K), where each element \(a_{jk}\) represents the number of students from census unit j that should attend school k in order to minimise the total distance travelled. To solve this optimization problem, we use an integer linear programming method known as transportation problems, which allows us to minimize an ‘objective function’ subject to certain ‘constraints’.

A. Define Objective Function

We define the objective function as Equation (1). Since matrix C represents the distance between census units and schools, Equation (1) minimizes the total distance travelled by all students, assuming that they are assigned according to matrix A.

\[ \min_{a \in \mathbb Z_{\geq 0}}( \sum_j^J \sum_k^K a_{jk}.c{jk} ) \quad \quad \textrm{(1)} \]

B. Define Constraints

We establish three constraints:

1. The elements of matrix A must be non-negative integers (\(a_{jk} \in \mathbb Z_{\geq 0}\)). This constraint ensures that the number of students assigned by matrix A is always an integer.
2. All school-age individuals in each census unit must be assigned to a school. The sum of each row in matrix A must be equal to the population demand of each census unit (\(\sum_k^K a_{jk} =demand_{jk}\); for each of the J census units).
3. Each school k must not exceed its maximum student capacity. In other words, the sum of each column in matrix A must be less than or equal to capacity of school k (\(\sum_j^J a_{jk} \leq supply_{jk}\); for each of the K schools).

C. Optimisation

To solve the optimisation problem of the objective function (1), we use the R package ‘lpSolve’ (Berkelaar, 2019). This package provides an interface between R and ‘lp_solve’ (Berkelaar et al., 2004), a Mixed Integer Linear Programming solver written in ANSI C. The result is the allocation matrix A that minimises the objective function while adhering to the constraints mentioned above.