arXiv:1603.07051v1 [cs.AI] 23 Mar 2016

Cosolver2B: An Efficient Local Search Heuristic for
the Travelling Thief Problem
Mohamed El Yafrani

Belaı̈d Ahiod

LRIT, associated unit to CNRST (URAC 29)
Faculty of Science, Mohammed V University of Rabat
B.P. 1014 Rabat, Morocco
Email: m.elyafrani@gmail.com

LRIT, associated unit to CNRST (URAC 29)
Faculty of Science, Mohammed V University of Rabat
B.P. 1014 Rabat, Morocco
Email: ahiod@fsr.ac.ma

Abstract—Real-world problems are very difficult to optimize.
However, many researchers have been solving benchmark problems that have been extensively investigated for the last decades
even if they have very few direct applications. The Traveling Thief
Problem (TTP) is a NP-hard optimization problem that aims to
provide a more realistic model. TTP targets particularly routing
problem under packing/loading constraints which can be found in
supply chain management and transportation. In this paper, TTP
is presented and formulated mathematically. A combined local
search algorithm is proposed and compared with Random Local
Search (RLS) and Evolutionary Algorithm (EA). The obtained
results are quite promising since new better solutions were found.

I. I NTRODUCTION
The travelling thief problem (TTP) is a novel NP-hard
problem introduced in [1] to provide a model that better
represents real-world problems. The particularity of TTP is
that it is composed of two other NP-hard problems, namely
the travelling salesman problem and the knapsack problem,
which are interdependent.
The problem can be introduced with the following simplified statement:
”Given n cities and m items scattered among these cities, a
thief with his rented knapsack should visit all n cities, once
and only once each, and pick up some items. The more the
knapsack gets heavier, the more the thief becomes slower. What
is the best path and picking plan to adopt to achieve the best
benefit ?”.
Two particular properties can be extracted from the statement above. First, the overall problem is composed of two
sub-problems: choosing the best path and picking up the most
profitable items. Second, the sub-problems are interdependent:
when the knapsack gets heavier, the speed of the thief decreases. The composition increases the number of possible
solutions, and the interdependence makes it impossible to
isolate sub-problems.
This kind of multiple interdependent components is widely
found in logistics and supply chain management. Nevertheless, few attempts have been made to study and solve these
problems as a whole, and a lot of effort have been made to
solve the components independently. In [3], the authors explain

why there is a gap between the work done by the Evolutionary Computation researchers and real-world applications. As
far as we know, these observations can be extended to all
metaheuristics community.
Examples of other realistic problems with multiple interdependent sub-problems include most supply chain optimization
problems [7], [8], routing problems with loading constraints
such as 2L-CVRP and 3L-CVRP [9], [10], [3], and water tank
delivery [14].
Since TTP was introduced, some algorithms were proposed
to solve it. An Evolutionary Algorithm and a Random Local
Search were proposed in [13] to provide a starting point to
other researchers. In [2], an approach named Cosolver was
introduced to solve TTP by separating the sub-problems and
managing a communication between them. Lastly, an interesting work on TTP introduces many complexity reduction
techniques in order to solve very large instances in a time
budget of 10 minutes [11].
In this paper, we follow the ideas proposed in [2] and [11]
to propose further improvements and introduce an algorithm
based on the Cosolver framework that can solve TTP instances
efficiently.
This paper is organized as follows. In section II TTP is
mathematically defined and investigated. Section III is dedicated to introduce our approach for solving TTP. The tests and
results are presented in section IV. Section V concludes the
paper and outlines areas for future research.
II. BACKGROUND
In this section, we present some background information
about TTP. The problem is formulated and an abstract algorithm is presented.
A. The Travelling Thief Problem
Herein we formulate the Travelling Thief Problem (TTP)
which combines two other well known benchmark problems,
namely the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP).
In TTP, we consider n cities and the associated distance
matrix {dij }. There are m items scattered in these cities, each
item k have a profit pk and a weight wk . A thief with his
knapsack is going to visit all these cities (once and only once

978-1-5090-0478-2/15/$31.00 c 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any
current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or
redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

each), and pick up some items to fill his knapsack. We note
W the maximum capacity of the knapsack, vmin and vmax are
the minimum and maximum possible velocity respectively.
Also, we consider also the following constraints and parameters:
•

•

•

Each item is available in only one city. We note {Ai } the
availability vector, Ai ∈ {1, ..., n} contains the reference
to the city that contains the item i.
We suppose that the knapsack is rented. We note R the
renting price per time unit.
The velocity of the thief changes accordingly to the
knapsack weight. We note vxi the velocity of the thief
at city xi (see equation 1).
vxi = vmax − C ∗ wxi

