Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276298
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Problemas de escalonamento no transporte coletivo : programação por restrições e outras tecnicas
Author: Yunes, Tallys Hoover
Advisor: Moura, Arnaldo Vieira, 1950-
Abstract: 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

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
Subject: Otimização combinatória
Programação (Matemática)
Programação lógica
Language: Português
Editor: [s.n.]
Citation: YUNES, Tallys Hoover. Problemas de escalonamento no transporte coletivo: programação por restrições e outras tecnicas. 2000. 127p. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/276298>. Acesso em: 2 ago. 2018.
Date Issue: 2000
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Yunes_TallysHoover_M.pdf6.41 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.