Problemas de escalonamento no transporte coletivo : programação por restrições e outras tecnicas
Tallys Hoover Yunes
DISSERTAÇÃO
Português
(Broch.)
T/UNICAMP Y92p
Campinas, SP : [s.n.], 2000.
127p. : il.
Orientador : Arnaldo Vieira Moura
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento de mão-de-obra oriundo da operação diária de uma empresa de ônibus urbanos da cidade de Belo Horizonte. Por questões de complexidade, este tipo de problema é normalmente dividido em dois subproblemas, a...
Ver mais
Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento de mão-de-obra oriundo da operação diária de uma empresa de ônibus urbanos da cidade de Belo Horizonte. Por questões de complexidade, este tipo de problema é normalmente dividido em dois subproblemas, a saber: crew scheduling, que trata a alocação diária de viagens a duplas de funcionários (motorista e cobrador), e crew rostering, que parte da solução do subproblema anterior e constrói uma escala de trabalho de mais longo prazo, e.g. um mês. Cada um desses subproblemas foi abordado utilizando-se técnicas de Programação Matemática e Programação por Restrições. Para o problema de crew scheduling, em particular, desenvolveu-se também um algoritmo híbrido de geração de colunas combinando as duas técnicas mencionadas e cujo desempenho foi significativamente melhor que o dos métodos isolados. Em geral, os modelos matemáticos resultantes de problemas dessa natureza são de grande porte. No caso aqui tratado, a matriz de coeficientes do programa linear associado a algumas instâncias dos problemas chega a conter dezenas de milhões de colunas. Todos os algoritmos propostos para a solução do problema foram implementados e testados sobre dados reais obtidos junto à empresa em questão. A análise dos resultados computacionais mostra que foi possível obter soluções de excelente qualidade em um tempo de computação adequado para as necessidades da empresa. Em particular, para o subproblema de scheduling, foi possível comprovar que as soluções obtidas são ótimas
Ver menos
Abstract: This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the...
Ver mais
Abstract: This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the problem is usualIy divided in two distinct subproblems, namely: crew scheduling, that deals with the daily alIocation of trips to crews, and crew rostering, which takes the solution of the first subproblem and extends the scheduling to a longer planning horizon, e.g. a month. We have tackled each one of these subproblems using Mathematical Programming (MP) and Constraint Logic Programming (CLP) approaches. Besides, we also developed a hybrid column generation algorithm for solving the crew scheduling problem, combining MP and CLP, which performed much better than the two previous approaches when taken in isolation. Real world crew management problems typicalIy give rise to large scale mathematical models. In our case, the coefficient matrix of the linear program associated with some instances of the problem contains tens of millions of columns. AlI the proposed algorithms have been implemented and tested over real world instances obtained from the aforementioned company. The analysis of our experiments indicates that it was possible to find high quality solutions within computational times that are suitable for the company's needs. In particular, we were able to find provably optimal solutions for the crew scheduling problem
Ver menos
Problemas de escalonamento no transporte coletivo : programação por restrições e outras tecnicas
Tallys Hoover Yunes
Problemas de escalonamento no transporte coletivo : programação por restrições e outras tecnicas
Tallys Hoover Yunes
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra