O problema do transporte escolar rural: uma abordagem Column-and-cut para o problema de roteamento de veículos capacitado

Existe uma situacao de afastamento e dificuldade ao acesso a servicos publicos em geral, na qual a populacao rural esta sujeita. Um dos principais, o acesso a educacao, encontra-se a caminhar para um horizonte melhor atraves da disponibilizacao de transporte adequado aos alunos. Assim, este trabalho vem ao encontro do interesse do governo local, no sentido de auxilialo na melhoria da disponibilizacao de um servico de transporte escolar de melhor qualidade a um custo mais baixo. O trabalho aborda o assunto do transporte escolar rural, classificado como Problema de Roteamento de Veiculos Capacitado, propondo algoritmos do tipo Column-and-cut para sua resolucao de forma mais rapida e com limites aceitaveis. O problema mestre deriva da ideia de particionamento de conjunto de Balinski e Quandt (1964) que e combinado com tres subproblemas. Estes subproblemas sao os responsaveis por gerar as colunas, o metodo das qroutesproposto por Christofides, Mingozzi e Toth (1981a) e o Problema do Caminho Minimo com Restricao de Recursos, nao-elementar de Desrochers (1986) e elementar de Feillet et al. (2004). Uma vez que a formulacao esta relaxada, utilizou-se duas familias de cortes para melhorar os limites obtidos, a primeira, proposta por Jepsen et al. (2008), que sao as Desigualdades sobre Subconjunto de Linhas e a segunda, proposta por Contardo, Desaulniers e Lessard (2015) que sao as Restricoes Fortes de Conexao. Os modelos sao avaliados atraves da aplicacao em instâncias da literatura.