APPLICATION OF INTEGER PROGRAMMING TECHNIQUES IN VEHICLE ROUTING PROBLEM WITH TIME WINDOWS / APLICAÇÕES DE TÉCNICAS DE PROGRAMAÇÃO INTEIRA EM PROBLEMAS DE ROTEAMENTO DE VEÍCULOS COM JANELAS DE TEMPO

AUTOR(ES)

FERNANDA DE ARAUJO GOMES MENEZES

DATA DE PUBLICAÇÃO

2004

RESUMO

Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro.

ASSUNTO(S)

programacao inteira column generation roteamento de veiculos integer programming geracao de colunas vehicle routing

Documentos Relacionados

• UMA APLICAÇÃO DE ALGORITMOS DE COLÔNIAS DE FORMIGAS EM PROBLEMAS DE ROTEIRIZAÇÃO DE VEÍCULOS COM JANELAS DE TEMPO
• Scatter search for Heterogeneous Fleet vehicle routing problem with Time Windows and Split Deliveries.
• Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea.
• INTEGER PROGRAMMING PROBLEMS ON TELECOMMUNICATIONS OPTICAL NETWORKS
• RESOLUÇÃO DE PROBLEMAS DE LOGÍSTICA FERROVIÁRIA UTILIZANDO PROGRAMAÇÃO INTEIRA