Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/14417
Title: Um melhor limite inferior para o problema do caixeiro viajante assimétrico baseado no problema da afectação
Other Titles: An improved lower bound for the asymmetric traveling salesman problem based on the assignment problem
Authors: Ramires, Ana 
Soares, João 
Keywords: Optimization; Combinatorial Optimization; Lower Bounds; Asymmetric Traveling Salesman; Disjunctive Programming
Issue Date: 2005
Publisher: APDIO - Associação Portuguesa de Investigação Operacional
Citation: 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
Serial title, monograph or event: Investigação Operacional
Volume: 25
Issue: 1
Place of publication or event: Lisboa
Abstract: 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: http://hdl.handle.net/10316/14417
ISSN: 0874-5161
Rights: openAccess
Appears in Collections:FCTUC Matemática - Artigos em Revistas Nacionais

Files in This Item:
File Description SizeFormat
Um melhor limite inferior para o problema do caixeiro viajante.pdf269.93 kBAdobe PDFView/Open
Show full item record

Page view(s) 50

381
checked on Jun 10, 2021

Download(s)

30
checked on Jun 10, 2021

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.