umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
How To Make a Greedy Heuristic for the Asymmetric Traveling Salesman Problem Competitive
Department of Econometrics and Operations Research, University of Groningen, The Netherlands.
Computer Science Institute, Martin-Luther-University, Halle-Wittenberg, Germany.
2005 (Engelska)Rapport (Refereegranskat)
Abstract [en]

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 and faster than previously reported greedy type algorithms.

Ort, förlag, år, upplaga, sidor
Groningen: University Groningen, The Netherlands , 2005. , s. 16
Serie
SOM (Systems, Organisations and Management) Research Report ; 05A11
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-83146OAI: oai:DiVA.org:umu-83146DiVA, id: diva2:665169
Tillgänglig från: 2013-11-19 Skapad: 2013-11-19 Senast uppdaterad: 2018-06-08

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Jäger, Gerold

Sök vidare i DiVA

Av författaren/redaktören
Jäger, Gerold
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 109 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf