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
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:
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.