Continuous reformulations and heuristics for the euclidean travelling salesperson problem
ESAIM: Control, Optimisation and Calculus of Variations, Tome 15 (2009) no. 4, pp. 895-913.

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.

DOI : https://doi.org/10.1051/cocv:2008056
Classification : 90C26,  90C59,  90C27
Mots clés : euclidean TSP, clustering, diff-convex, Weiszfeld algorithm
@article{COCV_2009__15_4_895_0,
author = {Valkonen, Tuomo and K\"arkk\"ainen, Tommi},
title = {Continuous reformulations and heuristics for the euclidean travelling salesperson problem},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
pages = {895--913},
publisher = {EDP-Sciences},
volume = {15},
number = {4},
year = {2009},
doi = {10.1051/cocv:2008056},
mrnumber = {2567251},
language = {en},
url = {http://www.numdam.org/item/COCV_2009__15_4_895_0/}
}
Valkonen, Tuomo; Kärkkäinen, Tommi. Continuous reformulations and heuristics for the euclidean travelling salesperson problem. ESAIM: Control, Optimisation and Calculus of Variations, Tome 15 (2009) no. 4, pp. 895-913. doi : 10.1051/cocv:2008056. http://www.numdam.org/item/COCV_2009__15_4_895_0/

[1] D. Applegate, R. Bixby, V. Chavátal and W. Cook, On the solution of traveling salesman problems, in Doc. Math., Extra volume ICM 1998 III, Berlin (1998) 645-656. | MR 1648194 | Zbl 0904.90165

[2] S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45 (1998) 753-782. | MR 1668147 | Zbl 1064.90566

[3] S. Arora, Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program. 97 (2003) 43-69. | MR 2004392 | Zbl 1035.90113

[4] 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. | MR 1731569 | Zbl 1027.68979

[5] H. Attouch and R.J.-B. Wets, Quantitative stability of variational systems: I. The epigraphical distance. Trans. Amer. Math. Soc. 328 (1991) 695-729. | MR 1018570 | Zbl 0753.49007

[6] 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. | MR 1215448 | Zbl 0793.49005

[7] S. Äyrämö, Knowledge Mining Using Robust Clustering. Jyväskylä Studies in Computing 63. University of Jyväskylä, Ph.D. thesis (2006).

[8] J.J. Bentley, Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. 4 (1992) 887-411. | MR 1189076 | Zbl 0758.90071

[9] 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, Caserta 14 (2004) 47-83. | MR 2118415 | Zbl 1089.49040

[10] K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106-130. | MR 1781609 | Zbl 0969.90073

[11] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms I-II. Springer (1993). | MR 1261420

[12] R. Horst and P.M. Pardolos Eds., Handbook of Global Optimization. Kluwer Academic Publishers (1995). | MR 1377081 | Zbl 0805.00009

[13] 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. | MR 1458637 | Zbl 0947.90612

[14] 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. | MR 1944493 | Zbl 1113.90356

[15] J.D. Litke, An improved solution to the traveling salesman problem with thousands of nodes. Commun. ACM 27 (1984) 1227-1236.

[16] D.S. Mitrinović, Analytic Inequalities. Springer-Verlag (1970). | MR 274686 | Zbl 0199.38101

[17] S. Peyton Jones, Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press (2003). | MR 1989220

[18] P. Polak and G. Wolansky, The lazy travelling salesman problem in ${ℝ}^{2}$. ESAIM: COCV 13 (2007) 538-552. | Numdam | MR 2329175 | Zbl 1153.90014

[19] G. Reinelt, TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376-384. | Zbl 0775.90293

[20] R.T. Rockafellar, Convex Analysis. Princeton University Press (1972). | MR 1451876 | Zbl 0193.18401

[21] R.T. Rockafellar and R.J.-B. Wets, Variational Analysis. Springer (1998). | MR 1491362 | Zbl 0888.49001

[22] T. Valkonen, Convergence of a SOR-Weiszfeld type algorithm for incomplete data sets. Numer. Funct. Anal. Optim. 27 (2006) 931-952. | MR 2262549 | Zbl 1112.90059

[23] T. Valkonen and T. Kärkkäinen, Clustering and the perturbed spatial median. Computer and Mathematical Modelling (submitted).