Evolutionary Computation plus Dynamic Programming for the Bi-Objective
  Travelling Thief Problem
  This research proposes a novel indicator-based hybrid evolutionary approach
that combines approximate and exact algorithms. We apply it to a new
bi-criteria formulation of the travelling thief problem, which is known to the
Evolutionary Computation community as a benchmark multi-component optimisation
problem that interconnects two classical NP-hard problems: the travelling
salesman problem and the 0-1 knapsack problem. Our approach employs the exact
dynamic programming algorithm for the underlying Packing-While-Travelling (PWT)
problem as a subroutine within a bi-objective evolutionary algorithm. This
design takes advantage of the data extracted from Pareto fronts generated by
the dynamic program to achieve better solutions. Furthermore, we develop a
number of novel indicators and selection mechanisms to strengthen synergy of
the two algorithmic components of our approach. The results of computational
experiments show that the approach is capable to outperform the
state-of-the-art results for the single-objective case of the problem.