(1)

−vmin
where C = vmaxW
is a constant value, and wxi
represents the weight of the knapsack at city xi .

The goal of the problem is to find the tour x and the picking
plan z that optimize the total travel gain defined in equation
2.
G(x, z) = g(z) − R ∗ f (x, z)
(2)
P
Where g(z) = m pm ∗ zm is the total value of the items
Pn−1
P
subject to m wm ∗ zm ≤ W , and f (x, z) = i=1 txi ,xi+1 +
txn ,x1 is the total travel time.
The solutions could be naturally coded as follows. The tour
x = (x1 , ..., xn ) is a vector containing the ordered list of cities,
and the picking plan z = (z1 , ..., zn ) is a binary vector such
as zi is equal to 1 if the item i is picked, 0 otherwise.
The interdependence between KP and TSP have been investigated. As shown in [1], [11], optimizing the sub-problems
in isolation (even to optimality) does not guarantee finding
good solutions for the overall problem. Therefore, finding good
global solutions requires an algorithm that takes interdependence of components in consideration, which makes the design
of such an algorithm quite difficult.
B. Cosolver
Cosolver is an abstract algorithm proposed in [2] to solve
TTP. The idea behind the algorithm is simple. Decompose
the overall problem and solve components separately using a
fitness function that takes in consideration the interdependence
between the two components.
Thus, given an initial solution (x0 , z0 ), TTP is decomposed
into the following problems.
1) The Travelling Salesman with Knapsack Problem
(TSKP): consists of finding the best tour x′ that, combined
with the last found picking plan z ′ , optimizes the TTP objective function G. Also, because the total profit function g
does not depend on the tour, instead of maximizing G, we
can consider minimizing the total travel cost T (see equation
3).
T (x, z) = R ∗ f (x, z)

(3)

2) The Knapsack on the Route Problem (KRP): consists of
finding the best picking plan z ′ that maximizes the total gain
G when combined with the last found tour x′ .
Figure 1 represents a flowchart of the Cosolver framework.
III. P ROPOSED

APPROACH

In this section, we propose an algorithm that implements
the Cosolver framework and uses some techniques proposed
in [11].
A. Solution initialization
In TTP, the initial solution has a big impact on the search
algorithm. Thus, the initialization strategy should be chosen
carefully. In our implementation, we use a heuristic approach
to initialize both the tour and the picking plan.
Firstly, the tour is generated using a good TSP algorithm
such as the Lin-Kernighan heuristic [6] or the Ant Colony
Optimization algorithm [5].
Then, the picking plan is initialized using the following
approach.
1) The insertion heuristic proposed in [11] is used to
fill the knapsack with items according to three fitness
approximations.
2) A simple bit-flip search on inserted items is performed
to eliminate some useless items from the picking plan
using the objective function.
We will refer to this heuristic as the insertion & elimination
heuristic.
B. Complexity reduction techniques
Our algorithm uses the following complexity reduction
techniques.
1) TSKP neighborhood reduction: The Delaunay triangulation [4] is used as a candidate generator for the 2-OPT
heuristic. This strategy was also proposed in [11].
2) Objective value recovery: Instead of using the objective
function to calculate the objective value of neighbors, this
value can be recovered by keeping track of time and weight
information at each tour’s city. The following vectors are used
to perform such operation.
acc
• Time accumulator (t
): a vector that contains the current
time at each city of the tour.
acc
• Weight accumulator (w
): a vector that contains the
current weight at each city of the tour.
reg
• Time register (t
): a vector that contains the added time
at each city of the tour.
reg
• Weight register (w
): a vector that contains the added
weight at each city of the tour.
Figure 2 shows the effect (in gray) of mutating a TTP
solution on the total travel time. Two mutations are shown
(in black): the one-bit-flip on the picking plan, and a 2-OPT
exchange on the tour.
A similar technique named incremental evaluation was
proposed in [11]. In our implementation, we go further and
use these techniques also to recover the vectors.

Fig. 1.

bit- ip

x(1)

A simplified Cosolver flowchart

x(i)
x(n)

t(1)
t(i-1)

x(1)

2-opt

t(n)
x(j)

x(i)

x(n)

t(1)

t(n)
t(i)

t(j)

Fig. 2. Example of changes that can be applied to a TTP solution (in black)
and its effect on the total traveling time function (in gray)

