arXiv:1802.02434v1 [cs.AI] 7 Feb 2018

Evolutionary Computation plus Dynamic
Programming for the Bi-Objective Travelling
Thief Problem
Junhua Wu1 , Sergey Polyakovskiy2 , Markus Wagner1 , and Frank
Neumann1
1

School of Computer Science, The University of Adelaide
2
School of Information Technology, Deakin University

Abstract
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
N P-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 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.

1

Introduction

The travelling thief problem (TTP) [4] is a bi-component problem, where two
well-known N P-hard combinatorial optimisation problems, namely the travelling salesperson problem (TSP) and the 0-1 knapsack problem (KP), are interrelated. Hence, tackling each component individually is unlikely to lead to a
global optimal solution. It is an artificial benchmark problem modelling features
of complex real-world applications emerging in the areas of planning, scheduling
and routing. For example, Stolk, Mann, Mohais, and Michalewicz [24] exemplify a delivery problem that consist of a routing part for the vehicle(s) and a
packing part of the goods onto the vehicle(s).
1

Thus far, many approaches have been proposed for the TTP [5, 9–12, 14–
18, 22, 25, 27, 31]. However to the best of our knowledge, all of them are
focusing on utilising the existing heuristic approaches (such as local search,
simulated annealing, tabu search, genetic algorithms, memetic algorithm, swarm
intelligence, etc.), incorporating either well-studied operators of the TSP and
KP or slight variations of such operators. The heuristic approaches or operators
that take advantage of the existing exact algorithms of the TTP [20, 30] are yet
lacking. On the other hand, very few investigations have been taken on the
approaches of the multi-objective formulations of the TTP except by Blank,
Deb, and Mostaghim [3], Yafrani, Chand, Neumann, Ahiod, and Wagner [32].
In this paper, we consider a bi-objective version of the TTP, where the
goal is to minimise the weight and maximise the overall benefit of a solution.
We present a hybrid approach for the bi-objective TTP that uses the dynamic
programming approach for the underlying PWT problem as a subroutine. The
evolutionary component of our approach constructs a tour π for the TTP. This
tour is then fed into the dynamic programming algorithm to compute a trade-off
front for the bi-objective problem. Here the tour π is kept fixed and the resulting
packing solutions are Pareto optimal owing to the capability of the dynamic
programming. A key aspect of the algorithm is to take advantage of the different
fronts belonging to different tours for the TTP component, as presumably the
global Pareto optimum might contain some segments from the different fronts.
Meanwhile, when the evolutionary approach evolves the tours and the current
general Pareto front consists of different tours (together with the packing plans),
a challenge is to select tours for mutations and crossovers that lead to promising
new tours. Such tours shall result in new Pareto optimal solutions for the
overall bi-objective TTP problem when running the dynamic programming on
them. In short, the selection mechanism shall encourage the synergy of the two
sub-approaches. We introduce a novel indicator-based evolutionary algorithm
(IBEA [33]) that contains a series of customised indicators and parent selections
to achieve this goal. Our results show that this approach solves the problem
well, and its by-product, which is the total reward of the single objective TTP,
beats the state-of-the-art approach in most cases.
The remainder of the paper first states the bi-objective version of the TTP
mathematically in Section 2. Then, Section 3 covers the prerequisites required
for our approach, which is later introduced in Section 4. Section 5 provides
the description of the computational setup and the analysis of computational
experiments. Finally, Section 6 draws conclusions.

2

The Travelling Thief Problem

The standard single-objective TTP [22] involves n cities, m items, and a thief
who must make a tour visiting each of the cities exactly once. The cities form a
set of nodes V = {1, . . . , n} in a complete graph G = (V, E), where E ⊆ V 2 is a
set of edges representing all possible connections between the cities. Every edge
eij ∈ E is assigned a known distance dij . Every node i ∈ V but the first one

2

Pn
relates to a unique set of items Mi = {1, . . . , mi }, i=2 mi = m, stored in the
corresponding city. Each item k ∈ Mi positioned in node i is associated with an
integer profit pik and an integer weight wik . The thief starts and ends the tour
in the first node and can collect any of the items located in the intermediate
nodes 2, . . . , n. Items may only be selected until their total weight exceeds a
knapsack’s capacity C. Furthermore, the thief pays a rent rate R for each time
unit of travelling. Selection of an item contributes its profit to a total reward,
but produces a transportation cost relative to its weight. As the weight of each
added item slows down the thief, the transportation cost increases. This cost
is therefore deducted from the reward. When the knapsack is empty, the thief
can achieve a maximal velocity υmax . When it is full, the thief can only move
with a minimal velocity υmin > 0. The actual velocity υi when moving along
the edge eij depends on the total weight of items chosen in the cities preceding
i. The problem asks to determine a combination of a tour and a subset of items
that minimises the difference between the total profit of selected items and the
overall transportation cost.
Let an integer-valued vector π ∈ V n , π = (π1 , ..., πn ), represent a tour such
that πi = j iff j is the ith visited node of the tour. Clearly, πi 6= πj for any i, j ∈
m
V , i 6= j. Next, let a binary decision vector ρ ∈ {0, 1} , ρ = (ρ21 , ..., ρnmn ),
encode a packing plan of the problem such
Pi that
Pmρjik = 1 iff item k in node i is
chosen, and 0 otherwise. Then Wπi = j=1 k=1
wjk ρjk is a total weight of
items sequentially selected in the nodes from π1 to πi , and υπi = υmax − νWπi ,
ν = (υmax − υmin ) /C, is the real velocity of the thief quitting the ith node. In
summary, the objective function of the TTP has the following form:
!
mi
n X
n−1
X
X dπi πi+1 dπ π
n 1
+
(1)
pik ρik −R
f (π, ρ) =
υπ i
υπ n
i=1
i=1
k=1

