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.
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] On the solution of traveling salesman problems, in Doc. Math., Extra volume ICM 1998 III, Berlin (1998) 645-656. | MR | Zbl
, , and ,[2] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45 (1998) 753-782. | MR | Zbl
,[3] Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program. 97 (2003) 43-69. | MR | Zbl
,[4] Approximation schemes for Euclidean -medians and related problems, in ACM Symposium on Theory of Computing (1998) 106-113. | MR | Zbl
, and ,[5] Quantitative stability of variational systems: I. The epigraphical distance. Trans. Amer. Math. Soc. 328 (1991) 695-729. | MR | Zbl
and ,[6] Quantitative stability of variational systems: II. A framework for nonlinear conditioning. SIAM J. Optim. 3 (1993) 359-381. | MR | Zbl
and ,[7] Knowledge Mining Using Robust Clustering. Jyväskylä Studies in Computing 63. University of Jyväskylä, Ph.D. thesis (2006).
,[8] Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. 4 (1992) 887-411. | MR | Zbl
,[9] 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
and ,[10] An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106-130. | MR | Zbl
,[11] Convex analysis and minimization algorithms I-II. Springer (1993). | MR
and ,[12] Handbook of Global Optimization. Kluwer Academic Publishers (1995). | MR | Zbl
and Eds.,[13] 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
and ,[14] 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
and ,[15] An improved solution to the traveling salesman problem with thousands of nodes. Commun. ACM 27 (1984) 1227-1236.
,[16] Analytic Inequalities. Springer-Verlag (1970). | MR | Zbl
,[17] Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press (2003). | MR
,[18] The lazy travelling salesman problem in . ESAIM: COCV 13 (2007) 538-552. | Numdam | MR | Zbl
and ,[19] TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376-384. | Zbl
,[20] Convex Analysis. Princeton University Press (1972). | MR | Zbl
,[21] Variational Analysis. Springer (1998). | MR | Zbl
and ,[22] Convergence of a SOR-Weiszfeld type algorithm for incomplete data sets. Numer. Funct. Anal. Optim. 27 (2006) 931-952. | MR | Zbl
,[23] Clustering and the perturbed spatial median. Computer and Mathematical Modelling (submitted).
and ,Cité par Sources :