This study addresses the recently introduced Traveling Thief Problem (TTP) which combines the classical Traveling Salesman Problem (TSP) with the 0-1 Knapsack Problem (KP). The problem consists of a set of cities, each containing a set of available items with weights and profits. It involves searching for a permutation of the cities to visit and a decision on items to pick. A selected item contributes its profit to the overall profit at the price of higher transportation cost incurred by its weight. The objective is to maximize the resulting profit.

We propose a number of problem-specific packing strategies run on top of TSP solutions derived by the Chained Lin-Kernighan heuristic. The investigations provided on the set of benchmark instances prove their rapidity and efficiency when compared with an approximate mixed integer programming based approach and state-of-the-art heuristic solutions from the literature.

Code and full results available here


1 2
January 28th, 2014

You think water moves fast? You should see ice

January 9th, 2017

Video Description (With Deep Neural Networks)

November 30th, 2015

Hello world!

January 28th, 2014

The hidden benefits of gossip, ostracism

January 28th, 2014

Rust Belt gentrification and how it hurts the poor

January 28th, 2014

An old mathematical puzzle soon to be unraveled?

January 28th, 2014

Making stem cells grow human hair

January 28th, 2014

Study analyzes content of nightmares and bad dreams

January 28th, 2014

Just another blog post

January 28th, 2014

Astronomy podcast for kids