[pt] MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES
[en] MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS
| dc.contributor | MARCUS VINICIUS S P DE ARAGAO | |
| dc.creator | ALEXANDRE ALTOE PIGATTI | |
| dc.date | 2003-11-17 | |
| dc.date.accessioned | 2022-09-21T21:42:03Z | |
| dc.date.available | 2022-09-21T21:42:03Z | |
| dc.identifier | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4132@1 | |
| dc.identifier | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4132@2 | |
| dc.identifier | http://doi.org/10.17771/PUCRio.acad.4132 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12032/42322 | |
| dc.description | [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. | |
| dc.description | [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. | |
| dc.language | pt | |
| dc.publisher | MAXWELL | |
| dc.subject | [pt] PROGRAMACAO INTEIRA | |
| dc.subject | [pt] METAEURISTICA | |
| dc.subject | [pt] GERACAO DE COLUNAS ESTABILIZADA | |
| dc.subject | [pt] GERACAO DE COLUNAS | |
| dc.subject | [en] INTER LINEAR PROGRAMMIN | |
| dc.subject | [en] METAHEURISTIC | |
| dc.subject | [en] STABILIZED COLUMN GENERATION | |
| dc.subject | [en] COLUMN GERERATION | |
| dc.title | [pt] MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES | |
| dc.title | [en] MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS | |
| dc.type | TEXTO |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||