Otimização da distribuição de alunos em São Tomé

Abstract

Nesta dissertação propomos a resolução do problema de otimização da distribuição de alunos por escola e por classes. Consideramos o caso particular da distribuição dos alunos do 2º ciclo do ensino secundário por 12 escolas secundárias da ilha de São Tomé, República Democrática de São Tomé e Príncipe. O problema enquadra-se num problema de transportes que é um problema de otimização na área da Investigação Operacional. O objetivo é minimizar a distância total percorrida pelos alunos das suas residências às escolas onde são colocados. A capacidade das escolas para a população escolar é limitada, e deve ser obedecida. Além disso, determina-se também o número de turmas que deve ser formada para cada classe em cada escola. Nesta dissertação são descritos matematicamente vários modelos de programação linear inteira para o problema. Começamos por apresentar, um modelo de atribuição visando apenas atribuir cada aluno à escola mais próxima da sua residência. Segue-se um modelo de programação linear inteira que distribui os alunos pelas escolas tendo em conta apenas a capacidade das escolas em termos do número de alunos. Depois apresentamos três modelos de distribuição de alunos pelas escolas e por classes, onde é considerada a capacidade das escolas em termos de turmas. Estes modelos propõem formas alternativas de determinar o número de turmas adequadas a cada classe em cada escola. Além disso, têm também a particularidade de dar preferência à distribuição dos alunos das classes menores respeitando um limite mínimo e máximo de alunos por turma. Por fim, apresentamos um algoritmo que faz a distribuição de alunos pelas escolas e por classes em várias fases. Na primeira fase, apenas são distribuídos os alunos cuja residência está a uma distância máxima pré-estabelecida. Na segunda fase, os restantes alunos são distribuídos pelas vagas sobrantes. Usamos vários valores para a capacidade das escolas para realizar diversas experiências computacionais através das quais foi possível encontrar a melhor solução para a distribuição de alunos pelas escolas e por classes para a capacidade atual das escolas existentes na ilha de São Tomé. Os valores da distância total percorrida variam entre 43959.99 e 48695.8 dependendo do modelo usado. Notamos que, em comparação com o valor da distância total percorrida atualmente que é de 66554.29 os valores obtidos nesta dissertação são muito melhores. Adicionalmente, foi também possível identificar regiões ou distritos da ilha com escassez de vagas para a população atual, e consequentemente para uma procura futura.

In this dissertation we propose to solve the problem of optimizing the distribution of students by school and by classes. We consider the particular case of the distribution of secondary school students by 12 secondary schools in the island of São Tomé, Democratic Republic of São Tomé and Príncipe. The problem falls under a transportation problem which is an optimization problem in the field of Operational Research. The objective is to minimize the total distance travelled by students from their homes to the schools where they are placed. The capacity of the schools for the school population is limited, and must be obeyed. In addition, the number of classes that should be formed for each class in each school is also determined. In this dissertation several integer linear programming models for the problem are described mathematically. We begin by presenting an assignment model that aims to assign each student to the school closest to his/her residence. This is followed by an integer linear programming model that distributes students among schools taking into account the capacity of schools in terms of the number of students. Then we present three models for distributing students across schools and classes, where the capacity of schools in terms of classes is considered. These models propose alternative ways of determining the number of classes suitable for each class in each school. Moreover, they also have the particularity of giving preference to the distribution of students in from lower grade classes respecting a minimum and maximum limit of students per class. Finally, we present an algorithm that performs the distribution of students by schools and by classes in several phases. In the first phase, only students whose residence is within a preestablished maximum distance are distributed. In the second phase, the remaining students are distributed by the remaining vacancies. We used several values for the capacity of the schools to perform several computational experiments through which it was possible to find the best solution for the distribution of students by schools and by classes for the current capacity of the existing schools on the island of São Tomé. The values of the total distance travelled vary between 43959.99 and 48695.8 depending on the model used. We note that compared to the current total distance travelled value which is 66554.29 the values obtained in this dissertation are much better. Additionally, it was also possible to identify regions or districts of the island with a shortage of places for the current population, and consequently for a future demand.