Defesa de ALLEXANDRE FORTES DA SILVA REIS

O Problema do Transporte Escolar Rural: Uma abordagem Column-and-cut para o Problema de Roteamento de Veículos Capacitado

 

Existe uma situação de afastamento e dificuldade ao acesso a serviços públicos em geral, na qual a população rural está sujeita. Um dos principais, o acesso à educação, encontra-se a caminhar para um horizonte melhor através da disponibilização de transporte adequado aos alunos. Assim, este trabalho vem ao encontro do interesse do governo local, no sentido de auxiliá-lo na melhoria da disponibilização de um serviço 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 Veículos Capacitado, propondo algoritmos do tipo Column-and-cut para sua resolução de forma mais rápida e com limites aceitáveis. O problema mestre deriva da ideia de particionamento de conjunto de Balinski e Quandt (1964) que é combinado com três
subproblemas. Estes subproblemas são os responsáveis por gerar as colunas, o método das q-routes proposto por Christofides, Mingozzi e Toth (1981a) e o Problema do Caminho Mínimo com Restrição de Recursos, não-elementar de Desrochers (1986) e elementar de Feillet et al. (2004). Uma vez que a formulação está relaxada, utilizou-se duas famílias de cortes para melhorar os limites obtidos, a primeira, proposta por Jepsen et al. (2008), que são as Desigualdades sobre Subconjunto de Linhas e a segunda, proposta por Contardo, Desaulniers e Lessard (2015) que são as Restrições Fortes de Conexão. Os modelos são avaliados através da aplicação em instâncias da literatura.

 

07/07/2015

14:00

sala 1012, Escola de Engenharia