MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES / MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS
AUTOR(ES)
ALEXANDRE ALTOE PIGATTI
DATA DE PUBLICAÇÃO
2003
RESUMO
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.
ASSUNTO(S)
programacao inteira integer programming column generation geracao de colunas estabilizada geracao de colunas metaeuristica metaheuristic stabilized column generation
