Alocação de muitos alunos para muitas escolas com base na capacidade

Question

Digamos que eu tenha um conjunto de coordenadas de escolas (S).Eu também tenho um conjunto de coordenadas centróides de bairros (N).

Eu sei quantas crianças existem em cada bairro e elas são categorizadas como ensino fundamental, médio ou médio.Então, em outras palavras,

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

Sei quantas vagas estão disponíveis em cada escola, sendo o formato:

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

Meu objetivo é combinar o maior número possível de alunos com uma escola dentro de um determinado raio.É possível (extremamente provável) que, nos meus cálculos, alguns alunos não tenham escola.

O que eu quero:identificar quais bairros têm crianças sem escola e quantas.

Meu plano atual:

• Liste todos os pareamentos e distâncias correspondentes entre escolas e bairro, dentro de um determinado raio
• Ordene por distância do mais baixo para o mais alto
• Dê prioridade com base na distância
• Percorra o bairro em ordem de aparecimento (cada bairro pode aparecer várias vezes vinculado a uma determinada escola dentro de um raio definido)
• Preencher a escola correspondente com crianças do bairro
• Remover vagas ocupadas da capacidade escolar
• Passe para o próximo par bairro-escola, ...

Como um exemplo:

• Digamos que você obtenha a seguinte ordem:

  Ordem = [(bairro_2, escola_7, distância1), (bairro_5, escola_2, distância2), (bairro_2, escola_2, distância3), (bairro_2, escola_3, distância4) ...]

Em seguida, a escola_7 recebe crianças do bairro_2.Nem todas as crianças do bairro_2 podem ser acolhidas na escola_7.

Em seguida, a escola_2 recebe os alunos do bairro_5.Agora, suponha que a escola_2 esteja lotada para o ensino médio.

Então, bairro_2 ainda tem alunos para enviar e tenta mandá-los para a escola_2.Ensino fundamental e médio, sem problemas, agora estão todos despachados.Mas o ensino médio está lotado.

Em seguida, passamos para o próximo par, e a escola_3 recebe os alunos restantes do ensino médio do bairro_2.Note-se que se a distância4 tivesse sido superior ao raio limite, estes alunos do ensino secundário teriam sido classificados como sem escola, uma vez que não existem outros pares disponíveis.

Além disso, se bairro_4 estiver fora do raio limite de qualquer escola, todas as suas crianças serão consideradas sem escola.

1) Meu algoritmo está correto?

2) Qual é o nome desse problema exato?Eu me deparei com muitos e muitos problemas de correspondência de pontos, alocação de capacidade ou a parte de "validação" do problema de localização de instalações, mas não esta variante específica por algum motivo (provavelmente habilidades de pesquisa ruins)

3) Como posso tornar isso eficiente ou é bastante razoável dessa forma?(eficiência não é minha principal preocupação, mas soluções fáceis são bem-vindas)

4) Tenho outras opções além da classificação por distância?Tecnicamente, no meu caso, a distância não importa muito para dar prioridade, é mais uma alocação aleatória (ou devo dizer justa) baseada, por exemplo, na hora do pedido recebido (dados desconhecidos).Portanto, meu método mostrará uma alocação provável de 100% para um bairro muito próximo de uma escola e um grupo de crianças sem escola em bairros mais distantes, mas isso pode não ser (não é) verdade na vida real.

Answer 1

Isto pode ser expresso como o problema de encontrar um correspondência máxima em um gráfico bipartido:cada criança é um vértice esquerdo, cada vaga em uma escola é um vértice direito e há uma aresta entre dois vértices se eles puderem ser combinados.

No seu caso, você pode resolvê-lo de forma mais eficiente usando fluxo máximo.Vou deixar resolver os detalhes.