Abordagens heurísticas para o problema de agendamento de equipes de manutenção de sinalização ferroviária
Visualizar/ Abrir
Data
2021Autor
Doehnert, Ruany Batista Leite, 1993-
Metadata
Mostrar registro completoResumo
Resumo: O sistema de sinalização ferroviária é um componente essencial para garantir a segurança e eficiência nas operações dos trens. O presente trabalho aborda o problema de agendamento de equipes de manutenção preventiva em uma ferrovia. Para garantir o funcionamento eficiente do sistema de sinalização, o planejamento de tarefas de manutenção preventiva é essencial. Realizou-se uma revisão sistemática da literatura com relação aos problemas de agendamento de equipes, identificando modelagens e métodos de resolução. Para resolução do problema, considerou-se um modelo matemático de Programação Inteira Mista (Mixer Integer Programming - MIP). O problema abordado se destaca dos demais problemas de agendamentos de equipes, pois considera a competência da equipe que irá executar a tarefa de manutenção. Essa configuração gera ainda mais complexidade para o problema. A resolução do modelo exato se torna inviável computacionalmente para instâncias com 11 ou mais tarefas devido a sua complexidade. Testes iniciais mostram que a resolução do modelo exato exige um tempo computacional de mais de 12 horas de otimização para instâncias com mais de 11 tarefas. Foram selecionadas 2 heurísticas para resolução do problema, Relax and Fix e Fix and Optimize. A heurística Relax and Fix não traz resultados satisfatórios devido a recorrência de soluções infactíveis. Na abordagem Fix and Optimize considerou-se variações dos índices a serem fixados, trazendo resultados satisfatórios (os valores da função objetivo são semelhantes aos valores encontrados na resolução do modelo exato). Os testes apresentam melhores resultados ao fixar o índice referente às tarefas (dentre os índices equipe, tarefa e data). A abordagem Fix and Optimize sequencial 2TL apresenta o melhor desempenho dentre todas as abordagens, encontrando soluções melhores que o modelo exato em 3 instâncias. Foram feitos testes usando a ferramenta do solver Gurobi, na resolução de Múltiplos Cenários em paralelo. A otimização de múltiplos cenários em paralelo se mostra bastante eficiente com relação ao tempo computacional. A abordagem Fix and Optimize aleatório 3EL também apresenta resultados satisfatórios (valores da função objetivo próximas aos valores encontrados pelo modelo exato). Concluiu-se que, dentre as abordagens propostas, a escolha dos índices a serem fixados interfere nos resultados. De acordo com os testes realizados, a fixação das tarefas apresenta melhores resultados para o problema abordado. Do ponto de vista prático a presente pesquisa contribui para a resolução do problema de agendamento de equipes de manutenção permitindo realizar um planejamento de tarefas de manutenção preventiva em uma ferrovia, ou até considerando outro cenário que envolva o planejamento de tarefas de manutenção considerando a competência do funcionário que irá realizar determinada tarefa. A presente pesquisa contribui apresentando testes computacionais de forma a comparar as abordagens apresentadas. Palavras-chaves: Problemas de Agendamento de Equipes. Tarefas de Manutenção. Abordagens heurísticas Abstract: The railway signaling system is an essential component to ensure the safety and efficiency of train operations. The present work addresses the Preventive Maintenance Crew Scheduling Problem on a Railway. To ensure the efficient operation of the signaling system, planning preventive maintenance tasks is essential. A systematic literature review was carried out regarding crew scheduling problems, identifying models and resolution methods. To solve the problem, a mathematical model of Mixed Integer Programming (MIP) was considered. The problem addressed stands out from the other crew scheduling problems, as it considers the competence of the crew that will perform the maintenance task. This configuration creates even more complexity for the problem. The resolution of the exact model becomes computationally unviable to perform with 11 or more tasks due to its complexity. Initial tests show that the resolution of the exact model requires a computational time of more than 12 hours of optimization for instances with more than 11 tasks. Two heuristics are proposed to solve the problem, Relax and Fix and Fix and Optimize. The Relax and Fix heuristic does not bring satisfactory results due to the recurrence of infactible solutions. In the Fix and Optimize approach, variations in the indexes to be fixed were considered, bringing satisfactory results (the values of the objective function are similar to the values found in the resolution of the exact model). The tests show better results when setting the index for the tasks (among the team, task and date indexes). The sequential 2TL Fix and Optimize approach presents the best performance among all approaches, finding better solutions than the exact model in 3 instances. Tests were made using the Gurobi solver tool, in the resolution of Multiple Scenarios in parallel. The optimization of multiple scenarios in parallel proves to be quite efficient with respect to computational time. The random 3EL Fix and Optimize approach also shows satisfactory results (values of the objective function close to the values found by the exact model). We concluded that, among the proposed approaches, the choice of indexes to be fixed interferes in the results. According to the tests performed, the fixation of tasks presents better results for the problem addressed. From a practical point of view, this research contributes to solving the problem of scheduling maintenance teams by allowing the planning of preventive maintenance tasks on a railway, or even considering another scenario that involves the planning of maintenance tasks considering the competence of the employee who will perform this task. This research contributes to computational tests in order to compare how to check. Key-words: Crew scheduling problems. Maintenance Tasks. Heuristic approaches.
Collections
- Dissertações [190]