Made available in DSpace on 2019-03-29T23:53:02Z (GMT). No. of bitstreams: 0
Previous issue date: 2015-09-18 / In this dissertation, we propose an Integer Linear Programming model to solve a Crew Scheduling Problem (CSP) in urban bus public transportation. As a starting point, we search for the solution that represents the global optimum in terms of the quantity of drivers used in the scheduling, using IBM ILOG CPLEX as optimization tool. We model the CSP as a set partitioning problem to avoid the allocation of different drivers to a given task. To meet a complementary goal, we propose a second mathematical model to minimize the amount of untapped hours and, thus, to reduce the extra-time hours performed by drivers. Several computational tests were performed with real-world data of urban bus lines provided by the municipal agency of the city of Fortaleza that regulates this sector, Etufor. To make the CSP more tractable, different strategies of determination of tasks were tested and compared. Computational results suggest the use of specific techniques, in accordance with the size of the bus line, for generating good solutions with respect to the amount of drivers and of untapped hours. Finally, a case study is performed to compare the quality of our solutions to those of a urban bus company, particularly in terms of number of drivers used in the schedule, the usage of available hours, and legal restrictions as well.
Keywords: Crew Scheduling Problem, Urban Bus Public Transportation, Integer Linear Programming, Heuristics, Labor Laws / Este trabalho propõe uma abordagem que utiliza Programação Linear Inteira para a solução do Problema de Programação de Tripulação (PPT) em transporte público de ônibus urbano. Como ponto de partida, buscamos a solução que representa o ótimo global em termos de quantidade de motoristas, através do uso da ferramenta IBM ILOG CPLEX. Essa modelagem tratou o PPT como um problema de particionamento de conjunto, o que evita a necessidade de um pós-processamento das soluções para a remoção de dupla alocação de tarefas. Para atender um objetivo secundário, uma segunda modelagem matemática foi proposta para minimizar a quantidade de horas não aproveitadas, e assim reduzir a utilização de horas extras por parte da empresa. Diversos testes computacionais foram realizados com dados reais de linhas de transporte urbano fornecidos pelo órgão municipal da cidade de Fortaleza que regulamenta o setor, Etufor. Para tornar o PPT tratável, algumas abordagens de determinação de tarefas foram testadas e comparadas. Os resultados computacionais obtidos são interessantes pois sugerem a utilização de técnicas específicas de acordo com o porte da linha para a geração de boas soluções no que se refere à quantidade de motoristas e à redução das horas não aproveitadas. Por fim, um estudo de caso é apresentado, comparando a solução do modelo com a solução praticada por uma empresa, em termos de quantidade de motoristas escalados, aproveitamento das horas contratadas e também respeito às restrições. Palavras-chave: Problema de Programação de Tripulação, Transporte Público de Ônibus Urbano, Programação Linear Inteira, Heurísticas, Restrições Trabalhistas.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/95879 |
| Date | 18 September 2015 |
| Creators | Nunes, Rafael de Paula |
| Contributors | Nepomuceno, Napoleao Vieira, Pinheiro, Plácido Rogério, Viana, Gerardo Valdisio Rodrigues, Nepomuceno, Napoleao Vieira |
| Publisher | Universidade de Fortaleza, Mestrado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 5443571202788449035, 500, 500, -7645770940771915222 |
Page generated in 0.0028 seconds