O problema do transporte escolar rural: uma abordagem Column-and-cut para o problema de roteamento de veículos capacitado
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Resumo
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 qroutesproposto 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.
Abstract
There is a situation of remoteness and difficulty of access to public services in general, in which the Brazilian rural population is submitted. One of the main, the access to education, is moving towards a horizon better by providing adequate transportation to students. This work isin line with the local governments interest in order to assist in improving the provision of a school transport service better quality at a lower cost. This paper addresses the issue of rural school transportation, classified as Capacitated Vehicle Routing Problem, proposing some Column-andcut algorithms to its resolution faster and with acceptable limits. The chosen master problem is derived from the set partitioning proposed by Balinski e Quandt (1964) which is combined withthree different subproblems. These ones are responsible for generate the columns, they are the qroutes method from Christofides, Mingozzi e Toth (1981a) and the Shortest Path Problem with Resources Constraints, non-elementar from Desrochers (1986) and the elementar from Feilletet al. (2004). Once the formulation is relaxed, two families of cuts were used to improve the obtained bounds, the first one is the Subset-row Inequalities from Jepsen et al. (2008) and the second one the Strong Degree Constraints from Contardo, Desaulniers e Lessard (2015). Themodels are evaluated using some of literature benchmarking instances.
Assunto
Transportes coletivos, Engenharia de produção
Palavras-chave
Geração de colunas e cortes, Transporte escolar rural, Roteamento de veículos capacitado