How to make a greedy heuristic for the asymmetric traveling salesman problem competitive

Jäger, G. and B. Goldengorin
Additional contact information
B. Goldengorin: Groningen University

No 05A11, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: It is widely confirmed by many computational experiments that a greedy type heuristics for the Traveling Salesman Problem (TSP) produces rather poor solutions except for the Euclidean TSP. The selection of arcs to be included by a greedy heuristic is usually done on the base of cost values. We propose to use upper tolerances of an optimal solution to one of the relaxed Asymmetric TSP (ATSP) to guide the selection of an arc to be included in the final greedy solution. Even though it needs time to calculate tolerances, our computational experiments for the wide range of ATSP instances show that tolerance based greedy heuristics is much more accurate an faster than previously reported greedy type algorithms

Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://irs.ub.rug.nl/ppn/289323576 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/289323576 [302 Found]--> https://irs.ub.rug.nl/ppn/289323576 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(d550aae0-376b-4d42-b071-e924c2db2261).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(d550aae0-376b-4d42-b071-e924c2db2261).html)

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:gro:rugsom:05a11

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().