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 2017 : 1 citations

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