Continuous reformulations and heuristics for the Euclidean travelling salesperson problem

Tuomo Valkonen; Tommi Kärkkäinen

ESAIM: Control, Optimisation and Calculus of Variations (2008)

  • Volume: 15, Issue: 4, page 895-913
  • ISSN: 1292-8119

Abstract

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

How to cite

top

Valkonen, Tuomo, and Kärkkäinen, Tommi. "Continuous reformulations and heuristics for the Euclidean travelling salesperson problem." ESAIM: Control, Optimisation and Calculus of Variations 15.4 (2008): 895-913. <http://eudml.org/doc/90943>.

@article{Valkonen2008,
abstract = { 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. },
author = {Valkonen, Tuomo, Kärkkäinen, Tommi},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {Euclidean TSP; clustering; diff-convex; Weiszfeld algorithm; diff-convex},
language = {eng},
month = {8},
number = {4},
pages = {895-913},
publisher = {EDP Sciences},
title = {Continuous reformulations and heuristics for the Euclidean travelling salesperson problem},
url = {http://eudml.org/doc/90943},
volume = {15},
year = {2008},
}

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
DA - 2008/8//
PB - EDP Sciences
VL - 15
IS - 4
SP - 895
EP - 913
AB - 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.
LA - eng
KW - Euclidean TSP; clustering; diff-convex; Weiszfeld algorithm; diff-convex
UR - http://eudml.org/doc/90943
ER -

References

top
  1. D. Applegate, R. Bixby, V. Chavátal and W. Cook, On the solution of traveling salesman problems, in Doc. Math., Extra volume ICM 1998III, Berlin (1998) 645–656.  
  2. S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM45 (1998) 753–782.  
  3. S. Arora, Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program.97 (2003) 43–69.  
  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.  
  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.  
  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.  
  7. S. Äyrämö, Knowledge Mining Using Robust Clustering. Jyväskylä Studies in Computing63. 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.  
  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, Caserta14 (2004) 47–83.  
  10. K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res.126 (2000) 106–130.  
  11. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms I-II. Springer (1993).  
  12. R. Horst and P.M. Pardolos Eds., Handbook of Global Optimization. Kluwer Academic Publishers (1995).  
  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.  
  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.  
  15. J.D. Litke, An improved solution to the traveling salesman problem with thousands of nodes. Commun. ACM27 (1984) 1227–1236.  
  16. D.S. Mitrinović, Analytic Inequalities. Springer-Verlag (1970).  
  17. S. Peyton Jones, Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press (2003).  
  18. P. Polak and G. Wolansky, The lazy travelling salesman problem in ℝ 2 . ESAIM: COCV13 (2007) 538–552.  
  19. G. Reinelt, TSPLIB – A traveling salesman problem library. ORSA J. Comput.3 (1991) 376–384.  
  20. R.T. Rockafellar, Convex Analysis. Princeton University Press (1972).  
  21. R.T. Rockafellar and R.J.-B. Wets, Variational Analysis. Springer (1998).  
  22. T. Valkonen, Convergence of a SOR-Weiszfeld type algorithm for incomplete data sets. Numer. Funct. Anal. Optim.27 (2006) 931–952.  
  23. T. Valkonen and T. Kärkkäinen, Clustering and the perturbed spatial median. Computer and Mathematical Modelling (submitted).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.