Here, we extend the standard formulation of the TTP by introduction of an
additional objective function. The new version, named as BO-TTP for short, becomes a bi-objective optimisation problem, where the total accumulated weight
ϕ (ρ) =

mi
n X
X

wik ρik

(2)

i=1 k=1

yields the second criterion. Such extension appears natural regarding the TTP
as one may either need to maximise the reward for a given weight of collected
items, or determine the least weight subject to bounds imposed on the reward.
Note that even if π is fixed, (1) is a non-monotone sub-modular function [23] that
implies possible deterioration of the reward as the number of selected items, and
therefore their total weight, increases. We formulate the BO-TTP as follows:

arg max f (π, ρ)
(π, ρ) =
s.t. ϕ (ρ) ≤ C
arg min ϕ(ρ)
As a bi-objective optimisation problem, BO-TTP asks for a set of Paretooptimal solutions where each feasible solution cannot be improved in a second
3

objective without degrading quality of the first one, and vice versa. In other
words, the goal is to find a set of all non-dominated feasible solutions X ⊆
Π × P such that for any solution (π, ρ) ∈ X there is no solution (π 0 , ρ0 ) ∈ X
such that either (f (π, ρ) < f (π 0 , ρ0 ))∧(ϕ (ρ) ≥ ϕ (ρ0 )) or (f (π, ρ) ≥ f (π 0 , ρ0 ))∧
(ϕ (ρ) < ϕ (ρ0 )) holds, where Π is a set of feasible tours and P is a set of feasible
packing plans.

3

Prerequisites

The packing while travelling problem (PWT) is a special case of the TTP,
which maximises the total reward for a specific tour π [23]. Thus, an optimal
solution of the PWT defines a subset of items producing the maximal gain.
This yields a non-linear knapsack problem, which can be efficiently solved via
the dynamic programming (DP) approach proposed by Neumann et al. [20].
Most importantly, we find that the DP yields not just a single optimal packing
plan, but a set of plans P π ⊆ P , where (π, ρ) and (π, ρ0 ) do not dominate each
other for any ρ, ρ0 ∈ P π . We name the corresponding objective vectors of P π as
a DP front. In Section 4, we design our hybrid algorithm that takes advantage
of the features of a DP front.
For self-sufficiency of the paper, in Section 3.1, we first briefly explain the
DP and how we adopt it to obtain a DP front. Section 3.2 then discusses several
algorithms to obtain tours that are later utilised by the DP to create multiple
DP fronts and to initialise the population for our hybrid evolutionary approach.

3.1

Dynamic Programming for the PWT

The DP for the PWT bases on a scheme traditional to the classical 0-1 knapsack
problem. It processes items in the lexicographic order as they appear along a
given tour π; that is, item l ∈ πi strictly precedes item k ∈ πj , to be written as
l  k, if either πi < πj or (πi = πj ) ∧ (l ≤ k) holds. Its table B is an m × C
matrix, where entry βkw represents the maximal reward that can be achieved
by examining all combinations of items l with l  k leading to the weight equal
to w. The base case of the DP with respect to the first item k, according to the
precedence order, positioned in node πi is as follows:



n−1

X


R 

− υmax
dπj πj+1 +dπn π1  ,
if w = 0




j=1



n−1
βkw =
X dπj πj+1 dπ π


+ n 1  , if w = wπi k
pπi k − R 


υ
υπn

π
j

j=1



−∞,
if w ∈
/ {0, wπi k }
Here, the first case relates to the empty packing when the thief collects no items
at all while travelling along π, and the second computes the reward when only
item k is chosen. Where a combination yielding w doesn’t exist, βkw = −∞.
4

For the general case, let item l be the predecessor of item k with regard to the
precedence order. And let β(k·) denote the column containing all the entries
βkw for w ∈ [0, C]. Then based on β(l·) one can obtain β(k·) computing each
entry βkw , assuming that item k is in node πi , as


βlw


n−1

X  dπj πj+1

dπj πj+1
−
β
+p
−R
lw−w
π
k
max
i
πi k
vmax − νw vmax − ν(w − wπi k )

j=i





dπn π1
d πn π 1

−R
−
vmax −νw

vmax −ν(w−wπi k )

In order to reduce the search space, in each column the cells dominated by other
cells are to be eliminated, i.e. if βkw1 > βkw2 and w1 ≤ w2 , then βkw2 = −∞.
An optimal solution derived by the DP corresponds to the maximal reward
stored in the last column of B. That is, maxw {β(s, w)} is the value of an
optimal solution, where s is the last item according to the precedence order.
The last column of B can be considered as a complete set of non-dominated
packing plans P π ⊆ Pπ ⊆ P , where Pπ is the set of all feasible packing plans for
a given tour π. The packing plans in P π are non-dominated exclusion of any
dominated solutions during the solution construction process.
Definition 1 Letting τ and Tπ be the corresponding objective vectors sets of
P π and Pπ respectively, τ is the Pareto front of Tπ . We therefore name τ as a
DP front for the given tour π.
A DP front τ for a tour π is a complete non-dominated set, as it contains all
non-dominated objective vectors in Tπ . We take advantage of this completeness
to generate the spread of solutions in our bi-objective approach in Section 4.

