Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/9723

TitleAplicação do algoritmo volumétrico à resolução aproximada e exacta do problema do caixeiro viajante assimétrico
Other titlesApplication of the volume algorithm to the approximate and exact solving of the asymmetric
Author(s)Rocha, Ana Maria A. C.
Fernandes, Edite Manuela da G. P.
Soares, João L.
KeywordsAsymmetric travelling salesman problem
Disaggregated flow formulation
Lagrangian relaxation
Caixeiro viajente assimétrico
Formulação de fluxo desagregado
Relaxação Lagrangeana
Issue date2005
Citation"Investigação Operacional". 25:2 (2005) 277-294.
Abstract(s)Neste artigo apresentamos resultados computacionais obtidos com o algoritmo volumétrico, uma variante do método do subgradiente, na resolução da relaxação linear que decorre da formulação estendida de fluxo desagregado para o problema do Caixeiro Viajante Assimétrico. As experiências computacionais foram realizadas numa selecção de instâncias da TSPLib e num conjunto de instâncias geradas aleatoriamente de acordo com o Dimacs Implementation Challenge. Também experimentámos a aplicação de heurísticas durante a execução do algoritmo volumétrico. As experiências computacionais mostram sucesso moderado com instâncias de média dimensão.
In this paper we present computational results with the volume algorithm, a variant of the subgradient method, when solving the linear relaxation that stems from the extended disaggregated °ow formulation of the Asymmetric Travelling Salesman Problems. Computational experiments were performed on a selection of instances from the TSPLib and some randomly generated instances according to the Dimacs Implementation Challenge. We have also tried ATSP heuristics within the volume algorithm. Computational experiments show moderated success on medium-scale instances.
TypeArticle
URIhttp://hdl.handle.net/1822/9723
Peer-Reviewedyes
AccessOpen access
Appears in Collections:LES/ALG - Artigos em revistas científicas nacionais com arbitragem

Files in This Item:
File Description SizeFormat 
ATSP_port_2005_06_13.pdf294,77 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID