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 : 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/articles/10.1051/cocv:2008056/}
}
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
PY  - 2009
SP  - 895
EP  - 913
VL  - 15
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/cocv:2008056/
DO  - 10.1051/cocv:2008056
LA  - en
ID  - COCV_2009__15_4_895_0
ER  - 
%0 Journal Article
%A Valkonen, Tuomo
%A Kärkkäinen, Tommi
%T Continuous reformulations and heuristics for the euclidean travelling salesperson problem
%J ESAIM: Control, Optimisation and Calculus of Variations
%D 2009
%P 895-913
%V 15
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/cocv:2008056/
%R 10.1051/cocv:2008056
%G en
%F 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/articles/10.1051/cocv:2008056/

[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).

Cité par Sources :