# Continuous reformulations and heuristics for the Euclidean travelling salesperson problem

Tuomo Valkonen; Tommi Kärkkäinen

ESAIM: Control, Optimisation and Calculus of Variations (2008)

- Volume: 15, Issue: 4, page 895-913
- ISSN: 1292-8119

## Access Full Article

top## Abstract

top## How to cite

topValkonen, Tuomo, and Kärkkäinen, Tommi. "Continuous reformulations and heuristics for the Euclidean travelling salesperson problem." ESAIM: Control, Optimisation and Calculus of Variations 15.4 (2008): 895-913. <http://eudml.org/doc/90943>.

@article{Valkonen2008,

abstract = {
We consider continuous reformulations of the Euclidean travelling
salesperson problem (TSP), based on certain clustering problem
formulations. These reformulations allow us to apply a generalisation
with perturbations of the Weiszfeld algorithm in an attempt to
find local approximate solutions to the Euclidean TSP.
},

author = {Valkonen, Tuomo, Kärkkäinen, Tommi},

journal = {ESAIM: Control, Optimisation and Calculus of Variations},

keywords = {Euclidean TSP; clustering;
diff-convex; Weiszfeld algorithm; diff-convex},

language = {eng},

month = {8},

number = {4},

pages = {895-913},

publisher = {EDP Sciences},

title = {Continuous reformulations and heuristics for the Euclidean travelling salesperson problem},

url = {http://eudml.org/doc/90943},

volume = {15},

year = {2008},

}

TY - JOUR

AU - Valkonen, Tuomo

AU - Kärkkäinen, Tommi

TI - Continuous reformulations and heuristics for the Euclidean travelling salesperson problem

JO - ESAIM: Control, Optimisation and Calculus of Variations

DA - 2008/8//

PB - EDP Sciences

VL - 15

IS - 4

SP - 895

EP - 913

AB -
We consider continuous reformulations of the Euclidean travelling
salesperson problem (TSP), based on certain clustering problem
formulations. These reformulations allow us to apply a generalisation
with perturbations of the Weiszfeld algorithm in an attempt to
find local approximate solutions to the Euclidean TSP.

LA - eng

KW - Euclidean TSP; clustering;
diff-convex; Weiszfeld algorithm; diff-convex

UR - http://eudml.org/doc/90943

ER -

## References

top- D. Applegate, R. Bixby, V. Chavátal and W. Cook, On the solution of traveling salesman problems, in Doc. Math., Extra volume ICM 1998III, Berlin (1998) 645–656. Zbl0904.90165
- S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM45 (1998) 753–782. Zbl1064.90566
- S. Arora, Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program.97 (2003) 43–69. Zbl1035.90113
- S. Arora, P. Raghavan and S. Rao, Approximation schemes for Euclidean k-medians and related problems, in ACM Symposium on Theory of Computing (1998) 106–113. Zbl1027.68979
- H. Attouch and R.J.-B. Wets, Quantitative stability of variational systems: I. The epigraphical distance. Trans. Amer. Math. Soc.328 (1991) 695–729. Zbl0753.49007
- H. Attouch and R.J.-B. Wets, Quantitative stability of variational systems: II. A framework for nonlinear conditioning. SIAM J. Optim.3 (1993) 359–381. Zbl0793.49005
- S. Äyrämö, Knowledge Mining Using Robust Clustering. Jyväskylä Studies in Computing63. University of Jyväskylä, Ph.D. thesis (2006).
- J.J. Bentley, Fast algorithms for geometric traveling salesman problems. ORSA J. Comput.4 (1992) 887–411. Zbl0758.90071
- G. Buttazzo and E. Stepanov, Minimization problems for average distance functionals, in Calculus of Variations: Topics from the Mathematical Heritage of Ennio De Giorgi, D. Pallara Ed., Quaderni di Matematica, Seconda Università di Napoli, Caserta14 (2004) 47–83. Zbl1089.49040
- K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res.126 (2000) 106–130. Zbl0969.90073
- J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms I-II. Springer (1993). Zbl0795.49002
- R. Horst and P.M. Pardolos Eds., Handbook of Global Optimization. Kluwer Academic Publishers (1995).
- D.S. Johnson and L.A. McGeoch, The traveling salesman problem: A case study in local optimization, in Local Search in Combinatorial Optimization, E. Aarts and J. Lenstra Eds., John Wiley and Sons (1997) 215–310. Zbl0947.90612
- D.S. Johnson and L.A. McGeoch, Experimental analysis of heuristics for the STSP, in The Traveling Salesman Problem and Its Variations, G. Gutin and A.P. Punnen Eds., Springer (2002) 369–443. Zbl1113.90356
- J.D. Litke, An improved solution to the traveling salesman problem with thousands of nodes. Commun. ACM27 (1984) 1227–1236.
- D.S. Mitrinović, Analytic Inequalities. Springer-Verlag (1970). Zbl0199.38101
- S. Peyton Jones, Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press (2003). Zbl1067.68041
- P. Polak and G. Wolansky, The lazy travelling salesman problem in ${\mathbb{R}}^{2}$. ESAIM: COCV13 (2007) 538–552. Zbl1153.90014
- G. Reinelt, TSPLIB – A traveling salesman problem library. ORSA J. Comput.3 (1991) 376–384. Zbl0775.90293
- R.T. Rockafellar, Convex Analysis. Princeton University Press (1972). Zbl0224.49003
- R.T. Rockafellar and R.J.-B. Wets, Variational Analysis. Springer (1998).
- T. Valkonen, Convergence of a SOR-Weiszfeld type algorithm for incomplete data sets. Numer. Funct. Anal. Optim.27 (2006) 931–952. Zbl1112.90059
- T. Valkonen and T. Kärkkäinen, Clustering and the perturbed spatial median. Computer and Mathematical Modelling (submitted). Zbl1201.90126

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.