Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood

References

• Aarts E, Lenstra JK, eds. (1997) Local Search in Combinatorial Optimization, 1st ed. (John Wiley & Sons, Inc., New York).Google Scholar
• Applegate D, Cook W, Rohe A (2003) Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1):82–92.Link, Google Scholar
• Applegate D, Bixby R, Chvatál V, Cook W (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Basu S (2012) Tabu search implementation on traveling salesman problem and its variations: A literature survey. Amer. J. Oper. Res. 2:163–173.Google Scholar
• Chandra B, Karloff H, Tovey C (1999) New results on the old k-OPT algorithm for the traveling salesman problem. SIAM J. Comput. 28(6):1998–2029.Crossref, Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd ed. (MIT Press, Cambridge, MA).Google Scholar
• Croes G (1958) A method for solving traveling-salesman problems. Oper. Res. 6(6):791–812.Link, Google Scholar
• Englert M, Roglin H, Vocking B (2014) Worst case and probabilistic analysis of the 2-OPT algorithm for the TSP. Algorithmica 68(1):190–264.Crossref, Google Scholar
• Flood MM (1956) The traveling-salesman problem. Oper. Res. 4(1):61–75.Link, Google Scholar
• Gutin G, Punnen A, eds. (2007) The Traveling Salesman Problem and Its Variations, Combinatorial Optimization, vol. 12 (Springer Science+Business Media, New York).Crossref, Google Scholar
• Hall P (1927) The distribution of means for samples of size n drawn from a population in which the variate takes values between 0 and 1, all such values being equally probable. Biometrika 19(3–4):240–245.Crossref, Google Scholar
• Hougardy S, Zhong X (2001) Hard to solve instances of the Euclidean traveling salesman problem. Math. Program. Comput. 13:51–74.Crossref, Google Scholar
• Ilhan I, Gokmen G (2022) A list-based simulated annealing algorithm with crossover operator for the traveling salesman problem. Neural Comput. Appl. 34:7627–7652.Crossref, Google Scholar
• Irwin J (1927) On the frequency distribution of the means of samples from a population having any law of frequency with finite moments, with special reference to Pearson’s type II. Biometrika 19(3–4):225–239.Crossref, Google Scholar
• Kern W (1989) A probabilistic analysis of the switching algorithm for the Euclidean TSP. Math. Program. 44:213–219.Crossref, Google Scholar
• Lancia G, Vidoni P (2020) Finding the largest triangle in a graph in expected quadratic time. Eur. J. Oper. Res. 286(2):458–467.Crossref, Google Scholar
• Lancia G, Vidoni P (2024a) Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time. Preprint, submitted March 28, https://arxiv.org/abs/2403.19878.Google Scholar
• Lancia G, Vidoni P (2024b) Average case sub-quadratic exact and heuristic procedures for the traveling salesman 2-OPT neighborhood. http://dx.doi.org/10.1287/ijoc.2023.0169.cd, https://github.com/INFORMSJoC/2023.0169.Google Scholar
• Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB, eds. (1991) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Lin S (1965) Computer solutions of the traveling salesman problem. Bell System Tech. J. 44(10):2245–2269.Crossref, Google Scholar
• Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2):498–516.Link, Google Scholar
• Lodi A, Punnen AP (2007) TSP software. Gutin G, Punnen AP, eds. The Traveling Salesman Problem and Its Variations, Combinatorial Optimization, vol. 12 (Springer, Boston), 737–749.Crossref, Google Scholar
• Nagata Y, Kobayashi S (2012) A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J. Comput. 25(2):346–363.Link, Google Scholar
• Papadimitriou C, Steiglitz K (1982) Combinatorial Optimization: Algorithms and Complexity (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Potvin JY (1996) Genetic algorithms for the traveling salesman problem. Ann. Oper. Res. 63:339–370.Crossref, Google Scholar
• Reinelt G (1991) TSPLIB - A traveling salesman problem library. ORSA J. Comput. 3:376–384.Link, Google Scholar
• Slootbeek JJA (2017) Average-case analysis of the 2-OPT heuristic for the TSP. Unpublished master’s thesis, Applied Mathematics, University of Twente, Enschede, Netherlands, 1–45.Google Scholar