Utilize este identificador para referenciar este registo: https://hdl.handle.net/10316/14418
Título: Aplicação do algoritmo volumétrico na resolução aproximada e exacta do problema do caixeiro viajante assimétrico
Autor: Rocha, Ana Maria 
Fernandes, Edite M. G. P. 
Soares, João 
Palavras-chave: Asymmetric travelling salesman problem; Disaggregated flow formulation; Lagrangian relaxation
Data: 2005
Editora: APDIO - Associação Portuguesa de Investigação Operacional
Citação: ROCHA, Ana Maria; FERNANDES, Edite M. G. P.; Soares, João - Aplicação do algoritmo volumétrico na resolução aproximada e exacta do problema do caixeiro viajante assimétrico. "Investigação Operacional". ISSN 0874-5161. 25:2 (2005) 277-294
Título da revista, periódico, livro ou evento: Investigação Operacional
Volume: 25
Número: 2
Local de edição ou do evento: Lisboa
Resumo: 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 flow 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.
URI: https://hdl.handle.net/10316/14418
ISSN: 0874-5161
Direitos: openAccess
Aparece nas coleções:FCTUC Matemática - Artigos em Revistas Nacionais

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato
Aplicação do algoritmo volumétrico na resolução.pdf254.1 kBAdobe PDFVer/Abrir
Mostrar registo em formato completo

Visualizações de página 50

520
Visto em 26/mar/2024

Downloads

30
Visto em 26/mar/2024

Google ScholarTM

Verificar


Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.