Improving efficiency of heuristics for the large scale traveling thief problem

Yi MEI, Xiaodong LI, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

37 Citations (Scopus)

Abstract

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. © Springer International Publishing Switzerland 2014.
Original languageEnglish
Title of host publicationSimulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings
EditorsGrant DICK, Will N. BROWNE, Peter WHIGHAM, Mengjie ZHANG, Thu Bui LAM, Hisao ISHIBUCHI, Yaochu JIN, Xiaodong LI, Yuhui SHI, Pramod SINGH, Kay Chen TAN, Ke TANG
PublisherSpringer, Cham
Pages631-643
Number of pages13
Volume8886
ISBN (Electronic)9783319135632
ISBN (Print)9783319135625
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event10th International Conference on Simulated Evolution and Learning, SEAL 2014 - Dunedin, New Zealand
Duration: 15 Dec 201418 Dec 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume8886
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Simulated Evolution and Learning, SEAL 2014
Country/TerritoryNew Zealand
CityDunedin
Period15/12/1418/12/14

Keywords

  • Local Search
  • Travelling Salesman Problem
  • Travel Salesman Problem
  • Knapsack Problem
  • Delaunay Triangulation

Fingerprint

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