Improving efficiency of heuristics for the large scale traveling thief problem

Yi Mei*, Xiaodong Li, Xin Yao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Citations (Scopus)


The Traveling Thief Problem (TTP) is a novel problem that combines the well-known Traveling Salesman Problem (TSP) and Knapsack Problem (KP). In this paper, the complexity of the local-searchbased heuristics for solving TTP is analyzed, and complexity reduction strategies for TTP are proposed to speed up the heuristics. Then, a two-stage local search process with fitness approximation schemes is designed to further improve the efficiency of heuristics. Finally, an efficient Memetic Algorithm (MA) with the two-stage local search is proposed to solve the large scale TTP. The experimental results on the tested large scale TTP benchmark instances showed that the proposed MA can obtain competitive results within a very short time frame for the large scale TTP. This suggests the potential benefits of designing intelligent divide-and-conquer strategies that solves the sub-problems separately while taking the interdependence between them into account.

Original languageEnglish
Title of host publicationSimulated Evolution and Learning
Subtitle of host publication10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, 2014. Proceedings
Number of pages13
ISBN (Electronic) 9783319135632
ISBN (Print) 9783319135625
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science


Dive into the research topics of 'Improving efficiency of heuristics for the large scale traveling thief problem'. Together they form a unique fingerprint.

Cite this