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.

Conference

EvoCOP, March 2016

DOI

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.