An Evolutionary Approach to the Full Optimization of the Traveling Thief Problem



Real-World problems usually consist of several different small sub-problems interacting with each other. These interactions promote a relation of interdependence, where the quality of a solution to one sub-problem influences the quality of another partial solution. The Traveling Thief Problem (TTP) is a recent benchmark that results from the combination of the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP). Thus far, existing approaches solve the TTP by fixing one of the components, usually the TSP, and then tackling the KP. We follow in a different direction and propose an Evolutionary Algorithm that addresses both sub-problems at the same time. Experimental results show that solving the TTP as whole creates conditions for discovering solutions with enhanced quality, and that fixing one of the components might compromise the overall results.


EvoCOP, March 2016


Cited by

Year 2018 : 3 citations

 Wu, J., Polyakovskiy, S., Wagner, M., & Neumann, F. (2018). Evolutionary Computation plus Dynamic Programming for the Bi-Objective Travelling Thief Problem. arXiv preprint arXiv:1802.02434.

 Nieto-Fuentes, R., Segura, C., & Valdez, S. I. (2018, July). A Guided Local Search Approach for the Travelling Thief Problem. In 2018 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE.

 Wuijts, R. H. (2018). Investigation of the Traveling Thief Problem (Master's thesis).

Year 2017 : 3 citations

 Vieira, D. K., Soares, G. L., Vasconcelos, J. A., and Mendes, M. H. (2017, April). A Ge- netic Algorithm for Multi-component Optimization Problems: The Case of the Travel- ling Thief Problem. In European Conference on Evolutionary Computation in Combi- natorial Optimization (pp. 18-29). Springer, Cham.

 Moeini,M.,Schermer,D.,andWendt,O.(2017,July).AHybridEvolutionaryApproach for Solving the Traveling Thief Problem. In International Conference on Computational Science and Its Applications (pp. 652-668). Springer, Cham.

 Polyakovskiy, Sergey, and Frank Neumann. "The Packing While Traveling Problem." European Journal of Operational Research 258, no. 2 (2017): 424-439.