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

Article type: Research Article

Authors: Chen, Junfeng^{a; b; *} | Zheng, Kaijun^a | Li, Qingwu^a | Ayush, Altangerel^c

Affiliations: [a] College of Internet of Things Engineering, Hohai University, Changzhou, China | [b] Jiangsu Key Laboratory of Power Transmission and Distribution Equipment, Hohai University, Changzhou, China | [c] School of ICT, Mongolian University of Science and Technology, Ulaanbaatar, Mongolia

Correspondence: [*] Corresponding author. Junfeng Chen, E-mail: chen-1997@163.com.

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

DOI: 10.3233/JIFS-221032

Journal: Journal of Intelligent & Fuzzy Systems, vol. 44, no. 2, pp. 1943-1956, 2023