01811nam a2200229 a 450000100080000000500110000800800410001910000190006024501440007926001340022330000140035750000330037152009400040465300310134465300260137565300310140165300340143265300380146665300250150465300310152970000210156010072822020-01-20       1999    bl uuuu     u00u1 u    #d1 aNARCISO, M. G.  aUsing local surrogate information in lagrangean relaxationban application to symmetric traveling salesman problems.h[electronic resource]  aIn: OFICINA DE PLANEJAMENTO E CONTROLE DA PRODUÇÃO EM SISTEMAS DE MANUFATURA, 1., 1999, Campinas. Anais... Campinas: Inpec1999  ap. 52-57.  aProjeto tematico 97/13930-1.  aThe Traveling Salesman Problem (TSP) is one of the most studied problems in Combinatorial Optimization literature. Several articles have been published on the subject and it remains today as an interesting and challenging problem. The most common interpretation of the problem seeks the shortest tour for a salesman on a number of cities or clients. Clients must be visited exactly one time and the salesman must return to their home city. For a comprehensive survey of solution methods, applications and related problems see the book of Lawler et al. [27]. Laporte [25] gives another review, including applications examples on computer wiring, wallpaper cutting, hole punching, job sequencing, dartboard design and crystallography. The problem is well known to be NP-hard [25] justifying the use of heuristics, mainly for large scale problems. Johnson and McGeoch [20] give a recent survey on the use of local search based heuristics.  aCombinatorial optimization  aLagrangean relaxation  aOtimização combinatória  aProblema do caixeiro viajante  aRelaxação lagrangeana/surrogate  aSurrogate relaxation  aTraveling salesman problem1 aLORENA, L. A. N.