Continuous reformulations and heuristics for the euclidean travelling salesperson problem

Valkonen, Tuomo; Kärkkäinen, Tommi

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.

Classification : 90C26, 90C59, 90C27
Mots clés : euclidean TSP, clustering, diff-convex, Weiszfeld algorithm

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

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

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

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