XINFORMAÇÕ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.
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: AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM Autor: MARCELO LADEIRA REIS
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
MARCUS VINICIUS S P DE ARAGAO - ADVISOR
EDUARDO UCHOA BARBOZA - CO-ADVISOR
Nº do Conteudo: 6582
Catalogação: 15/06/2005 Idioma(s): PORTUGUESE - BRAZIL
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
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: AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM Autor: MARCELO LADEIRA REIS
EDUARDO UCHOA BARBOZA - CO-ADVISOR
Nº do Conteudo: 6582
Catalogação: 15/06/2005 Idioma(s): PORTUGUESE - BRAZIL
Tipo: TEXT Subtipo: THESIS
Natureza: SCHOLARLY PUBLICATION
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:
The Capacitated Vehicle Routing problem (CVRP) has been
one of the most
studied problems in the field of Combinatorial
Optimization. A straight
forward generalization of the popular Travelling
Salesperson problem, the
CVRP has drawn attention of the most prominent researchers
since the
early 60`s. One of the most important algorithms appeared
in the early
80`s when a suitable Lagrangean relaxation algorithm has
demonstrated to
be far better than the contemporary ones. This algorithm
suggested the
use of column generation algorithms that succeeded to
become the best
ones in the late 80`s and early 90`s. Finally, in the mid
90`s, cutting plane
methods presented results that convinced the community
that this should
be the approach for solving the hardest CVRP problems.
This dissertation
presents an overview of those early algorithms and
proposes a formulation
that allows uniting the best contributions of them. The
resulting algorithm,
labeled as a branch-and-cut-and-price algorithm, deals
with exponentially
many variables and constraints that define a relaxed
solution space that is
the intersection of the relaxed solution spaces considered
in the previous
algorithms. The dissertation also describes a specially
devised dynamic
programming algorithm to solve the column generation
subproblem and
discusses robust branching strategies that altogether
allowed to build an
algorithm that perfoms well on several different classes
of instances. The
computational experience has shown that the approach here
proposed leads
to lower bounds superior than the previous ones. Moreover,
it allowed to
consistently solve instances with up to 135 vertices,
including 18 that were
solved for the first time.
Descrição | Arquivo |
COVER, ACKNOWLEDGEMENTS, RESUMO, ABSTRACT, SUMMARY AND LISTS | |
CHAPTER 1 | |
CHAPTER 2 | |
CHAPTER 3 | |
CHAPTER 4 | |
CHAPTER 5 | |
CHAPTER 6 | |
CHAPTER 7 | |
BIBLIOGRAPHY |