Teste de uma heurística para o problema de programação de trens em linhas singelas

Abstract

Este trabalho avalia a efetividade de uma heurística para a programação de trens em um trecho de ferrovia brasileira de linha singela. O algoritmo central empregado foi o módulo de grade de horário do TrainWorld (Chen et al., 2013), uma versão melhorada da heurística de Lee e Chen (2009). A heurística avalia diversas alternativas de sequência de trens entre estações até encontrar a melhor alternativa possível de minimizar atrasos no sistema. Dois cenários foram estudados: a simulação de um trecho de linha ferroviária fictícia (três trens e três estações) e uma simulação derivada de um caso real de uma ferrovia brasileira localizada no estado de Minas Gerais, envolvendo 28 trens e 15 estações em uma linha singela. Os resultados indicam que a grade de horário proposta pela heurística foi superior ao da grade de horário empregada pela ferrovia, entretanto o tempo de execução computacional ainda é parcialmente elevado. Oportunidades de melhoria da heurística foram identificadas.

This study evaluates the effectiveness of a heuristic for scheduling trains on a stretch of a single Brazilian railway line. The algorithm used was the central module of the time grid TrainWorld (CHEN et al., 2013), an improved version of the heuristic Lee and Chen (2009). The heuristic evaluates several alternative sequence of trains between railway stations to find the best possible alternative that minimize delays in the system. Two scenarios were studied: a simulation of a fictional stretch of railway line (three trains and three stations) and a simulation derived from a real case of a railroad located in the Brazilian state of Minas Gerais, involving 28 trains and 15 stations in a single line. The results indicate that the time grid proposed by the heuristic was better than the time grid used by the railroad, but the computation running time remains high. Opportunities for improvement were identified heuristics.