Dynamic programming operators for the bi-objective Traveling Thief Problem

Roberto Santana, Siddhartha Shakya

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

The traveling thief problem (TTP) has emerged as a realistic multi-component problem that poses a number of challenges to traditional optimizers. In this paper we propose different ways to incorporate dynamic programming (DP) as a local optimization operator of population-based approaches to the biobjective TTP. The DP operators use different characterizations of the TTP instance to search for packing plans that improve the best current solutions. We evaluate the efficiency of the DP-based operators using TTP instances of up to 33810 cities and 338100 items, and compare the results of the DP operators with state-of-the-art algorithms for these instances. Our results show that DP-based approaches, applied individually and in combination with other types of operators, can produce good approximations of the Pareto sets for these problems.

Original languageBritish English
Title of host publication2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728169293
DOIs
StatePublished - Jul 2020
Event2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Virtual, Glasgow, United Kingdom
Duration: 19 Jul 202024 Jul 2020

Publication series

Name2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings

Conference

Conference2020 IEEE Congress on Evolutionary Computation, CEC 2020
Country/TerritoryUnited Kingdom
CityVirtual, Glasgow
Period19/07/2024/07/20

Keywords

  • dynamic programming
  • evolutionary optimization
  • MOEA
  • traveling thief problem
  • TSP

Fingerprint

Dive into the research topics of 'Dynamic programming operators for the bi-objective Traveling Thief Problem'. Together they form a unique fingerprint.

Cite this