×

Continuous reformulations and heuristics for the Euclidean travelling salesperson problem. (English) Zbl 1189.90127

The authors reformulate the Euclidean TSP with points \(a_i\), \(i=1,2,\dots,n\) in \(\mathbb{R}^m\) by means of a multisource Fermat-Weber location problem. New points \(p_i\) are to be found such that \(f(p):=\sum_{i=1}^n\min_j \|a_i-p_j\|=0\) and \(g(p):=\sum_{i=1}^n \|p_i-p_{i+1}\|\) is a minimum. The function \(f(p)\) is diff-convex. The TSP is relaxed to the problem \(\min_p (f(p)+\lambda g(p))\) for \(\lambda >0\). It is shown that for \(\lambda < 1/2\) every global optimal solution of this problem coincides with an optimal TSP tour. On the other hand, any permutation leads to a local minimum of this objective function. In order to make the problem numerically better tractable, the authors replace \(f(p)\) by \(\bar{f}(p):=1/2\cdot \sum_{i=1}^n\sum_{j=1}^n\|p_i-p_j\|\). This allows them to apply a recently developed clustering algorithm [T. Valkonen and T. Kärkkäinen, Math. Comput. Modelling 52, No. 1–2, 87–106 (2010; Zbl 1201.90126)] which is sped up by heuristics. Numerical experiments on problems from the TSPLIB show quite good results (in particular for TSPs of smaller size). The suboptimal solutions generated by this method may serve as initial solutions for classical improvement methods for the TSP.

MSC:

90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization

Citations:

Zbl 1201.90126

Software:

Haskell; LKH; TSPLIB
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[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. Zbl0904.90165 MR1648194 · Zbl 0904.90165
[2] S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45 (1998) 753-782. Zbl1064.90566 MR1668147 · Zbl 1064.90566 · doi:10.1145/290179.290180
[3] S. Arora, Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program. 97 (2003) 43-69. Zbl1035.90113 MR2004392 · Zbl 1035.90113 · doi:10.1007/s10107-003-0438-y
[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. Zbl1027.68979 MR1731569 · Zbl 1027.68979
[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. Zbl0753.49007 MR1018570 · Zbl 0753.49007 · doi:10.2307/2001800
[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. Zbl0793.49005 MR1215448 · Zbl 0793.49005 · doi:10.1137/0803016
[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. Zbl0758.90071 MR1189076 · Zbl 0758.90071 · doi:10.1287/ijoc.4.4.387
[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. Zbl1089.49040 MR2118415 · Zbl 1089.49040
[10] K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106-130. Zbl0969.90073 MR1781609 · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2
[11] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms I-II. Springer (1993). MR1261420
[12] R. Horst and P.M. Pardolos Eds., Handbook of Global Optimization. Kluwer Academic Publishers (1995). Zbl0805.00009 MR1377081 · Zbl 0805.00009
[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. Zbl0947.90612 MR1458637 · Zbl 0947.90612
[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. Zbl1113.90356 MR1944493 · Zbl 1113.90356
[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). Zbl0199.38101 MR274686 · Zbl 0199.38101 · doi:10.1007/978-3-642-99970-3
[17] S. Peyton Jones, Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press (2003). MR1989220 · Zbl 1067.68041
[18] P. Polak and G. Wolansky, The lazy travelling salesman problem in \(\mathbb{R}^2\). ESAIM: COCV 13 (2007) 538-552. Zbl1153.90014 MR2329175 · Zbl 1153.90014 · doi:10.1051/cocv:2007025
[19] G. Reinelt, TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3 (1991) 376-384. Zbl0775.90293 · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[20] R.T. Rockafellar, Convex Analysis. Princeton University Press (1972). Zbl0193.18401 MR1451876 · Zbl 0193.18401
[21] R.T. Rockafellar and R.J.-B. Wets, Variational Analysis. Springer (1998). Zbl0888.49001 MR1491362 · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[22] T. Valkonen, Convergence of a SOR-Weiszfeld type algorithm for incomplete data sets. Numer. Funct. Anal. Optim. 27 (2006) 931-952. Zbl1112.90059 MR2262549 · Zbl 1112.90059 · doi:10.1080/01630560600791213
[23] T. Valkonen and T. Kärkkäinen, Clustering and the perturbed spatial median. Computer and Mathematical Modelling (submitted).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.