Sage Journals: Discover world-class research

Abstract

The traveling thief problem (TTP) is a typical combinatorial optimization problem that integrates the computational complexity of the traveling salesman problem (TSP) and the knapsack problem (KP). The interdependent and mutually restrictive relationship between these two sub-problems brings new challenges to the heuristic optimization algorithm for solving the TTP problem. This paper first analyzes the performance of three sub-component combined iterative algorithms: Memetic Algorithm with the Two-stage Local Search (MATLS), S5, and CS2SA algorithms, which all employ the Chained Lin-ighan (CLK) algorithm to generate the circumnavigation path. To investigate the influence of different traveling routes on the performance of TTP solving algorithms, we propose a combinatorial iterative TTP solving algorithm based on the Ant Colony Optimization (ACO) and MAX-MIN Ant System (MMAS). Finally, the experimental investigations suggest that the traveling route generation method dramatically impacts the performance of TTP solving algorithms. The sub-component combined iterative algorithms based on the MMAS algorithm to generate the circumnavigation path has the best practical effect.

Keywords

Traveling thief problem traveling salesman problem knapsack problem ant colony optimization MAX-MIN ant system

Get full access to this article

View all access options for this article.

References

Bonyadi

M.R.

, Michalewicz

, Barone

The Travelling Thief Problem: The First Step in the Transition from Theoretical Problems to Realistic Problems[C], 2013 IEEE Congress on Evolutionary Computation (CEC), Cancuu, Mexico, 2013, pp. 1037–1044.

Chiong

, Weise

Variants of evolutionary algorithms for real-world applications[M]. Berlin: Springer, 2012.

El Yafrani

and Ahiod

, Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing, Information Sciences 432 (2018), 231–244.

Polyakovskiy

, Bonyadi

M.R.

, Wagner

et al. A Comprehensive Benchmark Set and Heuristics for the Traveling Thief Problem[C], 2014 16th Genetic and Evolutionary Computation Conference (GECCO), Vancouver, Canada, 2014, pp. 477–484.

Mei

, Li

, Yao

Improving Efficiency of Heuris tics for the Large Scale Traveling Thief Problem[C], 2014 10th International Conference on Simulated Evolution and Learning (SEAL), Dunedin, New Zealand, 2014, pp. 631–643.

Mei

, Li

, Salim

et al., Heuristic evolution with genetic programming for Traveling Thief Problem[C], 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan, 2015, pp. 2753–2760.

Faulkner

, Polyakovskiy

, Schultz

et al., Approximate Approaches to the Traveling Thief Problem[C], 2015 17th Genetic and Evolutionary Computation Conference (GECCO), Madrid, San Marino, 2015, pp. 385–392

Gupta

, Prakash

, Greedy Heuristics for theTravelling Thief Problem[C], 2015 39th National Systems Conference (NSC), Shiv Nadar Univ, Dadri, India, 2015, pp. 1–5.

Mei

M.A.

and Hecheng

L.I.

, Hybrid genetic algorithm for solving new optimization model of TTP [J], Computer Engineering and Applications 54(06) (2018), 156–160.

10.

Zhang

, Yang

, Kang

et al., Solving the traveling thief problem based on item selection weight and reverse-order allocation[J], IEEE Access 9 (2021), 54056–54066.

11.

Ali

, Rafique

M.Z.

, Sarfraz

M.S.

et al., A novel approach for solving travelling thief problem using enhanced simulated annealing[J], PeerJ Computer Science 7 (2021), e377.

12.

Zhixiang

Research of Traveling Thief Problem Based on Discrete Particle Swarm Optimization and Its Applica-tion[D], University of Electronic Science and Technology of China, 2020.

13.

Nikfarjam

, Neumann

On the Use of Quality Diversity Algorithms for The Traveling Thief Problem[J], arXiv preprint arXiv:2112.08627 (2021).

14.

Lin

and Kernighan

B.W.

, An effective heuristic algorithm for the traveling-salesman problem[J], Operations Research 21(2) (1973), 498–516.

15.

Applegate

, Cook

and Rohe

, Chained Lin-ighan for large traveling salesman problems[J], INFORMS Journal on Computing 15(1) (2003), 82–92.

16.

El Yafrani

, Ahiod

Cosolver2B: An Efficient Local Search heuristic for the Travelling Thief Problem[C], 2015 12th IEEE/ACS International Conference of Computer Systems and Applications (AICCSA), Marrakech, Morocco, 2015, pp. 1–5.

17.

Bonyadi

M.R.

, Michalewicz

, Przybylek

M.R.

et al., Socially Inspired Algorithms for the Travelling Thief Prob-lem[C], 2014 16th Genetic and Evolutionary Computation Conference (GECCO), Vancouver, Canada, 2014, pp. 421-428.

18.

Colorni

, Dorigo

, Maniezzo

Distributed Optimization by Ant Colonies[C], 1991 1st European Con- ference on Artificial Life (ECAL), Paris, France, 1991, 142, pp. 134–142.

19.

Stutzle

, Hoos

MAX-MIN ant System and Local Search for the Traveling Salesman Problem[C], 1997 IEEE International Conference on Evolutionary Computation (ICEC’97), Indianapolis, IN, 1997, pp. 309–314.

Influence of subproblem solutions on the quality of traveling thief problem solutions

Abstract

Keywords

Get full access to this article

References