2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ The problem statement isn't clear to me. You say you want to match kids to schools, but you don't define what matches are legal and what are illegal. Can you give a more careful statement of the task you're trying to solve? $\endgroup$ – D.W. Mar 28 '20 at 8:24
  • $\begingroup$ The goal is to match students to schools by category (primary school age students to primary school slot, middle school age students to middle school slot). A school is defined by X primary slots, Y middle slots, Z high school slot. A neighborhood is defined by X' primary students, Y' middle students, Z' high school students. Anything where the distance between neighborhood where students are and school is greater than a given limit, say 100km, is not allowed. A primary student cannot be matched to a non primary slot, etc. These are the only constraints. $\endgroup$ – William Abma Mar 28 '20 at 14:50
  • $\begingroup$ OK. What's the context where you encountered this task? Can you credit the original source? $\endgroup$ – D.W. Mar 28 '20 at 17:28
  • $\begingroup$ What do you mean original source? Original source is me wanting to solve that particular problem. $\endgroup$ – William Abma Mar 29 '20 at 18:45
  • $\begingroup$ For instance, if you encountered it in a textbook or a website, crediting the source may help us understand what material you were studying then and what they may have been trying to teach you, and give an answer that is well-suited to the level of background you have. If it is a practical problem (e.g., you are a school administrator or developing IT tech for a school district), you can tell us that and give an idea about the size problem you have (e.g., number of students, number of schools), which may help identify which algorithms are going to be fast enough in practice. $\endgroup$ – D.W. Mar 29 '20 at 18:51
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, maximum flow algorithm is what I was looking for, thank you. $\endgroup$ – William Abma Mar 29 '20 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.