Voronoi Method: Zoning School System Proposal

Alamsyah Hanza

source: beritasatu.com

Maybe it is kinda too late for me to discuss this matter now. Because of the Zoning School System is not a thing right now, but it is a big deal in Indonesia around May and June 2019.

Indonesia has this a new rule (followed by another rule) to create some kind like “Zoning System” where a future student can’t choose the next level school outside their Zone. However, to be honest, I do not really understand the rule pretty much. So, here is an article in Bahasa about the rule and the reason why the government issuing the regulations.

Memahami Sistem Zonasi Sekolah di PPDB 2019 – Tirto.ID

tirto.id – Penerimaan Peserta Didik Baru (PPDB) 2019 masih menggunakan jalur zonasi, sebagaimana yang termaktub dalam…

9 Poin Buka-bukaan Mendikbud Soal Sistem Zonasi dan PPDB 2019

KOMPAS.com- Menteri Pendidikan dan Kebudayaan ( Mendikbud) Muhadjir Effendy menyampaikan beberapa poin penting terkait…

edukasi.kompas.com

All the rules there creates many viral negative feedbacks from the public as follows,

Click here for some details about the problem.

I won’t talk about the rules and how that rule makes a big impact on future students in Indonesia. Also, I won’t blame the rule itself, because I’m not sure how Indonesia’s Government comes up with the rule. However, in this blog, I want to propose some kind of method to do this “Zoning Problem” that probably can minimize the negative impact. I will show how I do the analysis and end up with the methods.

Every analysis must start with the problem definition which has the Northstar as the real goal. In this blog, I have a goal to do make a zoning school system with a minimum of the first negative impact above. I limit the problem to just minimize the first problem because I have limited data to work on. The second problem probably can be solved with density population data, meanwhile, the third problem should use the standardized quality of all schools.

So, based on my goal there, my problem statement is

“How to create the Zoning School system, so that the future students have at least 3 schools to choose?”

After we have the problem statement, the next to do is to get the data that is suitable for the problem. I need the location of all the schools in Indonesia in terms of longitude and latitude so I can define the zone. I get the data from this source which I think is open for anyone (at least in Indonesia). So, I crawl all the possible school that is listed there with its information.

Get the Longitude and Latitude

It takes me about 2 days to get the right data and I get around 200.000 schools in Indonesia from all levels: elementary schools (SD), Junior High School (SMP) and Senior High School (SMA/SMK). I am not sure about the quality of the data, but when I try to plot all the Longitude and Latitude from the website here is the result.

Probably All School Location in Indonesia

It shows the map of Indonesia, so the plot can confirm the data’s quality is good enough. To compare with the real map, I use python to read the shapefile of Indonesia’s map on the city level from this source.

Indonesia’s Map

Even with almost the same shape, after checking the data, there almost 2% of points are not exactly within the city polygon. The points outside polygon will be removed from the methods analysis. Here is an example from `Surabaya` which has points outside the polygon (red dots).

Surabaya All School Location’s

For a simple exploration, this is the heatmap of a total number of schools that are officially registered on the website in every city in Indonesia. The red area is a missing value because of the different name conventions of shapefile and scrapped data. The map shows there is more school is developed on Java island (the big island with yellow color in the south) than another island. Also, other than Java island, the number of schools is not spatially correlated. Sumatera for example (the big island on West), it has a yellow area which surrounded by green area.

Total School in Every City of Indonesia

Before proposing the method, let’s take a look at Zoning System using Radius Principal. The method is not that complex, Future Student School Zone is within radius X kilometers from the house.

Radius Principal

So, the student can’t choose a school that really far from their house (red area). This principal probably will work if it is guaranteed there will be schools within the zone. Let’s simulate this approach using Indonesia school location data.

The simulation is easy, just pick many random points on the polygon of a particular city and do iteration for different radius from schools (it easier to change radius from school point than random points, the result will the same). The random points are assumed to be the student house, this assumption can be fulfilled if the city is dense enough. Because we don’t want the random points to end up in the middle of the forest or abandoned lake. Thus, based on certain references, the simulation is done on DKI Jakarta, Kota Surabaya, Kota Medan, Kota Bandung, Kota Makassar, and Kota Palembang. As a note, the simulation using Senior High School (SMA) data location only.

This is the simulation example on Surabaya where the color shows the number of school choices that every random point will get for a particular radius. The red dot is the SMA location in Surabaya.

