Improving efficiency of heuristics for the large scale traveling thief problem

Yi MEI; Xiaodong LI; Xin YAO

doi:10.1007/978-3-319-13563-2_53

Improving efficiency of heuristics for the large scale traveling thief problem

Yi MEI, Xiaodong LI, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

42 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 language	English
Title of host publication	Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings
Editors	Grant 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
Publisher	Springer, Cham
Pages	631-643
Number of pages	13
Volume	8886
ISBN (Electronic)	9783319135632
ISBN (Print)	9783319135625
DOIs	https://doi.org/10.1007/978-3-319-13563-2_53
Publication status	Published - 2014
Externally published	Yes
Event	10th International Conference on Simulated Evolution and Learning, SEAL 2014 - Dunedin, New Zealand Duration: 15 Dec 2014 → 18 Dec 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Volume	8886
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Simulated Evolution and Learning, SEAL 2014
Country/Territory	New Zealand
City	Dunedin
Period	15/12/14 → 18/12/14

Keywords

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

Access to Document

10.1007/978-3-319-13563-2_53

Cite this

MEI, Y., LI, X., & YAO, X. (2014). Improving efficiency of heuristics for the large scale traveling thief problem. In G. DICK, W. N. BROWNE, P. WHIGHAM, M. ZHANG, T. B. LAM, H. ISHIBUCHI, Y. JIN, X. LI, Y. SHI, P. SINGH, K. C. TAN, & K. TANG (Eds.), Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings (Vol. 8886, pp. 631-643). (Lecture Notes in Computer Science; Vol. 8886). Springer, Cham. https://doi.org/10.1007/978-3-319-13563-2_53

MEI, Yi ; LI, Xiaodong ; YAO, Xin. / Improving efficiency of heuristics for the large scale traveling thief problem. Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings. editor / Grant 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. Vol. 8886 Springer, Cham, 2014. pp. 631-643 (Lecture Notes in Computer Science).

@inproceedings{82ae811e58b2488895079016644f5663,

title = "Improving efficiency of heuristics for the large scale traveling thief problem",

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. {\textcopyright} Springer International Publishing Switzerland 2014.",

keywords = "Local Search, Travelling Salesman Problem, Travel Salesman Problem, Knapsack Problem, Delaunay Triangulation",

author = "Yi MEI and Xiaodong LI and Xin YAO",

year = "2014",

doi = "10.1007/978-3-319-13563-2_53",

language = "English",

isbn = "9783319135625",

volume = "8886",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "631--643",

editor = "Grant DICK and BROWNE, {Will N.} and Peter WHIGHAM and Mengjie ZHANG and LAM, {Thu Bui} and Hisao ISHIBUCHI and Yaochu JIN and Xiaodong LI and Yuhui SHI and Pramod SINGH and TAN, {Kay Chen} and Ke TANG",

booktitle = "Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings",

note = "10th International Conference on Simulated Evolution and Learning, SEAL 2014 ; Conference date: 15-12-2014 Through 18-12-2014",

}

MEI, Y, LI, X & YAO, X 2014, Improving efficiency of heuristics for the large scale traveling thief problem. in G DICK, WN BROWNE, P WHIGHAM, M ZHANG, TB LAM, H ISHIBUCHI, Y JIN, X LI, Y SHI, P SINGH, KC TAN & K TANG (eds), Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings. vol. 8886, Lecture Notes in Computer Science, vol. 8886, Springer, Cham, pp. 631-643, 10th International Conference on Simulated Evolution and Learning, SEAL 2014, Dunedin, New Zealand, 15/12/14. https://doi.org/10.1007/978-3-319-13563-2_53

Improving efficiency of heuristics for the large scale traveling thief problem. / MEI, Yi; LI, Xiaodong; YAO, Xin.
Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings. ed. / Grant 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. Vol. 8886 Springer, Cham, 2014. p. 631-643 (Lecture Notes in Computer Science; Vol. 8886).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Improving efficiency of heuristics for the large scale traveling thief problem

AU - MEI, Yi

AU - LI, Xiaodong

AU - YAO, Xin

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Local Search

KW - Travelling Salesman Problem

KW - Travel Salesman Problem

KW - Knapsack Problem

KW - Delaunay Triangulation

UR - http://www.scopus.com/inward/record.url?scp=84921419428&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13563-2_53

DO - 10.1007/978-3-319-13563-2_53

M3 - Conference paper (refereed)

SN - 9783319135625

VL - 8886

T3 - Lecture Notes in Computer Science

SP - 631

EP - 643

BT - Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings

A2 - DICK, Grant

A2 - BROWNE, Will N.

A2 - WHIGHAM, Peter

A2 - ZHANG, Mengjie

A2 - LAM, Thu Bui

A2 - ISHIBUCHI, Hisao

A2 - JIN, Yaochu

A2 - LI, Xiaodong

A2 - SHI, Yuhui

A2 - SINGH, Pramod

A2 - TAN, Kay Chen

A2 - TANG, Ke

PB - Springer, Cham

T2 - 10th International Conference on Simulated Evolution and Learning, SEAL 2014

Y2 - 15 December 2014 through 18 December 2014

ER -

MEI Y, LI X, YAO X. Improving efficiency of heuristics for the large scale traveling thief problem. In DICK G, BROWNE WN, WHIGHAM P, ZHANG M, LAM TB, ISHIBUCHI H, JIN Y, LI X, SHI Y, SINGH P, TAN KC, TANG K, editors, Simulated Evolution and Learning : 10th International Conference, SEAL 2014, Dunedin, New Zealand, December 15-18, Proceedings. Vol. 8886. Springer, Cham. 2014. p. 631-643. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-13563-2_53

Improving efficiency of heuristics for the large scale traveling thief problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this