3) Objective function calculation: The objective function
has a complexity of O(m ∗ n) as proposed in [12], where
m is the number of items and n is the number of cities. The
complexity could be reduced to O(k∗n) where k is the number
of items per city. In the CEC ’2015 competition website 1 ,
the Java implementations already has a reduced complexity
but it uses a technique highly dependent on the TTP instance
generator. We believe that a better way is to class items per
city.
Figure 3 explains this technique using a simple example. In
the example, 4 cities are considered: city 1 contains 4 items (1,
2, 3 and 4), city 2 contains 2 items (5 and 6), city 3 contains
no items, city 4 contains 3 items (7, 8 and 9).
Fig. 4.

Fig. 3.

Data structure for classing items by cities

C. Proposed algorithm
Our heuristic, namely Cosolver2B, is based on local search
algorithms, and it implements the Cosolver framework. In
addition to the techniques presented above, we use the 2-OPT
heuristic to solve TSKP and a bit-flip search to solve the KRP.
The algorithm is summarized in the flowchart in figure 4.
1 http://cs.adelaide.edu.au/

optlog/CEC2015Comp/

Cosolver2B: Cosolver with 2-opt and bit-flip

The algorithm starts with a tour generated using the LinKernighan heuristic. The insertion & elimination heuristic is
then used to initialize the picking plan. The obtained tour
and picking plan are then given to the TSKP optimizer that
tries to improve the current tour using a 2-OPT heuristic.
The resulting tour is combined with the current picking plan
and given to the KRP optimizer that uses a simple bit-flip to
find a decent picking plan. If there is improvement, the new
picking plan is combined with the current tour and given to
the TSKP optimizer. This process is repeated until there is no
improvement.

IV. E XPERIMENTAL RESULTS
We tested our algorithm on 15 TTP instances of various
sizes [13]. The obtained results are compared with RLS and

TABLE I
R ESULTS OF C OSOLVER 2B COMPARED TO EA AND RLS

instance
berlin52 n255 uncorr-similar-weights 05
kroA100 n495 uncorr-similar-weights 05
ch150 n745 uncorr-similar-weights 05
ts225 n1120 uncorr-similar-weights 05
a280 n1395 uncorr-similar-weights 05.ttp
lin318 n1585 uncorr-similar-weights 05
u574 n2865 uncorr-similar-weights 05
dsj1000 n4995 uncorr-similar-weights 05
rl1304 n6515 uncorr-similar-weights 05
fl1577 n7880 uncorr-similar-weights 05
d2103 n10510 uncorr-similar-weights 05
pcb3038 n15185 uncorr-similar-weights 05
fnl4461 n22300 uncorr-similar-weights 05
rl11849 n59240 uncorr-similar-weights 05
usa13509 n67540 uncorr-similar-weights 05
pla33810 n169045 uncorr-similar-weights 05

EA

Cosolver2B

firstfit

Cosolver2B

bestfit

objective

time

objective

RLS
time

objective

time

objective

time

20591
38864
40922
84907
104365
75387
223165
320165
573667
589756
801110
1119168
1477673
2152954
2226676
-9929644

1.28
1.92
2.69
3.82
5.64
6.87
21
47
95
127
214
427
600
600
600
600

20591
38864
40922
84907
104365
75387
223165
320165
573667
589756
801110
1119169
1478963
4328939
5077892
-3158915

0.89
1.06
1.38
1.69
1.84
3.81
5.42
12
21
28
44
101
265
600
600
600

25440
39599
52225
88925
107233
114915
243571
332916
571634
665866
869584
1117659
1220469
1785671
4420300
14887314

0.13
0.21
0.38
0.61
0.88
1.25
5.36
5.95
68
139
357
600
600
600
600
600

26658
39597
53075
89079
112003
114915
253770
332917
586576
684731
869584
1086092
696650
478884
4082169
15085752

0.11
0.27
0.43
0.92
1.09
1.54
6.51
8.44
83
148
389
600
600
600
600
600

EA proposed in the same paper 2 .
We have implemented two versions of Cosolver2B. The first
is best fit (also known as best improvement) which searches
the entire neighborhood on a given iteration and selects the
best neighbor. The second is first fit (also known as first
improvement) which stops the neighborhood search once a
better solution is found.
Since our algorithms are deterministic, one run per instance
is sufficient. The algorithms have a maximum runtime limit
of 600 seconds. Note that our implementation uses the Java
platform, and the tests are performed on a core i3-2370M CPU
2.40GHz machine with 4 GB of RAM, running Linux.
On the other hand, due to their random behavior, 30 runs
per instance were performed using RLS and EA. The tests on
EA and RLS were performed on a different machine (Matlab
2014, core i7 2600 CPU 3.4 GHz, with 4GB of RAM, running
Windows 7). Thus, The runtimes for these algorithms are given
for guidance. Furthermore, in our comparison, we only select
the best found solution for these two algorithms.
The results are reported in table I. Note that the runtimes
are measured with seconds and the best objective values are
made bolder.
The results show that our algorithm was able to find new
better solutions for most tested instances only by combining
local search algorithms. Furthermore, we have made the following observations:
• Cosolver2B surpasses EA and RLS on various TTP sizes.
• The runtime of Cosolver2B is very decent for small and
mid-size instances. However, for very large instances the
runtime is quite high compared to RLS and EA.
2 for