3.2

Generation of Multiple DP Fronts

As a single DP front τ is produced for a single given tour π, i.e. π 7→ τ ,
we could generate multiple TSP tours to get a set of DP fronts. In practice,
various algorithms are capable of producing superior tours for the TSP, and
therefore many approaches to the TTP use this capability to succeed. Highperforming TTP algorithms are commonly two-stage heuristic approaches, like
those proposed by Polyakovskiy et al. [22], Faulkner et al. [12], and El Yafrani
and Ahiod [9]. Specifically, their first step generates a near-optimal TSP tour
and the second step completes solution by selection of a subset of items. Most
of the approaches utilise the Chained Lin-Kernighan heuristic [2], because it
is able to provide very tight upper bounds for TSP instances in short time.
The knapsack component then is often handled via constructive heuristics or
evolutionary approaches. However, the TTP is essentially structured in such
way that the importance of its both components is almost equal within the
problem. Although near-optimal TSP solutions can give good solutions to the
TTP, most of them are far away from being optimal [30]. This is the reason
for our first experimental study here, where we investigate the impact of several
5

TSP algorithms on TTP solutions. Note that owing to the DP we are able to
solve the knapsack part to optimality, which contributes to the validity of our
findings.
We analysed five algorithms for the TSP: the Inver-over heuristic (INV) [26],
the exact solver Concorde (CON) [1], the ant colony-based approach (ACO) [8],
the Chained Lin-Kernighan heuristic (LKH) [2] and its latest implementation
(LKH2) [13]. We ran each algorithm 10, 000 times on every instance of the
eil76 series of the TTP benchmark suite [22]. We computed 100 (capped due to
practical reasons) distinct tours by INV, 25 by CON, 24 by the both ACO and
LKH, and 12 by LKH2. The lengths of the tours generated by INV are narrowly
distributed around the average of 588.64 with the standard deviation being 2.55.
By contrast, every other algorithm generates tours having the identical tour
length of 585, which beats INV.

Total Reward

10000
8000
6000
4000
2000
0

ACO_Bounded01
CON_Bounded01
INV_Bounded01
LKH_Bounded01
LKH2_Bounded01
ACO_Bounded06
CON_Bounded06
INV_Bounded06
LKH_Bounded06
LKH2_Bounded06
ACO_SimilarWeights01
CON_SimilarWeights01
INV_SimilarWeights01
LKH_SimilarWeights01
LKH2_SimilarWeights01
ACO_SimilarWeights06
CON_SimilarWeights06
INV_SimilarWeights06
LKH_SimilarWeights06
LKH2_SimilarWeights06
ACO_Uncorrelated01
CON_Uncorrelated01
INV_Uncorrelated01
LKH_Uncorrelated01
LKH2_Uncorrelated01
ACO_Uncorrelated06
CON_Uncorrelated06
INV_Uncorrelated06
LKH_Uncorrelated06
LKH2_Uncorrelated06

-2000

Figure 1: Exploring diversity of TSP tours on the eil76 n75 series of the TTP
instances.
We then applied the DP to every tour produced by each of the algorithms.
Figure 1 depicts the resulted rewards on some sample TTP instances, where each
box with whiskers reports the distribution of the rewards for a certain instance
and the corresponding algorithm. The central mark of each box indicates the
median of rewards, and the bottom and top edges of the box indicate the 25th
and 75th percentiles, respectively. The whiskers extend to the most extreme
rewards without considering outliers, and outliers are plotted individually as
plus signs. From the plot, we may observe that the tours generated by the CON,
ACO, LKH and LKH2 have similar distributions of rewards. By contrast, the

6

boxes of INV seem to be more extreme on the both sides. This means that
the distribution of rewards via INV is more diverse and the best of the rewards
outperform the others. In other words, though the Inver-over heuristic may lose
against modern TSP approaches, it performs better in the role of generator of
varied tours for the TTP. It may act as a seeding algorithm for a population in
evolutionary algorithms.
In Figure 2, we visualise the collection of the DP fronts produced by the DP
on the TTP instance eil76 n75 uncorr 01 [22]. The corresponding tours are the
100 tours generated by the Inver-over heuristic. Actually, the plot depicts 200
fronts since the DP was applied to a tour and its reversed order.

Total Reward

5000

Max reward:4791.466 Corresponding tour length:586

0

-5000
0

1000

2000

3000

4000

Weight
Figure 2: The visualisation of 200 DP fronts, generated according to 100 TSP
tours produced by Inver-over for the TTP instance eil76 n75 uncorr 01.

Definition 2 Given n DP fronts τ1 , . . . , τn , let Φ denote a union of the fronts
as Φ = ∪ni=1 τi . Then a subset ω ⊆ Φ is the Pareto front of Φ called as the
surface of Φ.
The surface ω is formed by the union of all superior points resulted from
different DP fronts in Φ. It is further used to guide evolution process in our
approach.

4

