Allocation of many students to many schools based on capacity

Question

Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N).

I know how many kids are in each neighborhood, and they are categorized as either primary, middle or high school. So, in other words,

N = [(locationN1, primary:3, middle:10, high:4), (locationN2, primary:10, middle:17, high:7), ...]

I know how many spots are available in each school, the format being:

S = [(locationS1, primary:20, middle:5, high:2), (locationS2, primary:12, middle:7, high:8), ...]

My goal is to match as many students as possible to a school within a certain radius. It is possible (extremely likely) that in my calculations, some students will be school-less.

What I want: identify which neighborhood have school-less children and how many.

My current plan:

• List all the pairings and corresponding distances between schools and neighborhood, within a given radius
• Order by distance from lowest to highest
• Give priority based on distance
• Loop over the neighborhood in order of appearance (each neighborhood can appear several times linked to a given school within defined radius)
• Fill corresponding school with children from neighborhood
• Remove taken spots from the school capacity
• Move to the next neighborhood-school pairing, ...

As an example:

• Say you obtain the following ordering:

  Order = [(neighborhood_2, school_7, distance1), (neighborhood_5, school_2, distance2), (neighborhood_2, school_2, distance3), (neighborhood_2, school_3, distance4) ...]

Then, school_7 receives children from neighborhood_2. Not all children from neighborhood_2 can be taken in at school_7.

Then, school_2 receives students from neighborhood_5. Now, assume that school_2 is full for middle school capacity.

Then, neighborhood_2 still has students to dispatch, and so tries to send them to school_2. Primary and high school, no problem, they are now all dispatched. But middle school is full.

Then we move on to the next pairing, and school_3 gets the remaining middle school students from neighborhood_2. Note that if distance4 had been higher than the limit radius, these middle school students would have been classified as school-less since no other pairings are available.

Additionally, if neighborhood_4 is oit of the limit radius for any school, all its children are considered school-less.

1) Is my algorithm correct?

2) What is the name of this exact problem? I've come across many to many point matching, capacitated allocation problems, or the "validation" part of facility location problem, but not this particular variant for some reason (likely poor searching skills)

3) How can I make this efficient, or is it pretty reasonable this way? (efficiency is not my primary concern, but easy fixes are welcome)

4) Do I have other options besides distance sorting? Technically, in my case, distance doesn't matter much to give priority, it's more of a random (or should I say fair) allocation based on for example time of received application (unknown data). So my method will show likely 100% allocation for a neighborhood very close to a school amd a bunch of school-less kids in farrher neighborhoods, yet that may not be (is not) true in real life.

Answer 1

This can be expressed as the problem of finding a maximum matching in a bipartite graph: each kid is one left-vertex, each slot in a school is a right-vertex, and there is an edge between two vertices if they can be matched.

In your case, you can solve it more efficiently using max flow. I'll let work out the details.