Improving efficiency of heuristics for the large scale traveling thief problem

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


Colleges, School and Institutes

External organisations

  • RMIT University


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
Publication statusPublished - 2014

Publication series

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