Embedding learning capability in Lagrangean relaxation: An application to the travelling salesman problem

Reza Zamani and Sim Kim Lau

European Journal of Operational Research, 2010, vol. 201, issue 1, 82-88

Abstract: This paper presents an effective procedure that finds lower bounds for the travelling salesman problem based on the 1-tree using a learning-based Lagrangian relaxation technique. The procedure can dynamically alter its step-size depending upon its previous iterations. Along with having the capability of expansion-contraction, the procedure performs a learning process in which Lagrange multipliers are influenced by a weighted cost function of their neighbouring nodes. In analogy with simulated annealing paradigm, here a learning process is equivalent to escaping local optimality via exploiting the structure of the problem. Computational results conducted on Euclidean benchmarks from the TSPLIB library show that the procedure is very effective.

Keywords: Traveling; salesman; Lagrangian; relaxation; Heuristics (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00073-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:201:y:2010:i:1:p:82-88

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().