Repositório Digital

A- A A+

Modelagem do problema de escalonamento de veículos com múltiplas garagens usando rede tempo-espaço : grandes instâncias e frota heterogênea

.

Modelagem do problema de escalonamento de veículos com múltiplas garagens usando rede tempo-espaço : grandes instâncias e frota heterogênea

Mostrar registro completo

Estatísticas

Título Modelagem do problema de escalonamento de veículos com múltiplas garagens usando rede tempo-espaço : grandes instâncias e frota heterogênea
Autor Guedes, Pablo Cristini
Orientador Borenstein, Denis
Data 2014
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Escola de Administração. Programa de Pós-Graduação em Administração.
Assunto Escalonamento de veículos
Garagens
Logística
Transportes
Veículos automotores
[en] Column generation
[en] MDVSP
[en] MDVTSP
[en] Time-space network
Resumo O problema de escalonamento de veículos com múltiplas garagens (MDVSP, do inglês Multi-Depot Vehicle Scheduling Problem) é um problema clássico de logística e transportes. O MDVSP também é a base para a solução de vários problemas correlatos, tais como o problema de escalonamento de veículos em tempo-real e soluções integradas com o escalonamento de veículos, tais como o escalonamento da tripulação e otimização da tabela de horários. Desta forma, aprimorar a solução deste problema pode ser considerado de grande relevância, a qual permitirá resolver grandes instâncias reais de forma eficiente, bem como permitir a solução de problemas correlatos. O objetivo desta dissertação é verificar a aplicabilidade da utilização da rede tempo-espaço e do método de geração de colunas modificado proposto, para a solução deste problema, e de sua variante com frota heterogênea, considerando grandes instâncias. Diversos testes foram realizados utilizando o gerador de instâncias aleatórias com base na distribuição de demandas proposto. Grandes instâncias, envolvendo milhares de viagens (entre 500-10.000) e dezenas de garagens (4-128) são resolvidas em tempos razoáveis.
Abstract The multiple-depot vehicle-scheduling problem (MDVSP) is a classic logistic and transportation problem. The MDVSP is also a subproblem for solving various related problems, such as the real time vehicle scheduling problem, disruption management; and integrated problems such as the vehicle and crew scheduling problems. Although several mathematical and solution method have been developed in the literature, large instances (involving thousands of trips and several depots) are still difficult to solve in a reasonable time. The objective of this research work is to verify the applicability of the use of the space-time network towards obtaining good solutions for large instances in short time. Time-space network was suggested by Kliewer et al (2006), and it is positioned with respect to two-dimensional axes, one representing time and the other one space or stations. The arcs represent deadheading movements; and waiting periods in the same station. Solution methods for the MDVS combining time space with integer linear programming solvers and column generation were developed. Extensive testing was carried out using random generated instances, based on demands distribution. Large instances, involving thousands of trips (between 1,000-10,000) and dozen (4-64) depots, are solved in reasonable times.
Tipo Dissertação
URI http://hdl.handle.net/10183/96846
Arquivos Descrição Formato
000915445.pdf (569.5Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.