A hybrid evolutionary approach

Multi-objective optimisation algorithms guided by evolutionary mechanisms explore the decision space iteratively in order to determine a set of Pareto-optimal
solutions. Indeed, many of them may act myopically as they sample the space
7

searching for individual solutions without clear vision of the whole picture in
terms of other solutions and their number. Therefore, achieving strong diversity in exploring the space plays an important role in evolutionary algorithm
design. In this paper, we discuss one way to overcome potential issues related
to diversity and propose a hybrid approach where evolutionary techniques and
dynamic programming find synergy in their combination.
One of the challenges of multi-objective optimisation is to keep the wide
spread of solutions, which has to be guaranteed by strong diversity. Modern
approaches normally incorporate additional processes to tackle this, such as the
density estimation and/or crowdedness-comparison operator in SPEA2 [34] and
NSGA-II [7]. In our approach, the DP is incorporated as a subroutine capable
of producing at once a series of possible decisions with regard to a given tour.
Thus, when a tour is specified, the DP guarantees that a corresponding front
will be built without missing any of its points due to the completeness of the
DP front, which thus also guarantees a good spread of solutions.
On the other hand, due to the typically observed non-dominance of single
DP fronts, the global Pareto optimality of the BO-TTP may be formed either
by a single DP front or by the combination of segments from different top
DP fronts. In Figure 2, we may observe that the DP fronts are all intertwined
together, including the ones at the surface of the fronts collection. This seems to
indicate that the Pareto-optimal set of solutions is more likely to be the result
of multiple TSP tours and their DP fronts. We would like our evolutionary
mechanism to take advantage of this and to keep the top DP fronts so as to
improve the population further. In order to achieve this as well as to overcome
the drawback of existing multi-objective evolutionary optimisation algorithms
that focus on individual solutions, we design our hybrid IBEA with particular
indicators and selection mechanisms in orchestrating improvement of Pareto
front guided by the information of the DP fronts for most promising TSP tours.
Our hybrid approach reduces the search space to some extent by decomposing the problem and thus transforming it. Evolutionary optimisation approaches
traditionally depend on the choice of solution encoding (i.e. chromosome). Our
approach treats a single TSP tour as an individual. Thus, a set of tours yields a
population. Indeed, it operates on a reduced set of variables (implying shorter
chromosomes), thus decreasing memory consumption and the number of internally needed sorting operations, comparisons and search operations.
Algorithm 1 sketches the whole approach, which we adopted from the original
IBEA introduced by Zitzler and Künzli [33]. It accepts µ as a control parameter
for the size of the population Π ⊆ Π and α as a limit on the number of iterations,
which defines its termination criterion. In order to utilise the information within
the DP fronts to guide the evolution of individual tours, we design new indicators
to be computed based on the DP fronts instead of directly on the individuals.
Our specific selection mechanisms then filter the individuals according to the
indicator values in order to find the tours with better DP fronts.
The rest of this section first introduces the indicator functions we apply to
TSP solutions. Next, it details a parent selection mechanism to mate existing
individuals from the population. It ends with a discussion of mutation and
8

Algorithm 1 Hybrid IBEA Approach
Input: population size µ; limit on the number of generations α;
Initialisation:
set the iteration counter c = 0;
populate Π with µ new tours produced by the TSP solver;
while (c ≤ α) do
set c = c + 1;
Indicator:
run the DP for every tour π ∈ Π to compute its DP front τ ;
apply indicator function I(τ ) to calculate the indicator value for every individual
tour π ∈ Π;
Survivor Selection:
repeatedly remove the individual with the smallest indicator value from the
population Π until the population size is µ (ties are broken randomly);
Parent Selection:
apply parent selection procedure to Π according to the indicator values to choose
a set Λ of λ parent individuals;
Mating:
apply crossover and mutation operators to the parents of Λ to obtain a child
population Λ0 ;
set the new population as Π = Π ∪ Λ0 ;
end while

crossover operators guiding the search.

4.1

Design of Indicators

The designs of our indicators are based on the idea of measuring how each DP
front contributes to the surface ω of the fronts’ union Φ corresponding to the
population Π. The surface ω introduced in Definition 3.2 is the union of all
best segments from different DP fronts in Φ. Given a DP front τ for a tour
π ∈ Π and a measurement function M of a front, we use the followed formula
to calculate the indicator I:
I(τ ) = 1 −

M(ω \ τ )
.
M(ω)

(3)

This formula measures how much we could lose (expressed as a value from 0 to
1) if we did not include the segments of the front τ to the surface ω, i.e. ω \ τ .
In the following, we study two types of the measurement functions: Surface
Contribution (SC) and Hypervolume (HV), hence two corresponding indicators:
the Loss of Surface Contribution (LSC) and the Loss of Hypervolume (LHV).
Loss of Surface Contribution. Our first indicator is Surface Contribution
(SC), which is a novel and direct measure. Given the union of a set of fronts
Φ, a front τ ⊆ Φ and the surface ω ⊆ Φ, SC(τ ) counts the number of objective

9

vectors that τ contributes to ω, as defined by:
SC(τ ) =

|ω ∩ τ |
.
|ω|

(4)

