[pt] 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. / [en] 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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:6582 |
| Date | 15 June 2005 |
| Creators | MARCELO LADEIRA REIS |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0031 seconds