$$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$
INFORMAÇÕES SOBRE DIREITOS AUTORAIS


As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.

A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.

A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.

A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital

Avançada


Estatísticas | Formato DC|



Título: UM ALGORITMO DE GERAÇÃO DE COLUNAS E CORTES PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Autor(es): MARCELO LADEIRA REIS

Colaborador(es):  MARCUS VINICIUS S P DE ARAGAO - Orientador
EDUARDO UCHOA BARBOZA - Coorientador
Número do Conteúdo: 6582
Catalogação:  15/06/2005 Idioma(s):  PORTUGUÊS - BRASIL

Tipo:  TEXTO Subtipo:  TESE
Natureza:  PUBLICAÇÃO ACADÊMICA
Nota:  Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6582@1
Referência [en]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6582@2
Referência DOI:  https://doi.org/10.17771/PUCRio.acad.6582

Resumo:
O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez.

Descrição Arquivo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS  PDF
CAPÍTULO 1  PDF
CAPÍTULO 2  PDF
CAPÍTULO 3  PDF
CAPÍTULO 4  PDF
CAPÍTULO 5  PDF
CAPÍTULO 6  PDF
CAPÍTULO 7  PDF
BIBLIOGRAFIA  PDF
Agora você pode usar seu login do SAU no Maxwell!!
Fechar Janela



* Esqueceu a senha:
Senha SAU, clique aqui
Senha Maxwell, clique aqui