  Many real-world optimization problems have multiple interacting components.
Each of these can be NP-hard and they can be in conflict with each other, i.e.,
the optimal solution for one component does not necessarily represent an
optimal solution for the other components. This can be a challenge for
single-objective formulations, where the respective influence that each
component has on the overall solution quality can vary from instance to
instance. In this paper, we study a bi-objective formulation of the traveling
thief problem, which has as components the traveling salesperson problem and
the knapsack problem. We present a weighted-sum method that makes use of
randomized versions of existing heuristics, that outperforms participants on 6
of 9 instances of recent competitions, and that has found new best solutions to
379 single-objective problem instances.
