[{"type":"conference","publication":"Learning and Intelligent Optimization","abstract":[{"text":"Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms.","lang":"eng"}],"editor":[{"last_name":"Festa","full_name":"Festa, P","first_name":"P"},{"first_name":"M","last_name":"Sellmann","full_name":"Sellmann, M"},{"last_name":"Vanschoren","full_name":"Vanschoren, J","first_name":"J"}],"status":"public","_id":"46365","user_id":"15504","series_title":"Lecture Notes in Computer Science","department":[{"_id":"34"},{"_id":"819"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-319-50348-6"]},"place":"Ischia, Italy","year":"2016","citation":{"ieee":"J. Bossek and H. Trautmann, “Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers,” in <i>Learning and Intelligent Optimization</i>, 2016, vol. 10079, pp. 48–59, doi: <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>.","chicago":"Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers.” In <i>Learning and Intelligent Optimization</i>, edited by P Festa, M Sellmann, and J Vanschoren, 10079:48–59. Lecture Notes in Computer Science. Ischia, Italy: Springer International Publishing, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">https://doi.org/10.1007/978-3-319-50349-3_4</a>.","ama":"Bossek J, Trautmann H. Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers. In: Festa P, Sellmann M, Vanschoren J, eds. <i>Learning and Intelligent Optimization</i>. Vol 10079. Lecture Notes in Computer Science. Springer International Publishing; 2016:48–59. doi:<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>","apa":"Bossek, J., &#38; Trautmann, H. (2016). Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers. In P. Festa, M. Sellmann, &#38; J. Vanschoren (Eds.), <i>Learning and Intelligent Optimization</i> (Vol. 10079, pp. 48–59). Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">https://doi.org/10.1007/978-3-319-50349-3_4</a>","short":"J. Bossek, H. Trautmann, in: P. Festa, M. Sellmann, J. Vanschoren (Eds.), Learning and Intelligent Optimization, Springer International Publishing, Ischia, Italy, 2016, pp. 48–59.","bibtex":"@inproceedings{Bossek_Trautmann_2016, place={Ischia, Italy}, series={Lecture Notes in Computer Science}, title={Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers}, volume={10079}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer International Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Festa, P and Sellmann, M and Vanschoren, J}, year={2016}, pages={48–59}, collection={Lecture Notes in Computer Science} }","mla":"Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers.” <i>Learning and Intelligent Optimization</i>, edited by P Festa et al., vol. 10079, Springer International Publishing, 2016, pp. 48–59, doi:<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>."},"intvolume":"     10079","page":"48–59","date_updated":"2024-06-10T11:58:25Z","publisher":"Springer International Publishing","author":[{"full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek","first_name":"Jakob"},{"orcid":"0000-0002-9788-8282","last_name":"Trautmann","id":"100740","full_name":"Trautmann, Heike","first_name":"Heike"}],"date_created":"2023-08-04T15:10:58Z","volume":10079,"title":"Evolving Instances for Maximizing Performance Differences of State-of-The-Art Inexact TSP Solvers","doi":"10.1007/978-3-319-50349-3_4"},{"department":[{"_id":"34"},{"_id":"819"}],"series_title":"Lecture Notes in Computer Science","user_id":"15504","_id":"46366","status":"public","editor":[{"last_name":"Adorni","full_name":"Adorni, G","first_name":"G"},{"full_name":"Cagnoni, S","last_name":"Cagnoni","first_name":"S"},{"first_name":"M","last_name":"Gori","full_name":"Gori, M"},{"first_name":"M","last_name":"Maratea","full_name":"Maratea, M"}],"type":"conference","doi":"10.1007/978-3-319-49130-1_1","volume":10037,"author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668"},{"orcid":"0000-0002-9788-8282","last_name":"Trautmann","id":"100740","full_name":"Trautmann, Heike","first_name":"Heike"}],"date_updated":"2024-06-10T11:58:12Z","page":"3–12","intvolume":"     10037","citation":{"ieee":"J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,” in <i>AI*IA 2016 Advances in Artificial Intelligence</i>, 2016, vol. 10037, pp. 3–12, doi: <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>.","chicago":"Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” In <i>AI*IA 2016 Advances in Artificial Intelligence</i>, edited by G Adorni, S Cagnoni, M Gori, and M Maratea, 10037:3–12. Lecture Notes in Computer Science. Cham: Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">https://doi.org/10.1007/978-3-319-49130-1_1</a>.","ama":"Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In: Adorni G, Cagnoni S, Gori M, Maratea M, eds. <i>AI*IA 2016 Advances in Artificial Intelligence</i>. Vol 10037. Lecture Notes in Computer Science. Springer; 2016:3–12. doi:<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>","bibtex":"@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes in Computer Science}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference}, volume={10037}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>}, booktitle={AI*IA 2016 Advances in Artificial Intelligence}, publisher={Springer}, author={Bossek, Jakob and Trautmann, Heike}, editor={Adorni, G and Cagnoni, S and Gori, M and Maratea, M}, year={2016}, pages={3–12}, collection={Lecture Notes in Computer Science} }","short":"J. Bossek, H. Trautmann, in: G. Adorni, S. Cagnoni, M. Gori, M. Maratea (Eds.), AI*IA 2016 Advances in Artificial Intelligence, Springer, Cham, 2016, pp. 3–12.","mla":"Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” <i>AI*IA 2016 Advances in Artificial Intelligence</i>, edited by G Adorni et al., vol. 10037, Springer, 2016, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>.","apa":"Bossek, J., &#38; Trautmann, H. (2016). Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In G. Adorni, S. Cagnoni, M. Gori, &#38; M. Maratea (Eds.), <i>AI*IA 2016 Advances in Artificial Intelligence</i> (Vol. 10037, pp. 3–12). Springer. <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">https://doi.org/10.1007/978-3-319-49130-1_1</a>"},"place":"Cham","publication_identifier":{"isbn":["978-3-319-49129-5"]},"language":[{"iso":"eng"}],"abstract":[{"text":"State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem (TSP) are known to mostly yield high-quality solutions in reasonable computation times. With the purpose of understanding different levels of instance difficulties, instances for the current State of the Art heuristic TSP solvers LKH+restart and EAX+restart are presented which are evolved using a sophisticated evolutionary algorithm. More specifically, the performance differences of the respective solvers are maximized resulting in instances which are easier to solve for one solver and much more difficult for the other. Focusing on both optimization directions, instance features are identified which characterize both types of instances and increase the understanding of solver performance differences.","lang":"eng"}],"publication":"AI*IA 2016 Advances in Artificial Intelligence","title":"Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference","date_created":"2023-08-04T15:11:47Z","publisher":"Springer","year":"2016"},{"_id":"48838","user_id":"102979","series_title":"GECCO ’15","department":[{"_id":"819"}],"keyword":["evolutionary algorithms","model-based optimization","parameter tuning"],"language":[{"iso":"eng"}],"extern":"1","type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"text":"The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms’ performance. Since the manual exploration of the parameter space is tedious – even for few parameters – several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features. Our contribution is the proposal of a novel concept for feature-based algorithm parameter tuning, which applies an approximating surrogate model for learning the continuous feature-parameter mapping. To accomplish this, we learn a joint model of the algorithm performance based on both the algorithm parameters and the instance features. The required data is gathered using a recently proposed acquisition function for model refinement in surrogate-based optimization: the profile expected improvement. This function provides an avenue for maximizing the information required for the feature-parameter mapping, i.e., the mapping from instance features to the corresponding optimal algorithm parameters. The approach is validated by applying the tuner to exemplary evolutionary algorithms and problems, for which theoretically grounded or heuristically determined feature-parameter mappings are available.","lang":"eng"}],"status":"public","date_updated":"2023-12-13T10:40:30Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:51Z","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979"},{"first_name":"Bernd","full_name":"Bischl, Bernd","last_name":"Bischl"},{"last_name":"Wagner","full_name":"Wagner, Tobias","first_name":"Tobias"},{"first_name":"Günter","last_name":"Rudolph","full_name":"Rudolph, Günter"}],"title":"Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement","doi":"10.1145/2739480.2754673","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-3472-3"]},"place":"New York, NY, USA","year":"2015","citation":{"short":"J. Bossek, B. Bischl, T. Wagner, G. Rudolph, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2015, pp. 1319–1326.","mla":"Bossek, Jakob, et al. “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2015, pp. 1319–1326, doi:<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>.","bibtex":"@inproceedings{Bossek_Bischl_Wagner_Rudolph_2015, place={New York, NY, USA}, series={GECCO ’15}, title={Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement}, DOI={<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Bischl, Bernd and Wagner, Tobias and Rudolph, Günter}, year={2015}, pages={1319–1326}, collection={GECCO ’15} }","apa":"Bossek, J., Bischl, B., Wagner, T., &#38; Rudolph, G. (2015). Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1319–1326. <a href=\"https://doi.org/10.1145/2739480.2754673\">https://doi.org/10.1145/2739480.2754673</a>","ama":"Bossek J, Bischl B, Wagner T, Rudolph G. Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’15. Association for Computing Machinery; 2015:1319–1326. doi:<a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>","chicago":"Bossek, Jakob, Bernd Bischl, Tobias Wagner, and Günter Rudolph. “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1319–1326. GECCO ’15. New York, NY, USA: Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2739480.2754673\">https://doi.org/10.1145/2739480.2754673</a>.","ieee":"J. Bossek, B. Bischl, T. Wagner, and G. Rudolph, “Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2015, pp. 1319–1326, doi: <a href=\"https://doi.org/10.1145/2739480.2754673\">10.1145/2739480.2754673</a>."},"page":"1319–1326"},{"doi":"10.1145/2739480.2754705","title":"Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle","author":[{"first_name":"Stephan","last_name":"Meisel","full_name":"Meisel, Stephan"},{"first_name":"Christian","full_name":"Grimme, Christian","last_name":"Grimme"},{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"last_name":"Wölck","full_name":"Wölck, Martin","first_name":"Martin"},{"full_name":"Rudolph, Günter","last_name":"Rudolph","first_name":"Günter"},{"full_name":"Trautmann, Heike","last_name":"Trautmann","first_name":"Heike"}],"date_created":"2023-11-14T15:58:59Z","date_updated":"2023-12-13T10:49:06Z","publisher":"Association for Computing Machinery","page":"425–432","citation":{"bibtex":"@inproceedings{Meisel_Grimme_Bossek_Wölck_Rudolph_Trautmann_2015, place={New York, NY, USA}, series={GECCO’15}, title={Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle}, DOI={<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference }, publisher={Association for Computing Machinery}, author={Meisel, Stephan and Grimme, Christian and Bossek, Jakob and Wölck, Martin and Rudolph, Günter and Trautmann, Heike}, year={2015}, pages={425–432}, collection={GECCO’15} }","mla":"Meisel, Stephan, et al. “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle.” <i>Proceedings of the Genetic and Evolutionary Computation Conference </i>, Association for Computing Machinery, 2015, pp. 425–432, doi:<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>.","short":"S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, H. Trautmann, in: Proceedings of the Genetic and Evolutionary Computation Conference , Association for Computing Machinery, New York, NY, USA, 2015, pp. 425–432.","apa":"Meisel, S., Grimme, C., Bossek, J., Wölck, M., Rudolph, G., &#38; Trautmann, H. (2015). Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. <i>Proceedings of the Genetic and Evolutionary Computation Conference </i>, 425–432. <a href=\"https://doi.org/10.1145/2739480.2754705\">https://doi.org/10.1145/2739480.2754705</a>","ama":"Meisel S, Grimme C, Bossek J, Wölck M, Rudolph G, Trautmann H. Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference </i>. GECCO’15. Association for Computing Machinery; 2015:425–432. doi:<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>","ieee":"S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, and H. Trautmann, “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference </i>, 2015, pp. 425–432, doi: <a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>.","chicago":"Meisel, Stephan, Christian Grimme, Jakob Bossek, Martin Wölck, Günter Rudolph, and Heike Trautmann. “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference </i>, 425–432. GECCO’15. New York, NY, USA: Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2739480.2754705\">https://doi.org/10.1145/2739480.2754705</a>."},"year":"2015","place":"New York, NY, USA","publication_identifier":{"isbn":["978-1-4503-3472-3"]},"language":[{"iso":"eng"}],"extern":"1","keyword":["combinatorial optimization","metaheuristics","multi-objective optimization","online algorithms","transportation"],"department":[{"_id":"819"}],"series_title":"GECCO’15","user_id":"102979","_id":"48887","status":"public","abstract":[{"text":"We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference ","type":"conference"},{"place":"Madrid, Spain","year":"2015","page":"425–432","citation":{"mla":"Meisel, Stephan, et al. “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle.” <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)</i>, 2015, pp. 425–432, doi:<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>.","short":"S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, H. Trautmann, in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15), Madrid, Spain, 2015, pp. 425–432.","bibtex":"@inproceedings{Meisel_Grimme_Bossek_Wölck_Rudolph_Trautmann_2015, place={Madrid, Spain}, title={Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle}, DOI={<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)}, author={Meisel, Stephan and Grimme, Christian and Bossek, Jakob and Wölck, Martin and Rudolph, Guenter and Trautmann, Heike}, year={2015}, pages={425–432} }","apa":"Meisel, S., Grimme, C., Bossek, J., Wölck, M., Rudolph, G., &#38; Trautmann, H. (2015). Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)</i>, 425–432. <a href=\"https://doi.org/10.1145/2739480.2754705\">https://doi.org/10.1145/2739480.2754705</a>","ama":"Meisel S, Grimme C, Bossek J, Wölck M, Rudolph G, Trautmann H. Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)</i>. ; 2015:425–432. doi:<a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>","ieee":"S. Meisel, C. Grimme, J. Bossek, M. Wölck, G. Rudolph, and H. Trautmann, “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)</i>, 2015, pp. 425–432, doi: <a href=\"https://doi.org/10.1145/2739480.2754705\">10.1145/2739480.2754705</a>.","chicago":"Meisel, Stephan, Christian Grimme, Jakob Bossek, Martin Wölck, Guenter Rudolph, and Heike Trautmann. “Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)</i>, 425–432. Madrid, Spain, 2015. <a href=\"https://doi.org/10.1145/2739480.2754705\">https://doi.org/10.1145/2739480.2754705</a>."},"publication_identifier":{"isbn":["978-1-4503-3472-3"]},"title":"Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle","doi":"10.1145/2739480.2754705","date_updated":"2024-06-10T11:57:57Z","author":[{"first_name":"Stephan","last_name":"Meisel","full_name":"Meisel, Stephan"},{"first_name":"Christian","full_name":"Grimme, Christian","last_name":"Grimme"},{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Martin","full_name":"Wölck, Martin","last_name":"Wölck"},{"first_name":"Guenter","full_name":"Rudolph, Guenter","last_name":"Rudolph"},{"orcid":"0000-0002-9788-8282","last_name":"Trautmann","full_name":"Trautmann, Heike","id":"100740","first_name":"Heike"}],"date_created":"2023-08-04T15:24:41Z","abstract":[{"text":"We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.","lang":"eng"}],"status":"public","publication":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15)","type":"conference","language":[{"iso":"eng"}],"_id":"46377","department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504"},{"issue":"2","publication_identifier":{"issn":["1012-2443"]},"intvolume":"        69","page":"151–182","citation":{"ama":"Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. <i>Annals of Mathematics and Artificial Intelligence</i>. 2013;69(2):151–182. doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>","ieee":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann, “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem,” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, pp. 151–182, 2013, doi: <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","chicago":"Mersmann, Olaf, Bernd Bischl, Heike Trautmann, Markus Wagner, Jakob Bossek, and Frank Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” <i>Annals of Mathematics and Artificial Intelligence</i> 69, no. 2 (2013): 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>.","apa":"Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., &#38; Neumann, F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>69</i>(2), 151–182. <a href=\"https://doi.org/10.1007/s10472-013-9341-2\">https://doi.org/10.1007/s10472-013-9341-2</a>","bibtex":"@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem}, volume={69}, DOI={<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>}, number={2}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann, Olaf and Bischl, Bernd and Trautmann, Heike and Wagner, Markus and Bossek, Jakob and Neumann, Frank}, year={2013}, pages={151–182} }","mla":"Mersmann, Olaf, et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem.” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, no. 2, 2013, pp. 151–182, doi:<a href=\"https://doi.org/10.1007/s10472-013-9341-2\">10.1007/s10472-013-9341-2</a>.","short":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals of Mathematics and Artificial Intelligence 69 (2013) 151–182."},"year":"2013","volume":69,"date_created":"2023-11-14T15:58:59Z","author":[{"first_name":"Olaf","last_name":"Mersmann","full_name":"Mersmann, Olaf"},{"full_name":"Bischl, Bernd","last_name":"Bischl","first_name":"Bernd"},{"full_name":"Trautmann, Heike","last_name":"Trautmann","first_name":"Heike"},{"first_name":"Markus","last_name":"Wagner","full_name":"Wagner, Markus"},{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"date_updated":"2023-12-13T10:50:41Z","doi":"10.1007/s10472-013-9341-2","title":"A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesperson Problem","publication":"Annals of Mathematics and Artificial Intelligence","type":"journal_article","status":"public","abstract":[{"text":"Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.","lang":"eng"}],"department":[{"_id":"819"}],"user_id":"102979","_id":"48889","language":[{"iso":"eng"}],"keyword":["2-opt","90B06","Classification","Feature selection","MARS","TSP"]},{"date_updated":"2024-06-10T11:57:43Z","author":[{"first_name":"O","full_name":"Mersmann, O","last_name":"Mersmann"},{"first_name":"B","last_name":"Bischl","full_name":"Bischl, B"},{"first_name":"Heike","orcid":"0000-0002-9788-8282","last_name":"Trautmann","full_name":"Trautmann, Heike","id":"100740"},{"full_name":"Wagner, M","last_name":"Wagner","first_name":"M"},{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"full_name":"Neumann, F","last_name":"Neumann","first_name":"F"}],"date_created":"2023-08-04T15:48:57Z","volume":69,"title":"A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem","year":"2013","citation":{"short":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, F. Neumann, Annals of Mathematics and Artificial Intelligence 69 (2013) 151–182.","bibtex":"@article{Mersmann_Bischl_Trautmann_Wagner_Bossek_Neumann_2013, title={A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem}, volume={69}, journal={Annals of Mathematics and Artificial Intelligence}, author={Mersmann, O and Bischl, B and Trautmann, Heike and Wagner, M and Bossek, Jakob and Neumann, F}, year={2013}, pages={151–182} }","mla":"Mersmann, O., et al. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem.” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, 2013, pp. 151–182.","ama":"Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F. A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem. <i>Annals of Mathematics and Artificial Intelligence</i>. 2013;69:151–182.","apa":"Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., &#38; Neumann, F. (2013). A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem. <i>Annals of Mathematics and Artificial Intelligence</i>, <i>69</i>, 151–182.","chicago":"Mersmann, O, B Bischl, Heike Trautmann, M Wagner, Jakob Bossek, and F Neumann. “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem.” <i>Annals of Mathematics and Artificial Intelligence</i> 69 (2013): 151–182.","ieee":"O. Mersmann, B. Bischl, H. Trautmann, M. Wagner, J. Bossek, and F. Neumann, “A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem,” <i>Annals of Mathematics and Artificial Intelligence</i>, vol. 69, pp. 151–182, 2013."},"page":"151–182","intvolume":"        69","_id":"46394","user_id":"15504","department":[{"_id":"34"},{"_id":"819"}],"language":[{"iso":"eng"}],"type":"journal_article","publication":"Annals of Mathematics and Artificial Intelligence","abstract":[{"text":"Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.","lang":"eng"}],"status":"public"},{"author":[{"last_name":"Mersmann","full_name":"Mersmann, Olaf","first_name":"Olaf"},{"full_name":"Bischl, Bernd","last_name":"Bischl","first_name":"Bernd"},{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","full_name":"Bossek, Jakob","id":"102979"},{"full_name":"Trautmann, Heike","last_name":"Trautmann","first_name":"Heike"},{"full_name":"Wagner, Markus","last_name":"Wagner","first_name":"Markus"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_created":"2023-11-14T15:58:59Z","date_updated":"2023-12-13T10:48:58Z","publisher":"Springer-Verlag","title":"Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness","publication_identifier":{"isbn":["978-3-642-34412-1"]},"citation":{"ieee":"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 <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 2012, pp. 115–129.","chicago":"Mersmann, Olaf, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner, and Frank Neumann. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” In <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 115–129. LION 6. Berlin, Heidelberg: Springer-Verlag, 2012.","ama":"Mersmann O, Bischl B, Bossek J, Trautmann H, Wagner M, Neumann F. Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In: <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>. LION 6. Springer-Verlag; 2012:115–129.","apa":"Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., &#38; Neumann, F. (2012). Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, 115–129.","short":"O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, F. Neumann, in: Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219, Springer-Verlag, Berlin, Heidelberg, 2012, pp. 115–129.","bibtex":"@inproceedings{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin, Heidelberg}, series={LION 6}, title={Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}, booktitle={Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219}, publisher={Springer-Verlag}, author={Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}, year={2012}, pages={115–129}, collection={LION 6} }","mla":"Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” <i>Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219</i>, Springer-Verlag, 2012, pp. 115–129."},"page":"115–129","year":"2012","place":"Berlin, Heidelberg","series_title":"LION 6","user_id":"102979","department":[{"_id":"819"}],"_id":"48890","extern":"1","language":[{"iso":"eng"}],"keyword":["2-opt","Classification","Feature Selection","MARS","TSP"],"type":"conference","publication":"Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219","status":"public","abstract":[{"text":"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 perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.","lang":"eng"}]},{"publication_identifier":{"isbn":["978-3-642-34412-1 978-3-642-34413-8"]},"citation":{"apa":"Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., &#38; Neumann, F. (2012). Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In <i>Learning and Intelligent Optimization</i> (Vol. 7219, pp. 115–129). Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>","mla":"Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” <i>Learning and Intelligent Optimization</i>, vol. 7219, Springer Berlin Heidelberg, 2012, pp. 115–129, doi:<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">10.1007/978-3-642-34413-8_9</a>.","bibtex":"@inbook{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin, Heidelberg}, title={Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}, volume={7219}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">10.1007/978-3-642-34413-8_9</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer Berlin Heidelberg}, author={Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}, year={2012}, pages={115–129} }","short":"O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, F. Neumann, in: Learning and Intelligent Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 115–129.","ama":"Mersmann O, Bischl B, Bossek J, Trautmann H, Wagner M, Neumann F. Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In: <i>Learning and Intelligent Optimization</i>. Vol 7219. Springer Berlin Heidelberg; 2012:115–129. doi:<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">10.1007/978-3-642-34413-8_9</a>","chicago":"Mersmann, Olaf, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner, and Frank Neumann. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” In <i>Learning and Intelligent Optimization</i>, 7219:115–129. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. <a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>.","ieee":"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 <i>Learning and Intelligent Optimization</i>, vol. 7219, Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 115–129."},"intvolume":"      7219","page":"115–129","year":"2012","place":"Berlin, Heidelberg","author":[{"first_name":"Olaf","full_name":"Mersmann, Olaf","last_name":"Mersmann"},{"full_name":"Bischl, Bernd","last_name":"Bischl","first_name":"Bernd"},{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"},{"last_name":"Wagner","full_name":"Wagner, Markus","first_name":"Markus"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"date_created":"2023-11-14T15:58:59Z","volume":7219,"publisher":"Springer Berlin Heidelberg","date_updated":"2023-12-13T10:49:15Z","doi":"10.1007/978-3-642-34413-8_9","title":"Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness","type":"book_chapter","publication":"Learning and Intelligent Optimization","status":"public","abstract":[{"text":"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 perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.","lang":"eng"}],"user_id":"102979","department":[{"_id":"819"}],"_id":"48888","language":[{"iso":"eng"}],"extern":"1"},{"date_created":"2023-08-04T15:53:33Z","author":[{"first_name":"Olaf","last_name":"Mersmann","full_name":"Mersmann, Olaf"},{"first_name":"Bernd","full_name":"Bischl, Bernd","last_name":"Bischl"},{"orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"first_name":"Heike","full_name":"Trautmann, Heike","id":"100740","last_name":"Trautmann","orcid":"0000-0002-9788-8282"},{"first_name":"Markus","full_name":"Wagner, Markus","last_name":"Wagner"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"publisher":"Springer Berlin Heidelberg","date_updated":"2024-06-10T11:57:32Z","doi":"https://doi.org/10.1007/978-3-642-34413-8_9","title":"Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness","publication_identifier":{"isbn":["978-3-642-34413-8"]},"page":"115–129","citation":{"ama":"Mersmann O, Bischl B, Bossek J, Trautmann H, Wagner M, Neumann F. Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In: Hamadi Y, Schoenauer M, eds. <i>Learning and Intelligent Optimization</i>. Springer Berlin Heidelberg; 2012:115–129. doi:<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>","chicago":"Mersmann, Olaf, Bernd Bischl, Jakob Bossek, Heike Trautmann, Markus Wagner, and Frank Neumann. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” In <i>Learning and Intelligent Optimization</i>, edited by Youssef Hamadi and Marc Schoenauer, 115–129. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. <a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>.","ieee":"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 <i>Learning and Intelligent Optimization</i>, 2012, pp. 115–129, doi: <a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>.","apa":"Mersmann, O., Bischl, B., Bossek, J., Trautmann, H., Wagner, M., &#38; Neumann, F. (2012). Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness. In Y. Hamadi &#38; M. Schoenauer (Eds.), <i>Learning and Intelligent Optimization</i> (pp. 115–129). Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>","bibtex":"@inproceedings{Mersmann_Bischl_Bossek_Trautmann_Wagner_Neumann_2012, place={Berlin, Heidelberg}, title={Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer Berlin Heidelberg}, author={Mersmann, Olaf and Bischl, Bernd and Bossek, Jakob and Trautmann, Heike and Wagner, Markus and Neumann, Frank}, editor={Hamadi, Youssef and Schoenauer, Marc}, year={2012}, pages={115–129} }","mla":"Mersmann, Olaf, et al. “Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness.” <i>Learning and Intelligent Optimization</i>, edited by Youssef Hamadi and Marc Schoenauer, Springer Berlin Heidelberg, 2012, pp. 115–129, doi:<a href=\"https://doi.org/10.1007/978-3-642-34413-8_9\">https://doi.org/10.1007/978-3-642-34413-8_9</a>.","short":"O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, F. Neumann, in: Y. Hamadi, M. Schoenauer (Eds.), Learning and Intelligent Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 115–129."},"year":"2012","place":"Berlin, Heidelberg","department":[{"_id":"34"},{"_id":"819"}],"user_id":"15504","_id":"46398","language":[{"iso":"eng"}],"publication":"Learning and Intelligent Optimization","type":"conference","status":"public","abstract":[{"text":"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 perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.","lang":"eng"}],"editor":[{"full_name":"Hamadi, Youssef","last_name":"Hamadi","first_name":"Youssef"},{"first_name":"Marc","last_name":"Schoenauer","full_name":"Schoenauer, Marc"}]}]