Mostrar el registro sencillo del ítem

[en] MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS

dc.contributorMARCUS VINICIUS S P DE ARAGAO
dc.creatorALEXANDRE ALTOE PIGATTI
dc.date2003-11-17
dc.date.accessioned2022-09-21T21:42:03Z
dc.date.available2022-09-21T21:42:03Z
dc.identifierhttps://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4132@1
dc.identifierhttps://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=4132@2
dc.identifierhttp://doi.org/10.17771/PUCRio.acad.4132
dc.identifier.urihttps://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.languagept
dc.publisherMAXWELL
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.typeTEXTO


Ficheros en el ítem

FicherosTamañoFormatoVer

No hay ficheros asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem


© AUSJAL 2022

Asociación de Universidades Confiadas a la Compañía de Jesús en América Latina, AUSJAL
Av. Santa Teresa de Jesús Edif. Cerpe, Piso 2, Oficina AUSJAL Urb.
La Castellana, Chacao (1060) Caracas - Venezuela
Tel/Fax (+58-212)-266-13-41 /(+58-212)-266-85-62

Nuestras redes sociales

facebook Facebook

twitter Twitter

youtube Youtube

Asociaciones Jesuitas en el mundo
Ausjal en el mundo AJCU AUSJAL JESAM JCEP JCS JCAP