Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2014 | OriginalPaper | Chapter

Computing an Upper Bound for the Longest Edge in an Optimal TSP-Solution

Authors : Hans Achatz, Peter Kleinschmidt

Published in: Operations Research Proceedings 2013

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A solution of the traveling salesman problem (TSP) with n nodes consists of n edges which form a shortest tour. In our approach we compute an upper bound u for the longest edge which could be in an optimal solution. This means that every edge longer than this bound cannot be in an optimal solution. The quantity u can be computed in polynomial time. We have applied our approach to different problems of the TSPLIB (library of sample instances for the TSP). Our bound does not necessarily improve the fastest TSP-algorithms. However, the reduction of the number of edges might be useful for certain instances.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Electricity Storage Systems and Their Allocation in the German Power System
Literature
1.
Achatz, H., Kleinschmidt, P., & Paparrizos, K. (1991). A dual forest algorithm for the assignment problem. In P. Gritzmann, B. Sturmfels & V. Klee (Eds.), Applied geometry and discrete mathematics. The Victor Klee festschrift (pp. 1–10). Providence, R.I.: AMS (DIMACS’4).
2.
Achatz, H. (1999). Sensitivity analysis of the bipartite weighted matching problem. In P. Kall (Ed.), Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research, Zürich (pp. 135–141). Aug31–Sept 3, 1998. Berlin: Springer.
3.
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2007). The traveling salesman problem. A computational story. Princeton, NJ: Princeton University Press (Princeton series in applied mathematics).
4.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21, 498–516.CrossRef
5.
Reinelt, G. (1991). TSPLIB—a traveling salesman problem library. ORSA Journal on Computing, 3, 376–384.CrossRef
Metadata
Title
Computing an Upper Bound for the Longest Edge in an Optimal TSP-Solution
Authors
Hans Achatz
Peter Kleinschmidt
Copyright Year
2014
Book
Operations Research Proceedings 2013

Print ISBN: 978-3-319-07000-1

Electronic ISBN: 978-3-319-07001-8

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-07001-8_1