Abstract
The Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem, for which a large variety of evolutionary algorithms are known. However, these heuristics fail to find solutions for large instances due to time and memory constraints. Here, we discuss a set of edge fixing heuristics to transform large TSP problems into smaller problems, which can be solved easily with existing algorithms. We argue, that after expanding a reduced tour back to the original instance, the result is nearly as good as applying the used solver to the original problem instance, but requiring significantly less time to be achieved. We claim that with these reductions, very large TSP instances can be tackled with current state-of-the-art evolutionary local search heuristics.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: On the Solution of Traveling Salesman Problems. Documenta Mathematica Extra Volume ICM III, 645–656 (1998)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Implementing the Dantzig-Fulkerson-Johnson Algorithm for large Traveling Salesman Problems. Mathematical Programming 97, 91–153 (2003)
Lin, S., Kernighan, B.W.: An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21(2), 498–516 (1973)
Johnson, D.S.: Local optimization and the traveling salesman problem. In: Paterson, M.S. (ed.) Automata, Languages and Programming. LNCS, vol. 443, pp. 446–461. Springer, Heidelberg (1990)
Moscato, P., Norman, M.G.: A Memetic Approach for the Traveling Salesman Problem Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems. In: Valero, M., Onate, E., Jane, M., Larriba, J.L., Suarez, B. (eds.) Parallel Computing and Transputer Applications, pp. 177–186. IOS Press, Amsterdam (1992)
Merz, P., Freisleben, B.: Memetic Algorithms for the Traveling Salesman Problem. Complex Systems 13(4), 297–345 (2001)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Concorde TSP Solver (2005), http://www.tsp.gatech.edu/concorde/
Cook, W., Seymour, P.: Tour Merging via Branch-Decomposition. INFORMS Journal on Computing 15(3), 233–248 (2003)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Finding Cuts in the TSP (a Preliminary Report). Technical Report 95-05, Rutgers University, Piscataway NJ (1995)
Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research 126(1), 106–130 (2000)
Cook, W.J.: Log of SW24978 Computation (2004), http://www.tsp.gatech.edu/world/swlog.html
Arenas, M.G., Collet, P., Eiben, A.E., Jelasity, M., Merelo, J.J., Paechter, B., Schoenauer, M., Preuß, M.: A Framework for Distributed Evolutionary Algorithms. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) Parallel Problem Solving from Nature - PPSN VII. LNCS, vol. 2439, pp. 665–675. Springer, Heidelberg (2002)
Fischer, T., Merz, P.: Embedding a Chained Lin-Kernighan Algorithm into a Distributed Algorithm. In: MIC’2005 – 6th Metaheuristics International Conference, Vienna, Austria (2005)
Cook, W.J.: World Traveling Salesman Problem (2005), http://www.tsp.gatech.edu/world/
Walshaw, C.: Multilevel Refinement for Combinatorial Optimisation Problems. Annals of Operations Research 131, 325–372 (2004)
Walshaw, C.: A Multilevel Approach to the Travelling Salesman Problem. Operations Research 50(5), 862–877 (2002)
Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for Large Traveling Salesman Problems. INFORMS Journal on Computing 15(1), 82–92 (2003)
Kruskal, J.B.: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, vol. 7, pp. 48–50 (1956)
Friedman, J.H., Baskett, F., Shustek, L.H.: An Algorithm for Finding Nearest Neighbors. In: IEEE Transactions on Computers (TOC) C-24, pp. 1000–1006 (1975)
Sproull, R.F.: Refinements to Nearest-Neighbor Searching in k-Dimensional Trees. Algorithmica 6(4), 579–589 (1991)
Reinelt, G.: TSPLIB — a traveling salesman problem library. ORSA Journal on Computing 3(4), 376–384 (1991), http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Cook, W.J.: National Traveling Salesman Problems (2005), http://www.tsp.gatech.edu/world/countries.html
Johnson, D.S., McGeoch, L.A.: Experimental Analysis of Heuristics for the STSP, pp. 369–443. Kluwer Academic Publishers, Dordrecht (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Fischer, T., Merz, P. (2007). Reducing the Size of Traveling Salesman Problem Instances by Fixing Edges. In: Cotta, C., van Hemert, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2007. Lecture Notes in Computer Science, vol 4446. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71615-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-71615-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71614-3
Online ISBN: 978-3-540-71615-0
eBook Packages: Computer ScienceComputer Science (R0)