research-article

A feature-based comparison of local search and the christofides algorithm for the travelling salesperson problem

Authors:

Heike TrautmannAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 147 - 160

https://doi.org/10.1145/2460239.2460253

Published: 16 January 2013 Publication History

Get Access

Abstract

Understanding the behaviour of well-known algorithms for classical NP-hard optimisation problems is still a difficult task. With this paper, we contribute to this research direction and carry out a feature based comparison of local search and the well-known Christofides approximation algorithm for the Traveling Salesperson Problem. We use an evolutionary algorithm approach to construct easy and hard instances for the Christofides algorithm, where we measure hardness in terms of approximation ratio. Our results point out important features and lead to hard and easy instances for this famous algorithm. Furthermore, our cross-comparison gives new insights on the complementary benefits of the different approaches.

References

[1]

D. Applegate, W. J. Cook, S. Dash, and A. Rohe. Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14(2):132--143, 2002.

Digital Library

Google Scholar

[2]

S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753--782, 1998.

Digital Library

Google Scholar

[3]

B. Bischl, O. Mersmann, H. Trautmann, and M. Preuß. Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, GECCO '12. ACM, 2012.

Digital Library

Google Scholar

[4]

T. Kötzing, F. Neumann, H. Röglin, and C. Witt. Theoretical analysis of two aco approaches for the traveling salesman problem. Swarm Intelligence, pages 1--21, 2012.

Google Scholar

[5]

S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21(1):498--516, 1973.

Digital Library

Google Scholar

[6]

O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and F. Neumann. Local search and the traveling salesman problem: A feature-based characterization of problem hardness. In Proceedings of the Learning and Intelligent Optimization Conference (LION), LNCS. Springer, 2012. http://arxiv.org/abs/1208.2318.

Digital Library

Google Scholar

[7]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

Google Scholar

[8]

K. Smith-Miles and L. Lopes. Measuring instance difficulty for combinatorial optimization problems. Computers & OR, 39(5):875--889, 2012.

Digital Library

Google Scholar

[9]

K. Smith-Miles, J. I. van Hemert, and X. Y. Lim. Understanding tsp difficulty by learning from evolved instances. In LION, pages 266--280, 2010.

Digital Library

Google Scholar

[10]

A. Sutton and F. Neumann. A parameterized runtime analysis of evolutionary algorithms for the euclidean traveling salesperson problem. In Proceedings of Association of Advancements of Artificial Intelligence. AAAI, 2012.

Google Scholar

[11]

J. I. van Hemert. Evolving combinatorial problem instances that are difficult to solve. Evol. Comput., 14(4):433--462, Dec. 2006.

Digital Library

Google Scholar

[12]

V. V. Vazirani. Approximation algorithms. Springer, 2001.

Digital Library

Google Scholar

[13]

L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown. Satzilla: portfolio-based algorithm selection for sat. J. Artif. Int. Res., 32(1):565--606, June 2008.

Digital Library

Google Scholar

Cited By

View all

Heins JBossek JPohl JSeiler MTrautmann HKerschke P(2023)A study on the effects of normalized TSP features for automated algorithm selectionTheoretical Computer Science10.1016/j.tcs.2022.10.019940:PB(123-145)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.019
Bossek JNeumann ANeumann FWagner M(2022)Evolutionary diversity optimization for combinatorial optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533626(824-842)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533626
Bossek JNeumann FWagner M(2022)Exploring the feature space of TSP instances using quality diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528851(186-194)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528851
Show More Cited By

Index Terms

A feature-based comparison of local search and the christofides algorithm for the travelling salesperson problem
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the Maximum Scatter Traveling Salesperson Problem

We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This "maximum scatter" traveling salesperson problem (TSP) is closely related to the bottleneck TSP ...
Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness
LION 6: Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219

With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem TSP. Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical ...
Heuristics for K-Independent Average Traveling Salesperson Problem
Multi-disciplinary Trends in Artificial Intelligence
Abstract
This paper deals with heuristic solution of K-independent average traveling salesperson (KIATSP) problem which is a recent extension of the well-known traveling salesperson problem (TSP). This problem seeks finding of K mutually independent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
230
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Heins JBossek JPohl JSeiler MTrautmann HKerschke P(2023)A study on the effects of normalized TSP features for automated algorithm selectionTheoretical Computer Science10.1016/j.tcs.2022.10.019940:PB(123-145)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.019
Bossek JNeumann ANeumann FWagner M(2022)Evolutionary diversity optimization for combinatorial optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533626(824-842)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533626
Bossek JNeumann FWagner M(2022)Exploring the feature space of TSP instances using quality diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528851(186-194)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528851
Buzdalov M(2022)The $(1+(\lambda,\lambda))$ Genetic Algorithm on the Vertex Cover Problem: Crossover Helps Leaving Plateaus2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870224(1-10)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870224
Gao WNallaperuma SNeumann F(2021)Feature-Based Diversity Optimization for Problem Instance ClassificationEvolutionary Computation10.1162/evco_a_0027429:1(107-128)Online publication date: Mar-2021
https://doi.org/10.1162/evco_a_00274
Heins JBossek JPohl JSeiler MTrautmann HKerschke PFinck SHellwig MOliveto P(2021)On the potential of normalized TSP features for automated algorithm selectionProceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3450218.3477308(1-15)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3450218.3477308
Neumann AAlexander BNeumann F(2020)Evolutionary Image Transition and Painting Using Random WalksEvolutionary Computation10.1162/evco_a_0027028:4(643-675)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1162/evco_a_00270
Kärkkäinen TRasku J(2020)Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing ProblemsComputation and Big Data for Transport10.1007/978-3-030-37752-6_6(77-102)Online publication date: 29-Feb-2020
https://doi.org/10.1007/978-3-030-37752-6_6
Neumann AGao WWagner MNeumann FAuger AStützle T(2019)Evolutionary diversity optimization using multi-objective indicatorsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321796(837-845)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321796
Kerschke PHoos HNeumann FTrautmann H(2018)Automated Algorithm Selection: Survey and PerspectivesEvolutionary Computation10.1162/evco_a_00242(1-47)Online publication date: 26-Nov-2018
https://doi.org/10.1162/evco_a_00242
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the Maximum Scatter Traveling Salesperson Problem

Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness

Heuristics for K-Independent Average Traveling Salesperson Problem