Desenvolvimento de uma heurística para o problema de escalonamento de veículos com múltiplas garagens

Abstract

O escalonamento de veículos para múltiplas garagens é um problema clássico da Pesquisa Operacional de grande relevância à otimização da malha de transportes, de forma a buscar a melhor alocação dos recursos disponíveis. O problema é conhecido por ser do tipo NP-hard, e portanto a sua solução para grandes instâncias é realizada por heurísticas. Este trabalho aborda o desenvolvimento de uma heurística simples e eficiente para solucionar o MDVSP, buscando através da redução de possibilidades de viagens, pela retirada de viagens com baixas chances de pertencer a solução ótima reduzir a complexidade da rede. O problema reduzido, é então resolvido pela técnica de geração de colunas truncado e modificado, para resolver o problema de forma aceitável, encontrando soluções com bom compromisso entre tempo de execução e valor da função objetivo. A geração de colunas foi testada e validada através de comparações com trabalhos similares, enquanto que, cada técnica de redução de espaço de estados (de forma conjunta e individual) foram validados através da comparação com os resultados validados da geração de colunas modificada. A heurística mostrou uma melhoria considerável por meio da otimização do tempo de resolução, sem prejudicar os resultados de melhor valor, ficando com uma diferença máxima de 1% em comparação com os valores obtidos com geração de colunas. Se a redução for usada parcialmente, os tempos de solução podem ser reduzidos mais de sete vezes, com um pequeno incremento no valor da função objetivo. Pelas validações e experimentos realizados, pode-se afirmar que a heurística tem potencial para ser utilizada em problemas do mundo real, bem como servir como parte da solução de problemas correlatos mais complexos, como o crew scheduling, o disruption management e o escalonamento em tempo real.

The Multi Depot Vehicle Scheduling is a classical problem of Operations Research, with a great relevance to optimize the transportation network, as to find the best allocation of available resources. This problem is known to be NP-Hard, and therefore the solution of large instances is generally carried out by heuristics. This work proposes the development of a simple and efficient heuristic to solve the MDVSP, seeking by the reduction of travel possibilities, droping traveis with low chances to be in the best solution. The reduced problem is then solved by a modified truncated column generation technique, to solve the problem by an acceptable form, founding solutions for the MDVSP with a good compromise between time and costs. The column generation was tested and validated by the comparison of execution time and the value of objective function. The column generation was tested and comparised with similar works, whereas, each space state reduction technique (individual and joint) was validated in comparison with validated results of column generation truncated and modificated. The heuristics showed considerable improvements by the optimization of resolution time, without harm the best value results, obtaining differences lower as 1% comparing with the obtained values by the column generation solution. If the reduction is used partially, the solution times can be reduced in more then seven times, with a small increment in the objective function value. By the validations and experimenta realized, we can confirm that the heuristics has potential to be used in real world situations, as well as to serve as basis for the development of solution methods for more complex and correlated problems, as the crew scheduling problem, disruption management, and the real time assignment.