instance files and raw results of RLS and EA, the reader is referred to
https://sites.google.com/site/mohammadrezabonyadi/standarddatabases/travellingthief-problem-data-bases-and-raw-results

•

•

•

Both EA and RLS have an unpredictable behavior, while
Cosolver2B is deterministic and garantees decent solutions for most instances.
For many instances, most optimization runtime and gain
improvement is done on the KRP sub-problem.
The best fit strategy performed better than first fit for
most small and mid-size instances.
V. C ONCLUSION

In this paper, a combined local search heuristic has been
proposed. Our approach is based on the Cosolver framework
and complexity reduction techniques. The experimental results
have shown promising results both in terms of solution quality
and runtime. The good performance of Cosolver2B and the
memetic algorithm MALTS on very large scale instances
[11] proves the importance of making strong assumptions
about the problem domain when dealing with multi-component
problems.
Furthermore, we engage to improve our algorithm in terms
of space exploration and runtime by using more sophisticated
search heuristics.
ACKNOWLEDGMENT
The authors express their gratefulness to the following
persons who have contributed to this work with their useful
comments: Asmae El Ghazi, Aziz Ouaarab, and Mehdi El
Krari.
R EFERENCES
[1] Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone.
The travelling thief problem: the first step in the transition from
theoretical problems to realistic problems. In Evolutionary Computation
(CEC), 2013 IEEE Congress on, pages 1037–1044. IEEE, 2013.

[2] Mohammad Reza Bonyadi, Zbigniew Michalewicz, Michaŏ Roman Przybyŏek, and Adam Wierzbicki. Socially inspired algorithms
for the travelling thief problem. In Proceedings of the 2014 conference
on Genetic and evolutionary computation, pages 421–428. ACM, 2014.
[3] Andreas Bortfeldt. A hybrid algorithm for the capacitated vehicle
routing problem with three-dimensional loading constraints. Computers
& Operations Research, 39(9):2248–2257, 2012.
[4] Boris Delaunay. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie
Matematicheskii i Estestvennyka Nauk, 7(793-800):1–2, 1934.
[5] Marco Dorigo and Luca Maria Gambardella. Ant colonies for the
travelling salesman problem. BioSystems, 43(2):73–81, 1997.
[6] Keld Helsgaun. An effective implementation of the lin–kernighan
traveling salesman heuristic. European Journal of Operational Research,
126(1):106–130, 2000.
[7] Maksud Ibrahimov, Arvind Mohais, Sven Schellenberg, and Zbigniew
Michalewicz. Evolutionary approaches for supply chain optimisation:
part i: single and two-component supply chains. International Journal
of Intelligent Computing and Cybernetics, 5(4):444–472, 2012.
[8] Maksud Ibrahimov, Arvind Mohais, Sven Schellenberg, and Zbigniew
Michalewicz. Evolutionary approaches for supply chain optimisation.
part ii: multi-silo supply chains. International Journal of Intelligent
Computing and Cybernetics, 5(4):473–499, 2012.
[9] Manuel Iori and Silvano Martello. Routing problems with loading
constraints. Top, 18(1):4–27, 2010.
[10] Stephen CH Leung, Zhenzhen Zhang, Defu Zhang, Xian Hua, and
Ming K Lim. A meta-heuristic algorithm for heterogeneous fleet vehicle
routing problems with two-dimensional loading constraints. European
Journal of Operational Research, 225(2):199–210, 2013.
[11] Yi Mei, Xiaodong Li, and Xin Yao. Improving efficiency of heuristics
for the large scale traveling thief problem. In Simulated Evolution and
Learning, pages 631–643. Springer, 2014.
[12] Yi Mei, Xiaodong Li, and Xin Yao. On investigation of interdependence
between sub-problems of the travelling thief problem. Soft Computing,
pages 1–16, 2014.
[13] Sergey Polyakovskiy, Mohammad Reza, Markus Wagner, Zbigniew
Michalewicz, and Frank Neumann. A comprehensive benchmark set
and heuristics for the traveling thief problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Vancouver,
Canada, 2014.
[14] Jacob Stolk, Isaac Mann, Arvind Mohais, and Zbigniew Michalewicz.
Combining vehicle routing and packing for optimal delivery schedules
of water tanks. OR Insight, 26(3):167–190, 2013.

