A comparative study of evolutionary approaches to the bi-objective dynamic Travelling Thief Problem

Daniel HERRING*, Michael KIRLEY, Xin YAO

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

Abstract

Dynamic evolutionary multi-objective optimization is a thriving research area. Recent contributions span the development of specialized algorithms and the construction of challenging benchmark problems. Here, we continue these research directions through the development and analysis of a new bi-objective problem, the dynamic Travelling Thief Problem (TTP), including three modes of dynamic change: city locations, item profit values, and item availability. The interconnected problem components embedded in the dynamic problem dictate that the effective tracking of good trade-off solutions that satisfy both objectives throughout dynamic events is non-trivial. Consequently, we examine the relative contribution to the non-dominated set from a variety of population seeding strategies, including exact solvers and greedy algorithms for the knapsack and tour components, and random techniques. We introduce this responsive seeding extension within an evolutionary algorithm framework. The efficacy of alternative seeding mechanisms is evaluated across a range of exemplary problem instances using ranking-based and quantitative statistical comparisons, which combines performance measurements taken throughout the optimization. Our detailed experiments show that the different dynamic TTP instances present varying difficulty to the seeding methods tested. We posit the dynamic TTP as a suitable benchmark capable of generating problem instances with different controllable characteristics aligning with many real-world problems.

Original languageEnglish
Article number101433
JournalSwarm and Evolutionary Computation
Volume84
Early online date30 Nov 2023
DOIs
Publication statusPublished - Feb 2024
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2023 The Authors

Keywords

  • Combinatorial optimization
  • Dynamic multi-objective optimization
  • Evolutionary algorithms
  • Travelling Thief Problem

Fingerprint

Dive into the research topics of 'A comparative study of evolutionary approaches to the bi-objective dynamic Travelling Thief Problem'. Together they form a unique fingerprint.

Cite this