Geodesic
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.

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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

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

[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. | Zbl | MR | mathdoc-id

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

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

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

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

Cité par Sources :