[pt] Esta dissertação estuda modelos e algoritmos para o
Problema de Alocação Generalizada (PAG) . A motivação para
este estudo foi uma nova aplicação do PAG: o Problema de
Carregamento de Caminhões (PCC) . A pesquisa desenvolvida
concentra-se no estudo e na proposta de algoritmos
aproximados (metaeurísticas) e exatos para a resolução do
PAG. Os algoritmos aproximados propostos baseiam-se em um
conceito recentemente criado por Fischetti e Lodi (2003),
que utiliza programação matemática inteira para a
exploração eficiente de vizinhanças mais abrangentes. Os
resultados obtidos foram comparáveis aos melhores
conhecidos, com a vantagem de exigir um esforço pequeno de
implementação e um menor tempo de processamento. O
algoritmo exato proposto é um algoritmo de branch-and-cut-
and-price, que tem como ponto de partida o algoritmo
de branch-and-price de Savelsbergh (1997). Técnicas de
estabilização da geração de colunas similares às propostas
por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram
estudadas no âmbito desta dissertação, que experimenta
com diferentes implementações deste mecanismo. O algoritmo
de branch-andcut-and-price estabilizado demonstrou sua
eficiência ao resolver à otimalidade instâncias que se
encontravam em aberto na literatura. Finalmente,
experiências com PCC permitiram que os códigos
desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment
Problem (PAG), models and algorithms are studied and
proposed. This work was motivated by a real world
application: the Truck Loading Problem (PCC). Research was
done on approximated (metaheuristics) and exact algorithm
for solving the PAG. The approximated algorithms proposed
were based on a recent idea from Fischetti and Lodi (2003).
It uses integer programming to explore wider neighborhoods.
The results were compared to the best known, while
demanding much less implementation effort and using less
cpu time. The exact algorithm proposed is a branch-and-cut-
and-price developed from the branch-and-price algorithm of
Savelsbergh (1997). We used stabilized column generation
techniques similar to the one by Du Merle, Villeneuve,
Desrosiers and Hansen (1999), and devised experiments with
different implementations of this mechanism. The resulting
algorithm proved its efficiency by solving to optimality
open instances from the literature. Finally, experiments
with the PCC turned possible the evaluation of the codes
developed on real problems.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:4132 |
| Date | 17 November 2003 |
| Creators | ALEXANDRE ALTOE PIGATTI |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0021 seconds