[pt] Os problemas advindos da área de logística de transportes,
em especial no que diz respeito ao uso racional de frotas
de veículos, são amplamente estudados na área de otimização
combinatória. A natureza intrinsicamente combinatorial
desses problemas sugere que boa parte deles pode ser
formulada e resolvida como um problema de programação
linear inteira. Contudo, a maioria dos algoritmos
atualmente disponíveis não consegue encontrar, em tempos
computacionais aceitáveis, a solução ótima para instâncias
de porte razoável. O sucesso desses algoritmos tem sido
limitado, em parte devido ao fato dos mesmos não explorarem
avanços recentes na área de programação linear inteira.
Algumas dessas novas técnicas e suas aplicações a problemas
de roteamento de veículos são o objeto de estudo desta
dissertação. Primeiro são apresentadas as técnicas básicas
de decomposição de problemas de programação linear e linear
inteira e de 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. Em seguida são descritos problemas de
roteamento onde essa metodologia foi aplicada.
Inicialmente, é apresentado o problema de roteamente do
veículos com restrição de capacidade, o PRVC. Em seguida
são apresentados problemas de roteamento de veículos com
janela de tempo e frota heterogenea. Para cada problema,
descrevemos como as técnicas descritas acima foram
aplicadas e os resultados computacionais para um grande
número de instâncias. Finalmente, no último capítulo,
mostramos um caso real da aplicação do problema de
roteamento de veículos com janela de tempo e frota
heterogênea, que é o caso do problema de distribuição de
jornais numa grande empresa de comunicação do Rio de
Janeiro. / [en] Optimization techniques have an important role in
Transportation Logistics. The combinatorial nature of
several problems related to this area seggests integer
programming as a natural approach to solve them.
Nevertheless, there are many cases in which instances of
reasonable size are still beyond the resolution capability
of the algotithms presented in the literature. The sucess
of the known algotithms have therefore been limited partly
to the fact that most of them have not incorporated any
recent relevant advances in the combinatorial optimization
field. Some of these new techniques and their applications
are the main subject of this dissertation. Firstly, basic
decomposition techniques for linear and integer programming
problems, as well as the relates column generation approach
are 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 arousing from this approach
are explored and the resulting consequences to the standard
branch-and-bound algotithm and its variations branch-and-
cut, branch-and-prince and branch-and-cut-and-price are
presented. Later, routing problems where this methodology
was applied were addressed with the capacitated vehicle
routing problems - CVRP and followed by vehicle routing
problems with time windows and heterogeneous fleet. For
each problem, it is described how the techniques mentioned
above were reported. Finally, in the last time windows and
heterogeneous fleet, which is the case of a newspaper
distribution in a major communication company in Rio de
Janeiro.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:6532 |
| Date | 03 June 2005 |
| Creators | FERNANDA DE ARAUJO GOMES MENEZES |
| Contributors | OSCAR PORTO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0028 seconds