Using SC (4) to replace the M function in (3), we have the formula of LSC as
follows:
LSC(τ ) = 1 − SC(ω \ τ ).
Loss of Hypervolume. In multi-objective optimisation, the hypervolume
indicator is a traditional indicator used to indicate the quality of a set of objective vectors [35]. In the bi-criteria case, when a front is given as a set of points
in two-dimensional space, its value is computed as a sum of areas of rectangular
regions.
Let (0, C) be the reference point for our problem, which implies that only
the range of non-negative objective values is taken into account. In addition,
let p = (u, v) ∈ τ be a bi-dimensional objective vector in a DP front τ while
u > 0 and v < C, HV (τ ) calculates the hypervolume for τ as:
X
HV (τ ) =
up (vp − vp−1 )
p∈τ

Putting HV (τ ) back to (3), we have the loss of hypervolume LHV (τ ) computed
as
HV (ω \ τ )
.
LHV (τ ) = 1 −
HV (ω)

4.2

Parent Selection Mechanisms

With the individuals in the population Π being measured by the defined indicators, we can study strategies that shall efficiently select good individuals. There
are five parent selection schemes that we take into consideration due to their
popularity or previous theoretical findings. In comparison, we introduce two
simple and arbitrary selections as well as a traditional policy to be a baseline.
In this study, we expect to find a well-performing combination of indicator and
selection to encourage the synergy of the DP and evolutionary approach.
Rank-based Selection (RBS). In the rank-based selection policy, individuals are first ranked with respect to the value of an indicator. The selection
policy is based then on a specific distribution law affecting the choice of a parent. Here, we study three schemes introduced by Osuna, Gao, Neumann, and
Sudholt [21], namely exponential (EXP), inverse quadratic (IQ) and Harmonic
(HAR), and make them a part of our hybrid approach. Given a population of
size µ, the probability of selecting the ith ranked individual according to EXP,
IQ and HAR is, respectively,
i−2
i−1
2−i
Pµ
P
P
,
,
.
µ
µ
−j
−
−1
j=1 2
j=1 j 2
j=1 j
10

(5)

Fitness-Proportionate Selection (FPS). This rule estimates an individual π ∈ Π according to the indicator I(τ ) of its DP front τ . It has the following
form:
I(τi )
F P S (πi ) = Pµ
.
j=1 I(τj )

(6)

Tournament Selection (TS). This policy applies the tournament selection [19], but employs indicators discussed in Section 4.1 to rank individuals.
Arbitrary Selection (AS). Here, we consider two different rules: the best
arbitrary selection (BST) and another one, which we call extreme (EXT). The
former ranks individuals of a population with accordance to the value of an indicator and selects the best half of the population. The latter proceeds similarly
selecting 25% of the best and 25% of the worst individuals.
Uniformly-at-random Selection (UAR). This traditional policy selects
a parent from a population with probability µ1 uniformly at random.

4.3

Mutation and Crossover Operators

In our approach, we adopt a multi-point crossover operator that has already
proved its efficiency for the TTP in [9]. As an (un-optimised) rule, we perform
the crossover operation on a tour with 80% probability. It is always followed by
the mutation procedure, which either applies the classical 2OPT mutation [6]
or re-inserts a node to another location. Both the node and the location are
selected uniformly at random. We name these two operators 2OPT and JUMP,
respectively.

5
5.1

Computational Experiments
Computational Set Up

We examine the IBEA presented in Algorithm 1 by going through each of the
two indicators and the eight parent selections, resulting in a total of 16 settings.
For example, FPS on LHV means the combination of the FPS selection and the
LHV indicator.
From the original set of TTP instances, we use three different types, namely
bounded-strongly-correlated (Bounded ), uncorrelated (Uncorrelated ) and uncorrelated-with-similar-weights (SimilarWeights), selected from three instance
series: eil51, eil76, eil101 in the TTP benchmark [22]. We run our approach
30 times repetitively on each selected instance. Each time, the algorithm runs
20,000 generations on a population Π in size of 50.
Due to the significant computing cost, our experiments run on the supercomputer in our university, which consists of 5568 Intel(R) Xeon(R) 2.30GHz
CPU cores and 12TB of memory. Overall the experiments consumed around
170,000 CPU-hours.

11

5.2

Results and Analysis

