Skip to main content
Top

2017 | OriginalPaper | Chapter

Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms

Authors : Julian Blank, Kalyanmoy Deb, Sanaz Mostaghim

Published in: Evolutionary Multi-Criterion Optimization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This publication investigates characteristics of and algorithms for the quite new and complex Bi-Objective Traveling Thief Problem, where the well-known Traveling Salesman Problem and Binary Knapsack Problem interact. The interdependence of these two components builds an interwoven system where solving one subproblem separately does not solve the overall problem. The objective space of the Bi-Objective Traveling Thief Problem has through the interaction of two discrete subproblems some interesting properties which are investigated. We propose different kind of algorithms to solve the Bi-Objective Traveling Thief Problem. The first proposed deterministic algorithm picks items on tours calculated by a Traveling Salesman Problem Solver greedily. As an extension, the greedy strategy is substituted by a Knapsack Problem Solver and the resulting Pareto front is locally optimized. These methods serve as a references for the performance of multi-objective evolutionary algorithms. Additional experiments on evolutionary factory and recombination operators are presented. The obtained results provide insights into principles of an exemplary bi-objective interwoven system and new starting points for ongoing research.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ishibushi, H., Klamroth, K., Mostaghim, S., Naujoks, B., Poles, S., Purshouse, R., Rudolph, G., Ruzika, S., Sayin, S., Wiecek, M.M., Yao, X.: Multiobjective Optimization for Interwoven Systems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015) Ishibushi, H., Klamroth, K., Mostaghim, S., Naujoks, B., Poles, S., Purshouse, R., Rudolph, G., Ruzika, S., Sayin, S., Wiecek, M.M., Yao, X.: Multiobjective Optimization for Interwoven Systems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)
2.
go back to reference Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2007)MATH Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2007)MATH
3.
go back to reference Lagoudakis, M.G.: The 0–1 Knapsack Problem - An Introductory Survey (1996) Lagoudakis, M.G.: The 0–1 Knapsack Problem - An Introductory Survey (1996)
4.
go back to reference Bonyadi, M.R., Michalewicz, Z., Barone, L.: The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: IEEE Congress on Evolutionary Computation, pp. 1037–1044. IEEE (2013) Bonyadi, M.R., Michalewicz, Z., Barone, L.: The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: IEEE Congress on Evolutionary Computation, pp. 1037–1044. IEEE (2013)
5.
go back to reference Polyakovskiy, S., Bonyadi, M.R., Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, ser. GECCO 2014, pp. 477–484. ACM, New York (2014). http://doi.acm.org/10.1145/2576768.2598249 Polyakovskiy, S., Bonyadi, M.R., Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, ser. GECCO 2014, pp. 477–484. ACM, New York (2014). http://​doi.​acm.​org/​10.​1145/​2576768.​2598249
6.
go back to reference Reinelt, G.: TSPLIB - A t.s.p. library. Universität Augsburg, Institut für Mathematik, Augsburg. Technical report 250 (1990) Reinelt, G.: TSPLIB - A t.s.p. library. Universität Augsburg, Institut für Mathematik, Augsburg. Technical report 250 (1990)
7.
8.
go back to reference Bonyadi, M.R., Michalewicz, Z., Przybylek, M.R., Wierzbicki, A.: Socially inspired algorithms for the travelling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, ser. GECCO 2014, pp. 421–428. ACM, New York (2014). http://doi.acm.org/10.1145/2576768.2598367 Bonyadi, M.R., Michalewicz, Z., Przybylek, M.R., Wierzbicki, A.: Socially inspired algorithms for the travelling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, ser. GECCO 2014, pp. 421–428. ACM, New York (2014). http://​doi.​acm.​org/​10.​1145/​2576768.​2598367
9.
go back to reference Birkedal, R.: Design, implementation, comparison of randomized search heuristics for the traveling thief problem, Master’s thesis. Technical University of Denmark, Department of Applied Mathematics, Computer Science, Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk (2015). http://www.compute.dtu.dk/English.aspx Birkedal, R.: Design, implementation, comparison of randomized search heuristics for the traveling thief problem, Master’s thesis. Technical University of Denmark, Department of Applied Mathematics, Computer Science, Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk (2015). http://​www.​compute.​dtu.​dk/​English.​aspx
12.
go back to reference Mei, Y., Li, X., Yao, X.: Improving efficiency of heuristics for the large scale traveling thief problem. In: Proceedings of the Simulated Evolution, Learning - 10th International Conference, SEAL 2014, Dunedin, New Zealand, 15–18 December 2014, pp. 631–643 (2014). http://dx.doi.org/10.1007/978-3-319-13563-2_53 Mei, Y., Li, X., Yao, X.: Improving efficiency of heuristics for the large scale traveling thief problem. In: Proceedings of the Simulated Evolution, Learning - 10th International Conference, SEAL 2014, Dunedin, New Zealand, 15–18 December 2014, pp. 631–643 (2014). http://​dx.​doi.​org/​10.​1007/​978-3-319-13563-2_​53
13.
go back to reference Wachter, C.: Solving the travelling thief problem with an evolutionary algorithm. Diplomarbeit, Technischen Universitt Wien (2015) Wachter, C.: Solving the travelling thief problem with an evolutionary algorithm. Diplomarbeit, Technischen Universitt Wien (2015)
15.
go back to reference Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2000)CrossRef Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2000)CrossRef
17.
go back to reference Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0–1 knapsack problem. Manage. Sci. 45(3), 414–424 (1999)CrossRefMATH Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0–1 knapsack problem. Manage. Sci. 45(3), 414–424 (1999)CrossRefMATH
18.
go back to reference Oliver, I.M., Smith, D.J., Holland, J.R.C.: A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and their Application, pp. 224–230. L.E. Associates Inc., Mahwah (1987) Oliver, I.M., Smith, D.J., Holland, J.R.C.: A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and their Application, pp. 224–230. L.E. Associates Inc., Mahwah (1987)
Metadata
Title
Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms
Authors
Julian Blank
Kalyanmoy Deb
Sanaz Mostaghim
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-54157-0_4

Premium Partner