How to make a greedy heuristic for the asymmetric traveling salesman problem competitive
AbstractIt 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
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University of Groningen, Research Institute SOM (Systems, Organisations and Management) in its series Research Report with number 05A11.
Date of creation: 2005
Date of revision:
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Glover, Fred & Gutin, Gregory & Yeo, Anders & Zverovich, Alexey, 2001. "Construction heuristics for the asymmetric TSP," European Journal of Operational Research, Elsevier, vol. 129(3), pages 555-568, March.
- Goldengorin, Boris & Sierksma, Gerard, 2003. "Combinatorial optimization tolerances calculated in linear time," Research Report 03A30, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
- Hoesel, Stan van & Wagelmans, Albert, 1999. "On the complexity of postoptimality analysis of 0/1 programs," Open Access publications from Maastricht University urn:nbn:nl:ui:27-3980, Maastricht University.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Joke Bulthuis).
If references are entirely missing, you can add them using this form.