To compare the outcomes of the different approaches based on the final populations Π of tours, we calculate the hypervolumes for the surface of resulting
non-dominated solutions. We also store the corresponding total reward in order
to compare with the results from the state-of-the-art single-objective approach:
MA2B [9] (see comparison in [28]).
However, due to the varied mean values and unknown global optima of
different TTP instances, it is hard to analyse and compare across instances.
Nevertheless, such a comparison is desired because such analysis or comparison
may provide a more general view for our algorithm. We design a statistical
comparison to overcome this as follows. Firstly, we choose the uniformly-atrandom (UAR) selection as the baseline, which creates two baseline settings,
namely UAR on LHV and UAR on LSC. We secondly conduct Welch’s t-test [29]
between the results of the others and the baselines for two indicators respectively.
The results of the t-test are probability values (p-values), each of which measures the likelihood of one selection to the corresponding baseline with respect
to their performance. For example, we have the p-value being 4.75 × 10−7 in
the case of comparing the hypervolume of the FPS and the UAR on LHV. This
means that the probability of the FPS performing identical to the UAR on LHV
(as expressed by having the same means) is less than 0.0000475%. In fact, the
former performs much better than the latter on average. In order to improve the
readability, we use the logarithm of the p-value in our plots. Thus, the measure
of the FPS on LHV in our little example is 6.32 (i.e. log10 (4.75 × 10−7 )). In
short, the larger the logarithmic p-value is, the better the selection is against
the UAR.
Figure 3 depicts the overall results of the Welch’s t-test, in which we categorise our results into three types of bars according to three types of TTP
instances: Bounded, Uncorrelated and SimilarWeights. Each bar in the plots
represents the mean of the logarithmic p-values of several instances in this category, for example eil51 n50 bounded-strongly-corr 01.ttp, eil76 n75 boundedstrongly-corr 01.ttp and eil101 n100 bounded-strongly-corr 01.ttp. From it we
may observe distinguishable patterns between the selections running on the
LHV and the LSC respectively. For example, the three rank-based selection
(RBS) schemes generally perform better on LHV than on LSC, among which
the HAR is the best. According to the definitions, the HAR is the least aggressive scheme among the three, with a fat tail and relatively small probability for
selecting the best few individuals [21]. It seems to imply that the LHV benefits more from the diversity of candidates. By contrast, the AS-BST performs
best on LSC, which might imply that the LSC relies more on a few outstanding
individuals for approximating, as the AS-BST only focuses on the best ones.
In terms of different types of TTP instances, we may observe that the IBEA
performs best on the uncorrelated instances in all of the settings, while being
worst on the strongly bounded ones in most of the settings. This to some
extent supports the conjecture that strongly bounded TTP instances are the
(relatively) hard ones and uncorrelated instances are the easy ones [22].

12

30
25
20

Bounded

15

SimilarWeights

10

Uncorrelated

5
0
AS-BST

AS-EXT

FPS

RBS-EXP

RBS-HAR

RBS-IQ

TS

(a) Hypervolume of each selection on LHV
25
20
15

Bounded

10

SimilarWeights
Uncorrelated

5
0
AS-BST

AS-EXT

FPS

RBS-EXP

RBS-HAR

RBS-IQ

TS

(b) Hypervolume of each selection on LSC
30
25
20

Bounded

15

SimilarWeights

10

Uncorrelated

5
0
AS-BST

AS-EXT

FPS

RBS-EXP

RBS-HAR

RBS-IQ

TS

(c) Total Reward of each selection on LHV
25
20
15

Bounded

10

SimilarWeights
Uncorrelated

5
0
AS-BST

AS-EXT

FPS

RBS-EXP

RBS-HAR

RBS-IQ

TS

(d) Total Reward of each selection on LSC

Figure 3: The sum of the logarithm of the p-values of performing Welch’s t-test
for the selections each respectively against the UAR selection.

13

With regard to the choice of the parent selections, besides the RBS-HAR
and the AS-BST which perform best on LHV and LSC respectively, we would
like to recommend the FPS as well. This selection seems to be the safest choice,
as it performs consistently well on different settings.
Overall, we may observe from Figure 3 that the figures of the hypervolume
generally agree with those of the total reward. This somewhat suggests that
optimising the bi-objective TTP brings good results for the single objective
TTP as well. Table 1 presents the total rewards we get by optimising the
BO-TTP, in comparison with the state-of-art algorithm of the single objective
TTP, namely MA2B [9]. We run the MA2B with the time limits identical to our
approach. The results show that in the majority of the test cases, our approach
preforms better.

6

Conclusion

In this paper, we investigated a new bi-objective travelling thief problem which
optimises both the total reward and the total weight. We proposed a hybrid
indicator-based evolutionary algorithm (IBEA) that utilises the exact dynamic
programming algorithm for the underlying PWT problem as a subroutine to
evolve the individuals. This approach guarantees the spread of solutions without introducing additional spread mechanisms. We furthermore designed and
studied novel indicators and selection schemes that take advantage of the information in the Pareto fronts generated by the exact approach for evolving
solutions towards the global Pareto optimality. Our results show that this approach solves the problem well, because its by-products, which are the results for
the single-objective travelling thief problem, beat the state-of-the-art approach
single-objective approaches.

Acknowledgements
The authors were supported by Australian Research Council grants DP130104395,
DP140103400, and DE160100850.

14

eil51 n50

eil76 n75

eil101 n100

eil51 n50

eil76 n75

eil101 n100

eil51 n50

eil76 n75

eil101 n100

MA2B
Mean
Uncorrelated
2805.000
SimilarWeights 1416.348
Bounded
4057.652
Uncorrelated
5275.067
SimilarWeights 1398.867
Bounded
3849.067
Uncorrelated
3339.600
SimilarWeights 2215.500
Bounded
4949.000
FPS LHV
Mean
Uncorrelated
2828.728
SimilarWeights 1413.044
Bounded
4229.149
Uncorrelated
5445.624
SimilarWeights 1477.680
Bounded
4042.449
Uncorrelated
3620.844
SimilarWeights 2431.907
Bounded
5094.246
FPS LSC
Mean
Uncorrelated
2810.509
SimilarWeights 1426.135
Bounded
4231.299
Uncorrelated
5392.575
SimilarWeights 1474.803
Bounded
4054.815
Uncorrelated
3664.369
SimilarWeights 2436.374
Bounded
5067.070

Max
2855
1460
4105
5423
1502
4109
3789
2483
5137

