[pt] A natureza intrinsicamente combinatorial de muitos
problemas advindos da área de logística de transportes, em
especial aqueles que dizem respeito ao uso racional de
frotas de veículos, sugere que boa parte dos mesmos pode
ser formulada e resolvida como um problema de programação
linear inteira. Contudo, a maioria dos algoritmos até o
momento disponíveis não consegue encontrar, em tempos
computacionais aceitáveis, a solução ótima para instâncias
de porte razoável. O objeto de estudo desta tese é a
exploração de técnicas mais recentes da área de programação
linear inteira e suas aplicações a problemas de roteamento
de veículos. A primeira parte da tese descreve, além das
técnicas básicas de decomposição de problemas de
programação linear e linear inteira e de geração de
colunas, uma proposta de reformulação de problemas de
programação linear inteira alternativa àquela que gera o
tradicional problema mestre de Dantzig-Wolfe, geralmente
utilizados em abordagens por 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. Na segunda
parte da tese,
inicialmente, é apresentada a técnica denominada de Geração
Projetada
de Colunas e sua aplicação ao problema de Roteamento de
Veículos com
Restrição de Capacidade. Em seguida é abordada a resolução
do problema
de Roteamento de Veículos sobre Arcos, através de sua
transformação ao
primeiro problema citado e uso de um algoritmo branch-and-
cut-and-price.
Finalmente, é proposto um novo problema na área de
redistribuição de
veículos de aluguel, para o qual é proposta uma formulação
segundo uma
abordagem por geração de colunas. São apresentados, ainda,
procedimentos
para a geração de colunas e resultados computacionais
obtidos com um
algoritmo branch-and-price para essa formulação. / [en] Optimization techniques have an important role in
Transportation Logistics.
The combinatorial nature of the problems related to this
area suggests
integer programming as a natural approach to their
resolution. Nevertheless
there are many cases where even instances of reasonable
size still beyond
the resolution capability of the current known algorithms.
The success of
the known algorithms have therefore been limited. This can
be justified by
the fact the most of them leave important recent advances
in the combinatorial
optimization field unexplored. Some of these new techniques
and
their applications are the main subject of this thesis. In
the first part, the
basic decomposition techniques for linear and integer
programming problems
as well as the related column generation approach is
addressed. This
is followed by the presentation of a reformulation
technique for linear and
integer programming which is alternative to the well known
Dantzig-Wolfe
master program. The new possibilities coming from this
approach are explored
and the resulting consequences to the standard branch-and-
bound
algorithm and its variations branch-and-cut, branch-and-
price and branchand-
cut-and-price are presented. The second part of this text
addresses the
application of the metodologies described in part one to
routing problems
where capacity constraints are considered. First, a
techinque named Projected
Column Generation is described in the context of the
Capacitated
Vehicle Routing Problem. Then, it is presented a new
transformation from
the Capacitated Arc Routing Problem to the Capacitated
Vehicle Routing
Problem as well as a tailored branch-and-cut-and-price to
solve this problem.
Finally, a new problem in vehicle redistrubution is
described together
with a column generation approach for its resolution.
Computational results
for all applications are presented.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:6029 |
| Date | 09 March 2005 |
| Creators | HUMBERTO JOSE LONGO |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.002 seconds