The simulation overall dense cities show that, for a different area, the probability of all students to get a minimum of 3 schools to choose is different. The graph below tells the probability — in percentage — of students to get a minimum of 3 school options (y-axis) with a certain radius from their house (x-axis) for many different cities (distinct by colors). So, it is expected that the higher of the x-axis, the closest of the line to 100.

The graph describes that even with radius X=4 km, there is a certain area like Palembang which still has probability under 80%. Even a city called Bandung Barat can’t reach 60% with a radius X=5 km.

The probability that means students need to travel with a minimum of 5 km to get at least 3 school choices with probability 60% to get all the schools in Bandung Barat. Moreover, the radius here using Euclidian distance, so the true distance in real life could farther than 5 km.

In summary, the Radius Principle is better to be used for a city with a high population density. However, if the methods must be implemented for all cities with different density, then the radius distance should be different for a different area depends on the population density. Even the city could be divided into certain smaller areas and adopt different radius for those areas. Not only that but, developing new schools is also necessary for certain areas who really have a small number of schools. So, students will have different schools to choose and they should not spend their time on the road.

A zoning system is really challenging, especially the area that is full of small islands like Indonesia. The radius principal above has a lack of variety and it needs more exploration to determine the right radius for the right city. It also has a disadvantage if the student comes from a different island like Makassar. If the island distance to the closest school is more than the radius, the possibility of all students on that island to get to school is almost zero.

Makassar has many smalls island

Therefore the new method called Voronoi is proposed to minimize the time-consuming exploration to determine the radius. Voronoi is a method to make a partition of a plane into regions close to each of a given set of objects. Imagine we have a plane and there are some points on the plane, Voronoi’s objective is to make regions where every region is closer to a particular point than the other points.

Voronoi diagram example (source)

Let say we have a map and all location of schools, the Voronoi will automatically create the region for every school such that every student in that region is closer to that school than the other schools. However, it means every student only has one school option to choose if they must enter the closest school. Thus, the school clustering is proposed to create a larger area where students can have 3 schools minimum options. For now, I proposed KMeans to cluster the schools in every city (its better use the HDBSCAN for future reference), which leads us to another problem to choose the cluster number. For that case, the cluster number can be evaluated using a silhouette score where we will choose the cluster number with the highest score. It must keep in mind that all schools here are assumed has the same quality to prevent the cluster from all bad schools.

In summary, this is the algorithm of the proposed method

Pseudocode of the Algorithm

This is the result of the algorithm for Makassar and Bandung Barat.

Senior High School (SMA) Proposed Zoning System

The Voronoi method will ensure every student in the city will have a minimum of 3 option schools, it solves the “60% problem” on Bandung Barat before. The Voronoi also helps students on the far island to have a chance to get to school.

However, for some zone like the brown area on Bandung Barat (bottom left), the students must travel quite longer in averages because of the zone is quite big with only 3 options of schools. It probably shows that the Voronoi method will not solve the “All School is already full in this region” problem. This problem also shown in Palembang on the green zone (top left) and Surabaya on the violet zone (top left).

Surabaya and Palembang Proposed Zoning School for SMA

The Zoning system is built to equalize the quality of education such that there will be no higher or lower class region in terms of education. Even with the good intention, the poor Zoning system and the not standardized quality of schools will make the education system seems bad and reduce the right many students to get to a school.

The Radius Principle is one example of a deficient method to do Zoning system, especially for huge countries with a different population density all over the city. As the simulation shows, for Indonesia, with the same radius, the probability of students to get a minimum 3 schools option is variant. In Jakarta, the probability could reach almost 100% within a 2 km radius, but with the same radius, the probability is roughly 50% in Palembang. Thus, the radius distance should be different for a different area.

Voronoi with KMeans clustering is another method that quite better than Radius Principle which can cover the Radius Problem. The Voronoi could make an optimal region for every school so that there is no region that will not have a school option more than 3. However, the problems happen if one school is covering a really large area because of the low number of schools in the neighborhood area.

Therefore, to make more optimal solutions here some action that can be done

alamhanz/education_zone

It starts with New Zonasi Rule from Govt Indonesia that seems unfair for certain people (based on viral news). This…

github.com

Voronoi Diagrams Lab

In addition to directly reading in CSV files. Pandas has a built-in function for reading in JSON files. This section…

comet.lehman.cuny.edu

Favorite

Leave a Comment