SD
27.814
47.906
25.841
78.138
55.448
139.742
388.360
235.905
139.285

Max
2854.543
1459.953
4230.997
5514.666
1513.404
4108.760
3943.425
2482.462
5233.513

SD
15.357
17.780
10.118
58.992
24.494
38.805
222.815
52.265
65.267

Max
2832.496
1459.953
4241.199
5514.666
1513.404
4102.167
3846.172
2482.462
5233.513

SD
18.076
21.990
1.881
73.029
21.346
21.440
124.994
49.731
55.587

Table 1: Comparison of the total reward between running the state-of-art approach MA2B and the IBEA with the selection being FPS and the indicator
being LHV and LSC respectively. Each approach runs 30 times on the TTP
instances. Highlighted are the results that are better than MA2B.

15

References
[1] David
Applegate,
Ribert
Bixby,
Vasek
Chvatal,
William Cook. 2005.
Concorde tsp solver, 2006.
http://www.math.uwaterloo.ca/tsp/concorde.html (2005).

and
See:

[2] David Applegate, William J. Cook, and André Rohe. 2003. Chained LinKernighan for Large Traveling Salesman Problems. INFORMS Journal on
Computing 15, 1 (2003), 82–92. https://doi.org/10.1287/ijoc.15.1.
82.15157
[3] Julian Blank, Kalyanmoy Deb, and Sanaz Mostaghim. 2017. Solving
the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms. Springer International Publishing, Cham, 46–60. https:
//doi.org/10.1007/978-3-319-54157-0_4
[4] Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone. 2013.
The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In Proceedings of the IEEE Congress
on Evolutionary Computation, CEC 2013, Cancun, Mexico, June 20-23,
2013. 1037–1044.
[5] Mohammad Reza Bonyadi, Zbigniew Michalewicz, Michal Roman Przybylek, and Adam Wierzbicki. 2014. Socially Inspired Algorithms for the
Travelling Thief Problem. In Proceedings of the 2014 Annual Conference
on Genetic and Evolutionary Computation (GECCO ’14). ACM, 421–428.
[6] Georges A Croes. 1958. A Method for Solving Traveling-Salesman Problems. Operations Research 6, 6 (1958), 791–812. https://doi.org/10.
1287/opre.6.6.791
[7] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. 2002.
A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans.
Evolutionary Computation 6, 2 (2002), 182–197. https://doi.org/10.
1109/4235.996017
[8] Marco Dorigo and Thomas Stützle. 2004. Ant colony optimization. MIT
Press.
[9] Mohamed El Yafrani and Belaı̈d Ahiod. 2016. Population-based vs. Singlesolution Heuristics for the Travelling Thief Problem. In Proceedings of the
Genetic and Evolutionary Computation Conference 2016 (GECCO ’16).
ACM, 317–324.
[10] Mohamed El Yafrani and Belad Ahiod. 2017. A local search based approach
for solving the Travelling Thief Problem: The pros and cons. Applied Soft
Computing 52, Supplement C (2017), 795 – 804. https://doi.org/10.
1016/j.asoc.2016.09.047

16

[11] Mohamed El Yafrani, Marcella Martins, Markus Wagner, Belaı̈d Ahiod,
Myriam Delgado, and Ricardo Lüders. 2017. A hyperheuristic approach
based on low-level heuristics for the travelling thief problem. Genetic Programming and Evolvable Machines (15 7 2017). https://doi.org/10.
1007/s10710-017-9308-x
[12] Hayden Faulkner, Sergey Polyakovskiy, Tom Schultz, and Markus Wagner. 2015. Approximate Approaches to the Traveling Thief Problem. In
Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO ’15). ACM, New York, NY, USA, 385–392.
https://doi.org/10.1145/2739480.2754716
[13] Keld Helsgaun. 2000. An effective implementation of the Lin-Kernighan
traveling salesman heuristic. European Journal of Operational Research
126, 1 (2000), 106–130. https://doi.org/10.1016/S0377-2217(99)
00284-2
[14] Nuno Lourenço, Francisco B. Pereira, and Ernesto Costa. 2016. An Evolutionary Approach to the Full Optimization of the Traveling Thief Problem.
Springer International Publishing, Cham, 34–45. https://doi.org/10.
1007/978-3-319-30698-8_3
[15] Marcella S. R. Martins, Mohamed El Yafrani, Myriam R. B. S. Delgado,
Markus Wagner, Belaı̈d Ahiod, and Ricardo Lüders. 2017. HSEDA: A
Heuristic Selection Approach Based on Estimation of Distribution Algorithm for the Travelling Thief Problem. In Proceedings of the Genetic and
Evolutionary Computation Conference (GECCO ’17). ACM, New York,
NY, USA, 361–368.
[16] Yi Mei, Xiaodong Li, Flora Salim, and Xin Yao. 2015. Heuristic evolution with Genetic Programming for Traveling Thief Problem. In IEEE
Congress on Evolutionary Computation, CEC 2015, Sendai, Japan, May
25-28, 2015. 2753–2760. https://doi.org/10.1109/CEC.2015.7257230
[17] Yi Mei, Xiaodong Li, and Xin Yao. 2014. Improving Efficiency of Heuristics for the Large Scale Traveling Thief Problem. In Simulated Evolution
and Learning - 10th International Conference, SEAL 2014, Dunedin, New
Zealand, December 15-18, 2014. Proceedings. 631–643. https://doi.org/
10.1007/978-3-319-13563-2_53
[18] Yi Mei, Xiaodong Li, and Xin Yao. 2016. On investigation of interdependence between sub-problems of the Travelling Thief Problem. Soft Comput.
20, 1 (2016), 157–172. https://doi.org/10.1007/s00500-014-1487-2
[19] Brad L. Miller and David E. Goldberg. 1995. Genetic Algorithms, Tournament Selection, and the Effects of Noise. Complex Systems 9, 3 (1995).
http://www.complex-systems.com/abstracts/v09_i03_a02.html

