Danilo Sanches
Renato Tinós
ABSTRACT
The best known exact solver for generating provably optimal solutions to the Traveling Salesman Problem (TSP) is the Concorde algorithm. Concorde uses a branch and bound search strategy, as well as cutting planes to reduce the search space. The first step in using Concorde is to obtain a good initial solution. A good solution can be generated using a heuristic solver outside of Concorde, or Concorde can generate its own initial solution using the Chained Lin Kernighan (LK) algorithm. In this paper, we speed up Concorde by improving the initial solutions produced by Chained LK using Partition Crossover. Partition Crossover is a powerful deterministic recombination operator that is able to tunnel between local optima. In every instance we examined, the addition of recombination resulted in an average speed-up of Concorde, and in the majority of cases, the difference in the runtime costs was statistically significant.
- F. Ahammed and P. Moscato. Evolving l-systems as an intelligent design approach to find classes of difficult-to-solve traveling salesman problem instances. In Applications of Evolutionary Computation: EvoApplications, pages 1--11. Springer, 2011. Google Scholar
Digital Library
- D. Applegate, W. Cook, and A. Rohe. Chained lin-kernighan for large traveling salesman problems. INFORMS J. on Computing, 15(1):82--92, Jan. 2003. Google ScholarDigital Library
- D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook. Concorde-03.12.19, 2003. http://www.math.uwaterloo.ca/tsp/data/index.html.Google Scholar
- W. Cook and P. Seymour. Tour merging via branch-decomposition. INFORMS Journal on Computing, 15(3):233--248, 2003. Google ScholarDigital Library
- W.J. Cook. TSP test data, accessed October 24, 2016. http://www.math.uwaterloo.ca/tsp/data/index.html.Google Scholar
- D. Hains, D. Whitley, and A. Howe. Improving lin-kernighan-helsgaun with crossover on clustered instances of the TSP. In Parallel Problem Solving from Nature, PPSN'12, pages 388--397, 2012. Springer. Google ScholarDigital Library
- K. Helsgaun. General k-opt submoves for the lin-kernighan tsp heuristic. Mathematical Programming Computation, 1(2):119--163, 2009.Google ScholarCross Ref
- S. Hougardy and R. T. Schroeder. Edge elimination in tsp instances. In D. Kratsch and I. Todinca, editors, Graph-Theoretic Concepts in Computer Science, pages 275--286. Springer, 2014.Google ScholarCross Ref
- S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res., 21(2):498--516, Apr. 1973. Google ScholarDigital Library
- O. Martin, S. Otto, and E. Felten. Large-step markov chains for the tsp incorporating local search heuristics. Operations Research Letters, 11:219--224, 1992. Google ScholarDigital Library
- A. Möbius, B. Freisleben, P. Merz, and M. Schreiber. Combinatorial optimization by iterative partial transcription. Physycal Review E, 59(4):4667--4674, 1999.Google ScholarCross Ref
- G. Ochoa and N. Veerapen. Additional dimensions to the study of funnels in combinatorial landscapes. In Genetic and Evolutionary Computation Conference 2016, GECCO '16, pages 373--380, 2016. ACM. Google ScholarDigital Library
- N. Radcliffe and P. Surry. Fitness variance of formae and performance predictions. In D. Whitley and M. Vose, editors, Foundations of Genetic Algorithms 3, pages 51--72. Morgan Kaufmann, 1995.Google Scholar
- G. Reinelt. TSPLIB 95, accessed October 24, 2016. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.Google Scholar
- D. Sanches, D. Whitley, and R. Tinós. Building a better heuristic for the traveling salesman problem: Combining edge assembly crossover and partition crossover. In Genetic and Evolutionary Computation Conference GECCO, 2017. ACM. Google ScholarDigital Library
- R. Tinos, D. Whitley, and F. Chicano. Partition crossover for pseudo-boolean optimization. In Foundations of genetic algorithms, (FOGA-15), pages 137--149, 2015. ACM. Google ScholarDigital Library
- R. Tinós, D. Whitley, and G. Ochoa. Generalized asymmetric partition crossover (GAPX) for the asymmetric tsp. In Genetic and Evolutionary Computation Conference, GECCO '14, pages 501--508, 2014. ACM. Google ScholarDigital Library
- D. Whitley, D. Hains, and A. Howe. Tunneling between optima: Partition crossover for the traveling salesman problem. In Genetic and Evolutionary Computation Conference, GECCO '09, pages 915--922, 2009. ACM. Google ScholarDigital Library
- D. Whitley, D. Hains, and A. Howe. A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover. In Parallel Problem Solving from Nature, PPSN'10, pages 566--575, 2010. Springer. Google ScholarDigital Library
Index Terms
- Improving an exact solver for the traveling salesman problem using partition crossover
Recommendations
Building a better heuristic for the traveling salesman problem: combining edge assembly crossover and partition crossover
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceA genetic algorithm using Edge Assemble Crossover (EAX) is one of the best heuristic solvers for large instances of the Traveling Salesman Problem. We propose using Partition Crossover to recombine solutions produced by EAX. Partition Crossover is a ...
Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem
Ejection chain methods, which include the classical Lin-Kernighan LK procedure and the Stem-and-Cycle S&C reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems STSP. Although ...
Exact Heuristic Algorithm for Traveling Salesman Problem
ICYCS '08: Proceedings of the 2008 The 9th International Conference for Young Computer ScientistsNatural properties of stochastic searching strategies and operations in metaheuristic algorithms have important influence on convergence performance of various metaheuristic algorithms. Through similarity analysis to two kinds of metaheuristic ...
Comments