XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
OTIMIZAÇÃO DA DISTRIBUIÇÃO DE
ESTUDANTES EM ESCOLAS PÚBLICAS
DE UM DISTRITO DO MUNICÍPIO DE
SÃO GONÇALO - RJ
Anderson Velasco de Oliveira (UFF)
[email protected]
Artur Alves Pessoa (UFF)
[email protected]
Marcos Costa Roboredo (UFF/UERJ)
[email protected]
Neste trabalho é proposto um modelo de Programação Linear Inteira
composto de duas fases que visa otimizar a distribuição de estudantes
em escolas públicas estaduais no Município de São Gonçalo - RJ. Na
primeira fase, o modelo visa atribuir estudantes à escolas,
maximizando o número de alunos que possam ir a pé até as suas
escolas. Na segunda fase, o modelo mantém os estudantes que podem
ir a pé nas mesmas escolas e redistribui os demais estudantes
minimizando a distância total percorrida por estes. Resultados
mostram que, para um total de 3888 alunos, a atribuição proposta faz
com que apenas 487 destes alunos não consigam ir a pé até as suas
escolas. Além disso, para os demais estudantes, a segunda fase foi
capaz de reduzir a maior distância percorrida por algum aluno de
10334 m para 5336 m, que podem facilmente ser percorridos via
transporte público.
Palavras-chave: Otimização, Programação Linear Inteira, Problema
da Atribuição
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
1. Introdução
Em maio de 2007 estimou-se que, em termos globais, a população urbana ultrapassou a
população rural. Esses dados divulgados por especialistas não provêm de um censo, mesmo
assim representam uma marca histórica. No Brasil, esta transição teve este mesmo marco no
fim da década de 1960. Com isso, qualquer serviço público deve se adaptar a novas demandas
urbanas, seja quantitativa ou qualitativamente.
Entre os serviços públicos de maior demanda está a educação. Um número crescente de
alunos se matricula todos os anos nas instituições de ensino: nível pré-escolar, fundamental,
médio, técnico, superior e educação de jovens e adultos - EJA. Aqui será focado o ensino
médio regular público no Estado do Rio de Janeiro, que de forma geral, agrega jovens, cuja
grande maioria possui entre 15 e 17 anos de idade (idades consideradas ideais para o 1º ano,
2º ano e 3º ano do ensino médio, respectivamente). Segundo o Censo Escolar de 2010, dos
623549 estudantes matriculados no ensino médio no Estado do Rio de Janeiro, 491549
estavam matriculados na rede estadual de educação, sendo 442046 na zona urbana.
A questão a ser analisada neste trabalho é o tempo gasto pelo estudante entre a sua residência
e a instituição de ensino na qual estuda, que pode resultar em diversos benefícios e malefícios.
Se o tempo for relativamente grande, o aluno deverá dispor de meio de transporte para chegar
à escola e, na volta, chegar a casa. Dentre fatores facilmente observados tem-se o gasto de
recursos com o transporte escolar e, devido ao tráfego em horários de pico, gasto de tempo no
deslocamento do estudante.
No Estado do Rio de Janeiro, por exemplo, o estudante da rede estadual de ensino tem direito
a gratuidade nos transportes públicos através de um cartão dados aos estudantes no início do
ano letivo. Este benefício custa recursos ao governo que subsidia parte desta gratuidade.
Portanto, diminuir a distância residência-escola é diretamente benéfica aos cofres públicos,
pois a demanda pela gratuidade diminuiria e, consequentemente, o subsidio por parte do
governo as empresas de transporte público teria de sofrer um decréscimo benéfico aos cofres
públicos.
Quanto ao tráfego, os horários de entrada e saída de alunos coincidem com os horários de
maior número de veículos nas ruas. Portanto, diminuir a distância residência-escola é benéfica
ao tráfego, e, consequentemente, a qualidade de vida da população local, principalmente dos
estudantes.
2
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Neste contexto, pretende-se neste trabalho apresentar um modelo de Programação Linear
Inteira que visa atribuir estudantes a escolas maximizando o número de estudantes que
consigam ir a pé até sua escola. Como estudo de caso, foi escolhido um determinado público
de alunos da rede estadual de ensino em uma região de São Gonçalo, município do Estado do
Rio de Janeiro. Para a geração dos dados de entrada, utilizou-se os dados do IBGE (CENSO
2010), do INEP (CENSO ESCOLAR 2010) e a localização das escolas da citada região, as
projeções para o ano de 2015, bem como as reais ofertas de vagas para o Ensino Médio
regular.
Conforme já comentado, o modelo proposto incialmente visa atribuir os estudantes as escolas
de modo que o maior número de estudantes possível consiga percorrer o trajeto a pé até suas
escolas. Como isto não é possível para todos os estudantes, é proposto ainda neste trabalho
um pós-processamento que visa realocar os estudantes que não irão a pé até suas escolas,
minimizando a distância média percorrida por estes. Resultados mostram que, para um total
de 3888 alunos da região considerada, a atribuição proposta faz com que apenas 487 destes
alunos não consigam ir a pé até as suas escolas. Além disso, para os demais estudantes, o pósprocessamento foi capaz de reduzir a maior distância percorrida por algum aluno de 10334 m
para 5336 m, que podem facilmente ser percorridos via transporte público.
Este artigo está dividido da seguinte maneira. Seção 2 descreve os trabalhos relacionados ao
tema. Seção 3 apresentada como foram obtidos os dados de entrada do estudo de caso, bem
como o modelo utilizado. Seção 4 apresenta e discute os resultados obtidos. Seção 5 sumariza
as conclusões.
2. Revisão de literatura
Existem diversas publicações relacionadas à alocação de recursos que envolvem o setor
educacional e programação matemática. A maioria destes trabalhos visa analisar a localização
das escolas ou estudar como é feito o transporte escolar.
Com relação a localização, as pesquisas visam propor novas sedes escolares de modo a
minimizar a soma percorrida pelos estudantes. Neste contexto, Pizzolato e Da Silva (1997)
fazem um relato de experiências envolvendo modelos de programação matemática e
localização de escolas em diversos municípios do Brasil. De maneira similar, Barcelos et al.
(2004) aplica o modelo das p-medianas para a localização de novas instalações de ensino
público na cidade de Vitória – ES. Pizzolato et al. (2004) fazem uma sistematização da
3
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
metodologia utilizada nos trabalhos prévios. Mais recentemente, Menezes e Pizzolato (2014)
abordam o grande crescimento populacional de Guaratiba, região da cidade do Rio de Janeiro
e propõe soluções quanto à localização de novas sedes escolares da rede municipal de ensino
para suprir tal demanda.
A respeito do roteamento do transporte escolar de estudantes, as pesquisas visam, em escolas
onde parte dos estudantes utiliza o transporte disponibilizado pela própria escola, definir
quantos veículos a escola necessita, qual atribuição de alunos para estes veículos e qual a rota
que será seguida por cada veículo. Devido a complexidade deste problema, existem pesquisas
tanto práticas quanto teóricas. Park e Kim (2010) fazem uma revisão detalhada do problema e
das principais referências até o ano de 2010. Mais recentemente, Campbell et al. (2015) faz
um estudo sobre este problema em um distrito do Canadá, considerando as especificidades do
estudo de caso.
O presente estudo se torna particular pelo fato de não estar interessado na localização de uma
nova escola e nem no roteamento do transporte escolar. O propósito é determinar através da
Programação Linear Inteira uma melhor distribuição dos estudantes nas escolas da rede
estadual na região já citada.
3. Metodologia
Esta seção apresenta como foram obtidos os dados de entrada necessários e o modelo
proposto.
3.1. Dados de entrada
Os estudantes envolvidos na análise de dados são os estudantes, moradores do distrito de
Neves, em São Gonçalo, município do Rio de Janeiro, que, em 2010, estavam matriculados no
ensino médio regular da rede estadual de ensino. Estão excluídos dessa análise os estudantes
do EJA – ensino de jovens e adultos, os do ensino profissionalizante e do ensino
Normal/Magistério.
Para a obtenção de uma atribuição de estudantes a escolas que maximize o maior número de
estudantes que possam ir a pé, são necessários a obtenção dos seguintes dados da região
citada: número de estudantes em cada uma das três séries do ensino médio, o endereço de
cada um destes estudantes, endereço de cada escola da região, capacidade máxima de
estudantes de cada escola em cada uma das três séries e distância a pé entre cada estudante e
cada escola.
4
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Primeiramente determinou-se o modo como seria analisado a quantidade de estudantes a
serem alocados nas instituições de ensino distribuídas pela região do município onde seria
aplicado o estudo. Para fazer uma análise por território escolheu-se usar os setores censitários
discriminados no Censo Demográfico de 2010 – IBGE. O setor censitário é a menor unidade
territorial, formada por área contínua, integralmente contida em área urbana ou rural, com
dimensão adequada à realização da coleta de dados por um pesquisador que vai a campo por
ocasião do censo. O setor constitui um conjunto de quadras, no caso de área urbana, ou uma
área do município, no caso de uma área não urbanizada. São Gonçalo possui 1932 setores
censitários e, portanto, devido a esse grande número de unidades de setores, escolheu-se o
distrito de Neves, que possui 377 dos setores censitários e abrange 20 bairros, como mostrado
na Figura 1.
Figura 1 - Mapa de São Gonçalo (RJ), com seus setores censitários e o Distrito de Neves destacados
Foram considerados os centroides de todos os setores censitários usados no estudo, como
mostra a Figura 2, pontos que representam o centro geográfico do setor. Como não é possível
encontrar a localização exata de cada estudante entre 15 e 17 anos de idade (considerada idade
ideal para o ensino médio, segundo a legislação brasileira), assumimos que toda a população
do setor se encontra localizada no centroide. Para estabelecer tal ponto utilizou-se o software
5
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Quantum Gis – QGIS, um Sistema de informação Geográfica (SIG), software livre licenciado
sob a GNU – General Public License.
Figura 2 - Distrito de Neves, seus setores censitários e os centroides associados
Em 2010, segundo o Censo Escolar, em São Gonçalo, dos 46 892 estudantes matriculados no
ensino médio, 35135 estavam matriculados na rede estadual de educação. Portanto, 74,9% dos
estudantes do ensino médio em São Gonçalo, que estão na série correta para sua idade. Neste
mesmo ano, nas escolas públicas estaduais de ensino médio em 2010, estavam matriculados
na rede estadual de educação. Usou-se tal percentual em cada setor censitário: dos residentes
na faixa etária de 15 a 17 anos de idade, considerou-se que 74,9% deles estavam em uma
escola estadual. Existe outro dado presente no Censo Escolar de 2010 que é a taxa de
distorção idade-série, que nos informa o percentual de alunos na zona urbana de São Gonçalo,
apenas 51% dos jovens de 15 anos estava no 1º ano do ensino médio. Dos que tinham 16
anos, apenas 55% estavam no 2º ano do ensino médio. Dos que tinham 17 anos, 56% estavam
no 3º ano do ensino médio.
A região estudada possui dez escolas, onde o endereço de cada uma destas é de fácil
obtenção. De posse desses endereços e dos centroides, através do Google Maps, é possível
encontrar a menor distância a pé de cada centroide a cada escola.
6
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
A capacidade máxima de estudantes do ensino médio em cada escola varia de ano para ano
uma vez que estas escolas não possuem somente ensino médio. Para se estimar esta
capacidade, foi considerado o maior número de matrículas no ensino médio, em cada escola,
considerando os anos de 2010, 2011, 2012 e 2013. Como a alocação nas escolas em relação as
séries depende da demanda, é proposto aqui uma a adequação variável, de acordo com tal
demanda. Porém, cada escola deve ter ao menos uma turma de cada série, obedecendo um
número mínimo pré-estipulado de alunos para se formar uma turma. A soma de alunos
alocados obedecerá a capacidade máxima de cada escola.
3.2. Modelo proposto e módulo de pós-processamento
Nesta seção, é descrito o modelo proposto que visa atribuir os estudantes (representados pelos
centroide) as escolas, maximizando o número de estudantes que consigam ir a pé.
Dados de entrada
→
conjunto de centroides
→
conjunto das escolas
→
conjunto das turmas
→
número de estudantes do centroide da turma
→
número mínimo de estudantes para se abrir uma turma.
→
capacidade de alunos da escola .
→
distância a pé entre o centroide e a escola .
→
distância máxima que um estudante pode percorrer a pé.
Variáveis inteiras
→
número de alunos da turma k transportados da região i para a escola j
→
número de alunos da turma k atribuídos para a escola j
Modelo
7
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
max
(1)
s.a.
(2)
(3)
(4)
(5)
(6)
(7)
A função objetivo (1) visa maximizar o número de alunos que vão a pé até a escola
atribuída. As restrições (2) garantem a consistência entre as variáveis
e . As restrições (3)
garantem que todos os alunos serão atribuídos a alguma escola. As restrições (4) garantem
que a capacidade de cada escola deve ser respeitada. As restrições (5) garantem que no
mínimo uma turma de cada tipo seja aberta em cada escola. As restrições (6) e (7) mostram
que as variáveis do problema devem ser inteiras não negativas.
Após a execução do modelo prévio, a tendência é que os alunos que não ficaram alocados em
uma escola que possam ir a pé sejam alocados em escolas muito longe uma vez que esta
distância não influencia na função objetivo (1). Assim, um módulo de pós-processamento é
acionado, onde todos os estudantes alocados pelo modelo em escolas onde é possível se ir a
pé são mantidos nas mesmas escolas. Já os demais estudantes, são realocados de modo que a
distância total percorrida seja a menor possível. Assim, o módulo de pós-processamento
consiste da execução de um novo modelo com as mesmas variáveis e restrições do modelo (1)
– (7), onde as variáveis
com
são fixadas com os valores gerados. A função
objetivo passa a ser a seguinte, que visa minimizar a soma das distâncias percorridas pelos
alunos que não vão a pé:
(8)
4. Resultados
8
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
O estudo de caso é composto de 369 centroides, 3888 alunos, 10 escolas, 3 tipos de turma (1º,
2º e 3º anos do ensino médio). Foi estipulado que cada aluno pode andar no máximo 1500 m a
pé. A Tabela 1 compara os resultados obtidos antes e após uso do módulo de pósprocessamento:
Tabela 1- Estatísticas comparativas antes e após o módulo de pós-processamento
Estatística
Número de alunos total
Número de alunos não a pé
Número de alunos a pé
Distancia media total (m)
Distancia media não a pé (m)
Distancia media a pé (m)
Maior distancia (m)
Antes do pósprocessamento
3888
487
3401
1458,31
4513,55
1020,82
10334,00
Após o pósprocessamento
3888
487
3401
1180,07
2292,20
1020,82
5336,00
Pela Tabela 1, conclui-se que dos 3888 alunos, apenas 487 não foram alocados em escolas a
uma distância menor ou igual a 1.500 m. Outro ponto importante é que antes do pósprocessamento, alguns alunos foram alocados em escolas a uma distância superior a 10.000
m. Já com a utilização do pós-processamento este número se reduziu para menos de 6.000 m.
Outro ponto importante a ser analisado é a porcentagem de uso das capacidades das escolas.
A Tabela 2 fornece tal porcentagem após a alocação final de estudantes.
Tabela 2 - Percentual da capacidade utilizado de cada escola
Escola
1
2
3
4
5
6
7
8
9
10
Percentual da
capacidade
utilizado (%)
100,00
100,00
100,00
100,00
68,48
12,14
100,00
62,88
100,00
49,35
9
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
Pela Tabela 2, observa-se que, para a maioria das escolas, o percentual de utilização da
capacidade foi de 100%. Observa-se que a escola 5 foi pouco utilizada por ser distante da
maioria dos alunos. Uma importante conclusão da Tabela 2 é que, uma das maneiras de fazer
com que todos os estudantes possam ir a pé até as suas escolas, é aumentando a capacidade de
algumas das escolas com 100% de uso.
5. Conclusões
Este trabalho apresentou um modelo de Programação Linear Inteira que decide a atribuição de
alunos a escolas públicas visando maximizar o número de alunos que possam ir a pé até as
suas escolas. A solução gerada tende a agradar tanto os governantes, que economizam
recursos financeiros quanto aos alunos, que não precisam se preocupar com eventuais
engarrafamentos. Foi proposto ainda um módulo de pós-processamento que visa realocar da
melhor maneira possível os estudantes que não poderão ir a pé até as suas escolas.
Como estudo de caso, foram utilizados dados reais de um distrito do Município de São
Gonçalo – RJ, onde foi possível constatar que, dos 3888 alunos considerados, apenas 487
alunos não vão a pé para suas escolas. Destes 487 alunos, a maior distância percorrida 5336
m, que facilmente pode ser percorrida via transporte público. O estudo apontou ainda que
grande parte das escolas tiveram sua capacidade 100% utilizada. Isto mostrou que caso
algumas destas escolas tenha sua capacidade aumentada, então todos os alunos poderiam ir a
pé até suas escolas.
Como trabalhos futuros, pretende-se criar modelos que indiquem maneiras de fazer com que
todos os alunos possam ir a pé até suas escolas. Uma possível maneira para isso é a criação de
um modelo que decida quais escolas devem ter sua capacidade aumentada. Um outro possível
modelo visa a decisão de onde se localizar novas escolas.
REFERÊNCIAS
BARCELOS, Fabrício Broseghini; PIZZOLATO, Nélio Domingues; LORENA, Luiz Antonio
Nogueira. Localização de escolas do ensino fundamental com modelos capacitado e nãocapacitado: caso de Vitória/ES. Pesquisa Operacional, v. 24, n. 1, p. 133-149, 2004.
CAMPBELL, James F.; NORTH, Jeremy W.; ELLEGOOD, William A. Modeling Mixed
Load School Bus Routing. Quantitative Approaches in Logistics and Supply Chain
Management. Springer International Publishing, 2015. p. 3-30.
MENEZES, Rafael Cezar; PIZZOLATO, Nélio Domingues. Locating public schools in fast
expanding areas: application of the capacitated p-median and maximal covering location
models. Pesquisa Operacional, v. 34, n. 2, p. 301-317, 2014.
10
XXXV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Perspectivas Globais para a Engenharia de Produção
Fortaleza, CE, Brasil, 13 a 16 de outubro de 2015.
PARK, Junhyuk; KIM, Byung-In. The school bus routing problem: A review. European
Journal of operational research, v. 202, n. 2, p. 311-319, 2010.
PIZZOLATO, Nelio Domingues; DA SILVA, Hamilton B. Fraga. The location of public
schools: evaluation of practical experiences. International Transactions in Operational
Research, v. 4, n. 1, p. 13-22, 1997.
PIZZOLATO, Nelio Domingues; BARCELOS, Fabrício Broseghini; LORENA, Luiz Antonio
Nogueira. School location methodology in urban areas of developing countries. International
Transactions in Operational Research, v. 11, n. 6, p. 667-681, 2004.
11