IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v24y2018i3d10.1007_s10732-017-9328-y.html
   My bibliography  Save this article

A case study of algorithm selection for the traveling thief problem

Author

Listed:
  • Markus Wagner

    (The University of Adelaide)

  • Marius Lindauer

    (Albert-Ludwigs-Universität Freiburg)

  • Mustafa Mısır

    (Nanjing University of Aeronautics and Astronautics)

  • Samadhi Nallaperuma

    (University of Sheffield)

  • Frank Hutter

    (Albert-Ludwigs-Universität Freiburg)

Abstract

Many real-world problems are composed of several interacting components. In order to facilitate research on such interactions, the Traveling Thief Problem (TTP) was created in 2013 as the combination of two well-understood combinatorial optimization problems. With this article, we contribute in four ways. First, we create a comprehensive dataset that comprises the performance data of 21 TTP algorithms on the full original set of 9720 TTP instances. Second, we define 55 characteristics for all TPP instances that can be used to select the best algorithm on a per-instance basis. Third, we use these algorithms and features to construct the first algorithm portfolios for TTP, clearly outperforming the single best algorithm. Finally, we study which algorithms contribute most to this portfolio.

Suggested Citation

  • Markus Wagner & Marius Lindauer & Mustafa Mısır & Samadhi Nallaperuma & Frank Hutter, 2018. "A case study of algorithm selection for the traveling thief problem," Journal of Heuristics, Springer, vol. 24(3), pages 295-320, June.
    • Handle: RePEc:spr:joheur:v:24:y:2018:i:3:d:10.1007_s10732-017-9328-y
    DOI: 10.1007/s10732-017-9328-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-017-9328-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-017-9328-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. David Applegate & William Cook & André Rohe, 2003. "Chained Lin-Kernighan for Large Traveling Salesman Problems," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 82-92, February.
    3. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    4. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    5. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Müller, David & Müller, Marcus G. & Kress, Dominik & Pesch, Erwin, 2022. "An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning," European Journal of Operational Research, Elsevier, vol. 302(3), pages 874-891.
    2. Jonatas B. C. Chagas & Julian Blank & Markus Wagner & Marcone J. F. Souza & Kalyanmoy Deb, 2021. "A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem," Journal of Heuristics, Springer, vol. 27(3), pages 267-301, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    2. Fatih Rahim & Canan Sepil, 2014. "A location-routing problem in glass recycling," Annals of Operations Research, Springer, vol. 223(1), pages 329-353, December.
    3. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    4. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    5. William Cook & Paul Seymour, 2003. "Tour Merging via Branch-Decomposition," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 233-248, August.
    6. William Cook & Sanjeeb Dash & Ricardo Fukasawa & Marcos Goycoolea, 2009. "Numerically Safe Gomory Mixed-Integer Cuts," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 641-649, November.
    7. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    8. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    9. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    10. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    11. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    12. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    13. Ernst Althaus & Felix Rauterberg & Sarah Ziegler, 2020. "Computing Euclidean Steiner trees over segments," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 309-325, October.
    14. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    15. Martins, Francisco Leonardo Bezerra & do Nascimento, José Cláudio, 2022. "Power law dynamics in genealogical graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    16. Marjan Marzban & Qian-Ping Gu & Xiaohua Jia, 2016. "New analysis and computational study for the planar connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 198-225, July.
    17. Ferrer, José M. & Martín-Campo, F. Javier & Ortuño, M. Teresa & Pedraza-Martínez, Alfonso J. & Tirado, Gregorio & Vitoriano, Begoña, 2018. "Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications," European Journal of Operational Research, Elsevier, vol. 269(2), pages 501-515.
    18. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    19. Jesus Garcia-Diaz & Jairo Sanchez-Hernandez & Ricardo Menchaca-Mendez & Rolando Menchaca-Mendez, 2017. "When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem," Journal of Heuristics, Springer, vol. 23(5), pages 349-366, October.
    20. Thomas R. Visser & Remy Spliet, 2020. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(4), pages 1091-1112, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:24:y:2018:i:3:d:10.1007_s10732-017-9328-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.