17

[20] Frank Neumann, Sergey Polyakovskiy, Martin Skutella, Leen Stougie, and
Junhua Wu. 2017. A Fully Polynomial Time Approximation Scheme for
Packing While Traveling. CoRR abs/1702.05217 (2017). arXiv:1702.05217
http://arxiv.org/abs/1702.05217
[21] Edgar Covantes Osuna, Wanru Gao, Frank Neumann, and Dirk Sudholt. 2017. Speeding up evolutionary multi-objective optimisation through
diversity-based parent selection. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July
15-19, 2017. 553–560.
[22] Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew
Michalewicz, and Frank Neumann. 2014. A comprehensive benchmark set
and heuristics for the traveling thief problem. In Genetic and Evolutionary
Computation Conference, GECCO ’14, Vancouver, BC, Canada, July 1216, 2014. 477–484.
[23] Sergey Polyakovskiy and Frank Neumann. 2017. The Packing While Traveling Problem. European Journal of Operational Research 258, 2 (2017),
424–439. https://doi.org/10.1016/j.ejor.2016.09.035
[24] Jacob Stolk, Isaac Mann, Arvind Mohais, and Zbigniew Michalewicz. 2013.
Combining vehicle routing and packing for optimal delivery schedules of
water tanks. OR Insight 26, 3 (2013), 167–190. https://doi.org/10.
1057/ori.2013.1
[25] Anna Strzeżek, Ludwik Trammer, and Marcin Sydow. 2015. DiverGene:
Experiments on controlling population diversity in genetic algorithm with
a dispersion operator. In 2015 Federated Conference on Computer Science and Information Systems (FedCSIS). 155–162. https://doi.org/
10.15439/2015F411
[26] Guo Tao and Zbigniew Michalewicz. 1998. Inver-over Operator for the
TSP. In Parallel Problem Solving from Nature - PPSN V, 5th International Conference, Amsterdam, The Netherlands, September 27-30, 1998,
Proceedings. 803–812.
[27] Markus Wagner. 2016. Stealing Items More Efficiently with Ants: A Swarm
Intelligence Approach to the Travelling Thief Problem. In Swarm Intelligence: 10th International Conference, ANTS 2016, Brussels, Belgium,
September 7-9, 2016, Proceedings, Marco Dorigo, Mauro Birattari, Xiaodong Li, Manuel López-Ibáñez, Kazuhiro Ohkura, Carlo Pinciroli, and
Thomas Stützle (Eds.). Springer, 273–281.
[28] Markus Wagner, Marius Lindauer, Mustafa Mısır, Samadhi Nallaperuma,
and Frank Hutter. 2017. A case study of algorithm selection for the
traveling thief problem. Journal of Heuristics (07 Apr 2017). https:
//doi.org/10.1007/s10732-017-9328-y

18

[29] Bernard L Welch. 1947. The Generalization of ‘Student’s’ Problem when
Several Different Population Variances are Involved. Biometrika 34, 1/2
(1947), 28–35. http://www.jstor.org/stable/2332510
[30] Junhua Wu, Markus Wagner, Sergey Polyakovskiy, and Frank Neumann.
2017. Exact Approaches for the Travelling Thief Problem. In Simulated
Evolution and Learning - 11th International Conference, SEAL 2017, Shenzhen, China, November 10-13, 2017, Proceedings. 110–121.
[31] Mohamed El Yafrani and Belaı̈d Ahiod. 2018. Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing. Information Sciences 432 (2018), 231–244. https://doi.org/10.1016/j.ins.
2017.12.011
[32] Mohamed El Yafrani, Shelvin Chand, Aneta Neumann, Belaı̈d Ahiod, and
Markus Wagner. 2017. Multi-objectiveness in the Single-objective Traveling
Thief Problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ’17). ACM, New York, NY, USA,
107–108. https://doi.org/10.1145/3067695.3076010
[33] Eckart Zitzler and Simon Künzli. 2004. Indicator-Based Selection in Multiobjective Search. In Parallel Problem Solving from Nature - PPSN VIII,
8th International Conference, Birmingham, UK, September 18-22, 2004,
Proceedings. 832–842.
[34] Eckart Zitzler, Marco Laumanns, and Lothar Thiele. 2001. SPEA2:
Improving the strength Pareto evolutionary algorithm. TIK-report 103
(2001).
[35] Eckart Zitzler and Lothar Thiele. 1998. Multiobjective Optimization Using
Evolutionary Algorithms - A Comparative Case Study. In Parallel Problem
Solving from Nature - PPSN V, 5th International Conference, Amsterdam,
The Netherlands, September 27-30, 1998, Proceedings. 292–304.

19

