CISUC

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

Authors

Abstract

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