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