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
Improving the Performance of Greedy Heuristics for TSPs Using Tolerances
P&QM Area, IIM Ahmedabad, India.
Faculty to Economics Sciences, University of Groningen, the Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
Department of Computer Science, Royal Holloway University of London, UK and Department of Computer Science, University of Haifa, Israel.
Computer Science Institute, University of Halle-Wittenberg, Germany.
2007 (Engelska)Ingår i: Communications in Dependability and Quality Management, Vol. 10, nr 1, s. 52-70Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper we introduce three greedy algorithms for the traveling salesman problem. These algorithms are unique in that they use arc tolerances, rather than arc weights, to decide whether or not to include an arx in a solution. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. Along with other papers dealing with the Assignment Problem, this paper indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach. We recommend one of our algorithms as a significantly better alternative to the weight-based greedy, which is often used to produce initial TSP tours.

Ort, förlag, år, upplaga, sidor
Germa and SOM Research Institute, University of Groningen, the Netherlands , 2007. Vol. 10, nr 1, s. 52-70
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-82913OAI: oai:DiVA.org:umu-82913DiVA, id: diva2:663913
Tillgänglig från: 2013-11-13 Skapad: 2013-11-13 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: 104 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