On investigation of interdependence between sub-problems of the Travelling Thief Problem

Yi MEI, Xiaodong LI, Xin YAO

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

40 Citations (Scopus)


In this paper, the interdependence between sub-problems in a complex overall problem is investigated using a benchmark problem called Travelling Thief Problem (TTP), which is a combination of Travelling Salesman Problem (TSP) and Knapsack Problem (KP). First, the analysis on the mathematical formulation shows that it is impossible to decompose the problem into independent sub-problems due to the non-linear relationship in the objective function. Therefore, the algorithm for TTP is not straightforward although each sub-problem alone has been investigated intensively. Then, two meta-heuristics are proposed for TTP. One is the Cooperative Co-evolution (CC) that solves the sub-problems separately and transfers the information between them in each generation. The other is the Memetic Algorithm (MA) that solves TTP as a whole. The comparative results showed that MA consistently obtained much better results than both the standard and dynamic versions of CC within comparable computational budget. This indicates the importance of considering the interdependence between sub-problems in an overall problem like TTP. © 2014, Springer-Verlag Berlin Heidelberg.
Original languageEnglish
Pages (from-to)157-172
Number of pages16
JournalSoft Computing
Issue number1
Early online date16 Oct 2014
Publication statusPublished - Jan 2016
Externally publishedYes

Bibliographical note

This work was supported by an ARC Discovery Grant (No. DP120102205) and an EPSRC Grant (No. EP/I010297/1). Xin Yao is supported by a Royal Society Wolfson Research Merit Award.


  • Combinatorial optimization
  • Cooperative Co-evolution
  • Evolutionary computation
  • Interdependence
  • Travelling Thief Problem


Dive into the research topics of 'On investigation of interdependence between sub-problems of the Travelling Thief Problem'. Together they form a unique fingerprint.

Cite this