Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/14417
Título: | Um melhor limite inferior para o problema do caixeiro viajante assimétrico baseado no problema da afectação | Outros títulos: | An improved lower bound for the asymmetric traveling salesman problem based on the assignment problem | Autor: | Ramires, Ana Soares, João |
Palavras-chave: | Optimization; Combinatorial Optimization; Lower Bounds; Asymmetric Traveling Salesman; Disjunctive Programming | Data: | 2005 | Editora: | APDIO - Associação Portuguesa de Investigação Operacional | Citação: | RAMIRES, Ana; SOARES, João - Um melhor limite inferior para o problema do caixeiro viajante assimétrico baseado no problema da afectação. "Investigação Operacional". ISSN 0874-5161. 25:1 (2005) 63-83 | Título da revista, periódico, livro ou evento: | Investigação Operacional | Volume: | 25 | Número: | 1 | Local de edição ou do evento: | Lisboa | Resumo: | Neste artigo explicamos como obter um limite inferior para o valor óptimo do problema do caixeiro viajante assimétrico melhor do que o que advém do problema de afectação através da resolução sucessiva de problemas de afectação. O algoritmo que propomos é um método de primeira ordem baseado na função de penalidade exponencial cujas direcções de deslocamento são definidas com base numa relaxação disjuntiva que propomos ser de dois tipos, uma baseada em ciclos e a outra baseada em cliques. In this article we decribe how to compute a lower bound for the asymmetric traveling salesman problem that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a first-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we proposed as being one of two possible classes, one based on cycles, the other based on cliques. |
URI: | https://hdl.handle.net/10316/14417 | ISSN: | 0874-5161 | Direitos: | openAccess |
Aparece nas coleções: | FCTUC Matemática - Artigos em Revistas Nacionais |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Um melhor limite inferior para o problema do caixeiro viajante.pdf | 269.93 kB | Adobe PDF | Ver/Abrir |
Visualizações de página 50
553
Visto em 22/out/2024
Downloads
137
Visto em 22/out/2024
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.