COMPARAÇÃO DE ALGORITMOS HEURÍSTICOS PARA UM PROBLEMA DE PLANEJAMENTO OPERACIONAL DE TRANSPORTE PÚBLICO

24 a 28/09

COMPARAÇÃO DE ALGORITMOS HEURÍSTICOS PARA UM PROBLEMA DE
PLANEJAMENTO OPERACIONAL DE TRANSPORTE PÚBLICO
Douglas Baroni Rizzato1, Rubens Zenko Sakiyama2, Ademir Aparecido Constantino3, Wesley
Romão4
Departamento de Informática – Universidade Estadual de Maringá (UEM)
Avenida Colombo, 5790 – 87020-900 – Bloco C56 – PR – Brasil
1
[e-mail], [e-mail], [e-mail], [e-mail]

RESUMO
Este trabalho aborda um problema escalonamento de motoristas de uma empresa de transporte público, baseado em um caso real de grande porte, o qual tem como objetivo formar jornadas diárias de trabalho que atenda a uma série de restrições e minimize o custo operacional. Dada a complexidade computacional e escala dos dados, este trabalho propõe um algoritmo heurístico para resolver tal problema buscando minimizar os custos da solução. O algoritmo é baseado na resolução de sucessivos problemas de atribuição, sendo dividido em duas fases. Na fase da construção da solução inicial é gerado um conjunto de jornadas divididas em várias camadas. Na fase de melhoramento são empregados dois procedimentos, PCR e K-Swap, combinados com a metaheurística VND, para minimização do custo da solução inicial. Para validar o algoritmo foram realizados testes com instâncias de dados reais e aleatórias, incluindo uma instância real com mais de
2300 viagens. Em geral, os resultados alcançados obtiveram custos menores que os utilizados para comparação, evidenciando os benefícios das técnicas apresentadas.

IS
A

N
A

PALAVRAS CHAVE. Problema de Grande Porte, Problema de Escalonamento de Motoristas,
Heurística, Problema de Atribuição.

É

Área principal: Logística e Transporte, Metaheurística

R
P

ABSTRACT

This paper tackles a bus-driver scheduling problem for a public transport company, based on large-scale real-would instances, which aims to construct a set of dairy work duties satisfying a set of constraints and to