umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP
Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
Computer Science Institute, University of Halle-Wittenberg, Germany.
Computer Science Institute, University of Halle-Wittenberg, Germany.
2006 (English)In: Proceedings of 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006) / [ed] T. Erlebach, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2006, 86-97 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we improve the quality of a recently suggested class of construction heuristics for the Asymmetric Traveling Salesman Problem (ATSP), namely the Contract-or-Patch heuristic. Our improvement is based on replacing the selection of each path to be contracted after deleting a heaviest arc from each short cycle in an Optimal Assignment Problem Solution (OAPS) by contracting a single arc from a short cycle in an OAPS with the largest upper tolerance with respect to one of the relaxed ATSP. The improved algorithm produces higher-quality tours than all previous COP versions and is clearly outperforming all other construction heuristics on robustness.

Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2006. 86-97 p.
Series
Lecture Notes in Computer Science, Volume 4235
Keyword [en]
Traveling Salesman Problem, Tolerances, Construction Heuristics
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84356OAI: oai:DiVA.org:umu-84356DiVA: diva2:683175
Conference
3rd Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006)
Available from: 2014-01-02 Created: 2014-01-02 Last updated: 2014-03-25Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 31 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf