# GECCO2019 - Bi-objective Traveling Thief Competition¶

The Genetic and Evolutionary Computation Conference (GECCO) presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms, genetic programming, ant colony optimization and swarm intelligence, complex systems (artificial life/robotics/evolvable hardware/generative and developmental systems/artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.

# Motivation¶

Real-world optimization problems often consist of several NP-hard combinatorial optimization problems that interact with each other. Such multi-component optimization problems are difficult to solve not only because of the contained hard optimization problems, but in particular, because of the interdependencies between the different components. Interdependence complicates a decision making by forcing each sub-problem to influence the quality and feasibility of solutions of the other sub-problems. This influence might be even stronger when one sub-problem changes the data used by another one through a solution construction process. Examples of multi-component problems are vehicle routing problems under loading constraints, maximizing material utilization while respecting a production schedule, and relocation of containers in a port while minimizing idle times of ships.

The goal of this competition is to provide a platform for researchers in computational intelligence working on multi-component optimization problems. The main focus of this competition is on the combination of TSP and Knapsack problems. However, we plan to extend this competition format to more complex combinations of problems (that have typically been dealt with individually in the past decades) in the upcoming years.

# News¶

**July 4, 2019**: And the winner is … (The results are shown below)

**June 30, 2019**: One day to go. Last chance for submissions!

**March 21, 2019**: Prize money - the winner(s) of the competition will receive a cash prize of AUD 400 (sponsored by Markus Wagner)

**March 18, 2019**: Leaderboard was created. From now on every submission will be reflected.

**Feb 20, 2019**: We are happy to announce the competition started. Submissions will be accepted until **June 30, 2019, Midnight, UTC-12**.

# Leaderboard¶

**FINAL**

And the winner is

HPI

Tobias Friedrich, Philipp Fischbeck, Lukas Behrendt, Freya Behrens, Rachel Brabender, Markus Brand, Erik Brendel, Tim Cech, Wilhelm Friedemann, Hans Gawendowicz, Merlin de la Haye, Pius Ladenburger, Julius Lischeid, Alexander Löser, Marcus Pappik, Jannik Peters, Fabian Pottbäcker, David Stangl, Daniel Stephan, Michael Vaichenker, Anton Weltzien, Marcus Wilhelm.

Congratulations!

The 2nd place is taken by team JoMar and the 3rd place by team NTGA and SSteam. We have received submissions from 13 teams in total. Two submissions were invalid and are therefore not shown in the evaluation. We like to thank all participants for the effort made to investigate the traveling thief problem. We hope you have enjoyed implementing new ideas and having contributed to this competition!

One comment about the leaderboard:

We would like encourage you to submit whenever you found some improvements of your algorithm. By doing this, we can out the most of this competition. By knowing better solutions for test instances are available all participants are able to find out possible weaknesses of their algorithms and can work on it before the deadline has passed. This allows everybody to continuously work on their implementation. Pursuing the strategy of keeping good results confidential as long as possible, slows down the overall development and harms the progress in this research field.

Whenever we receive a submission, we will execute the evaluation procedure. Since the estimated ideal and nadir point might change, the relative Hypervolume can change as well (even though your submission is the same). We will make the achieved objective values for each instance publicly available, but not the design space values (tour and packing plan). The reason is that we do not like all participants to execute local searches on the result of other submissions.

**Submissions received:**

JoMar - Jonatas Batista Costa das Chagas, Marcone Jamilson Freitas Souza

shisunzhang - Jialong Shi, Jianyong Sun, Qingfu Zhang

ALLAOUI - Mohcin Allaoui, Belaid Ahiod

faria - Gilson Faria

HPI - Philipp Fischbeck et al.

NTGA - Maciej Laszczyk, Pawel Myszkowski

SSteam - Roberto Santana, Siddhartha Shakya

SamirO-ETF-ba - Samir Omanovic

FRA - Lukas Atkinson, Samuel D’Aprea, Nils Jorek

sinc - Matías Gerard, Leandro Vignolo

JG - Julia Garbaruk

MicroGA - Gregorio Toscano, David Tovias

ValAurTeam - Valeriu Motroi

The step by step evaluation is available here. The objective values of each submissions (the mapping between tours/packing plans and objectives values has been checked for correctness) are available here.

The current overall ranking is:

Rank | Team | Points |
---|---|---|

1 | HPI | 26 |

2 | jomar | 14 |

3 | NTGA | 5 |

SSteam | 5 | |

4 | ALLAOUI | 2 |

shisunzhang | 2 | |

5 | FRA | 0 |

JG | 0 | |

SamirO-ETF-ba | 0 | |

faria | 0 | |

sinc | 0 |

The ranking is calculated as described. The results for each test instance for each participant is shown below:

Problem | Team | Hypervolume | Estimated Ideal Point | Estimated Nadir Point |
---|---|---|---|---|

a280_n279 | HPI | 0.8984 | (2613.0, -42036.0) | (5444.0, -0.0) |

jomar | 0.8956 | |||

shisunzhang | 0.8866 | |||

NTGA | 0.8837 | |||

ALLAOUI | 0.8735 | |||

SSteam | 0.8706 | |||

faria | 0.6026 | |||

SamirO-ETF-ba | 0.5385 | |||

sinc | 0.3775 | |||

FRA | 0.2256 | |||

JG | 0.1663 | |||

a280_n1395 | HPI | 0.8259 | (2613.0, -489194.0) | (6573.0, -0.0) |

jomar | 0.8217 | |||

shisunzhang | 0.8209 | |||

NTGA | 0.8115 | |||

ALLAOUI | 0.809 | |||

SSteam | 0.7871 | |||

faria | 0.7595 | |||

SamirO-ETF-ba | 0.4921 | |||

sinc | 0.2634 | |||

JG | 0.1088 | |||

FRA | 0.107 | |||

a280_n2790 | jomar | 0.8879 | (2613.0, -1375443.0) | (6646.0, -0.0) |

HPI | 0.8876 | |||

ALLAOUI | 0.8851 | |||

NTGA | 0.8826 | |||

shisunzhang | 0.8744 | |||

SSteam | 0.8651 | |||

SamirO-ETF-ba | 0.6046 | |||

sinc | 0.4199 | |||

faria | 0.4055 | |||

FRA | 0.2202 | |||

JG | 0.0302 | |||

fnl4461_n4460 | HPI | 0.9339 | (185359.0, -645150.0) | (442464.0, -0.0) |

jomar | 0.9327 | |||

NTGA | 0.914 | |||

ALLAOUI | 0.8892 | |||

SSteam | 0.8542 | |||

shisunzhang | 0.8258 | |||

faria | 0.5896 | |||

FRA | 0.0045 | |||

SamirO-ETF-ba | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 | |||

fnl4461_n22300 | HPI | 0.8189 | (185359.0, -7827881.0) | (452454.0, -0.0) |

jomar | 0.8146 | |||

NTGA | 0.8035 | |||

SSteam | 0.7815 | |||

ALLAOUI | 0.7605 | |||

shisunzhang | 0.7267 | |||

faria | 0.1259 | |||

FRA | 0.002 | |||

SamirO-ETF-ba | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 | |||

fnl4461_n44600 | HPI | 0.8829 | (185359.0, -22136989.0) | (459901.0, -0.0) |

jomar | 0.8747 | |||

SSteam | 0.8569 | |||

shisunzhang | 0.8503 | |||

NTGA | 0.8248 | |||

ALLAOUI | 0.8182 | |||

faria | 0.0391 | |||

FRA | 0.0152 | |||

SamirO-ETF-ba | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 | |||

pla33810_n33809 | HPI | 0.9272 | (66048945.0, -4860715.0) | (168432301.0, -0.0) |

NTGA | 0.8887 | |||

ALLAOUI | 0.8737 | |||

jomar | 0.8451 | |||

SSteam | 0.8326 | |||

shisunzhang | 0.7085 | |||

faria | 0.1146 | |||

SamirO-ETF-ba | 0.0 | |||

FRA | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 | |||

pla33810_n169045 | HPI | 0.8183 | (66048945.0, -59472432.0) | (169415148.0, -0.0) |

SSteam | 0.7766 | |||

NTGA | 0.7736 | |||

ALLAOUI | 0.7691 | |||

jomar | 0.7385 | |||

shisunzhang | 0.5361 | |||

faria | 0.0037 | |||

SamirO-ETF-ba | 0.0 | |||

FRA | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 | |||

pla33810_n338090 | HPI | 0.8761 | (66048945.0, -168033267.0) | (168699977.0, -0.0) |

SSteam | 0.8538 | |||

jomar | 0.8537 | |||

ALLAOUI | 0.837 | |||

NTGA | 0.7813 | |||

shisunzhang | 0.7232 | |||

faria | 0.0008 | |||

SamirO-ETF-ba | 0.0 | |||

FRA | 0.0 | |||

sinc | 0.0 | |||

JG | 0.0 |

# Competition¶

The Traveling Thief Problem was originally proposed in [1]. If you like to know more about the problem origin we encourage you to read this paper as a starting point. The test problems used for this competition were proposed in [2]. We selected a representative set to cover varying scenarios for the traveling thief for this competition. The bi-objective traveling thief problem was discussed and investigated in [3].

**How to get started**

For guidance, a sample Java implementation is provided: here. You can find information about how to get started there as well. It should provide a starting point to get familiar with the problem and prototype quickly new ideas. However, for this competition you have the freedom to use whatever you need, e.g. speed up the evaluation function, reimplement the problem in other programming languages (e.g. C, Matlab, Python).

**Test Instances**

The nine test instances:

# |
n |
Name |
Instance in [2] |
---|---|---|---|

1 |
100 |
a280_n279 |
a280_n279_bounded-strongly-corr_01 |

2 |
100 |
a280_n1395 |
a280_n1395_uncorr-similar-weights_05 |

3 |
100 |
a280_n2790 |
a280_n2790_uncorr_10 |

4 |
50 |
fnl4461_n4460 |
fnl4461_n4460_bounded-strongly-corr_01 |

5 |
50 |
fnl4461_n22300 |
fnl4461_n22300_uncorr-similar-weights_05 |

6 |
50 |
fnl4461_n44600 |
fnl4461_n44600_uncorr_10 |

7 |
20 |
pla33810_n33809 |
pla33810_n33809_bounded-strongly-corr_01 |

8 |
20 |
pla33810_n169045 |
pla33810_n169045_uncorr-similar-weights_05 |

9 |
20 |
pla33810_n338090 |
pla33810_n338090_uncorr_10 |

For simplicity, we shortened the file name of the selected instances. However, the original instances are annotated above.
The column **n** represents the MAXIMUM number of non-dominated solutions being accepted for the submission for each test problem.

**Submission Format**

To participate in the competition it is required to submit your solutions for ALL test problems.
For each problem two files need to be submitted (i) one file that contains the tour and packing plan and (ii) one file
that contains the time and profits for each corresponding solution. The filenames are supposed to be *<team>_<problem>.x*
and *<team>_<problem>.f*.

First, the file containing the tour and packing plan (*<team>_<problem>.x*) contains for each solution two lines where the
first represents the permutation vector and the second line the packing plan encoded by 0 and 1. Then one empty line
is added to separate one solution from another. An example output can be found here.

Second the file containing the objective space values (*<team>_<problem>.f*) contains the corresponding time and profit
separated by space. An example output can be found here.

The test instances are included in the Github project and a method to run your algorithm on them already exists.

**Submission**

Deadline for this competition is the

**June 30, 2019, Midnight, UTC-12**

Before you submit please make sure to verify the correctness of your solutions using **Verify.java**
(You might need to pull the latest version of the project).

Please submit by sending an email to blankjul@egr.msu.edu with the subject: **GECCO2019 - Bi-objective Traveling Thief Problem Submission**
and provide as a link where we are able to download your results.

**Evaluation**

After having received all submissions, the evaluation will be done as follows:

*For each of the nine test problems*

We will merge the solution sets of all submissions and extract the non-dominated set.

The minimum in time and the maximum in profit will be used to determine the reference point.

With respect to this reference point the quality of each submission will be measured using the hypervolume indicator.

We will sort the submissions according to the achieved hypervolume in descending order and give points as follows: 1st place -> 3 points, 2nd place -> 2 points, 3rd place -> 1 point.

By adding up the points for each submission we will create the overall ranking.
*Please note, that depending on the number of submissions the evaluation might need to be reconsidered.*

# Problem¶

The traveling thief problem combines the Traveling Salesman Problem (TSP) and the Knapsack Problem (KNP). Both problems will be explained in the following sections.

## Traveling Salesman Problem (TSP)¶

In the TSP a salesman has to visit \(n\) cities. The distances are given by a map represented as a distance matrix \(A = (d_{ij})\) with \(i,j \in \{0,..,n\}\). The salesman has to visit each city once and the result is a permutation vector \(\pi = (\pi_1, \pi_2, ..., \pi_n)\) , where \(\pi_i\) is the i-th city of the salesman. The distance between two cities divided by a constant velocity \(v\) results in the traveling time for the salesman denoted by \(f(\pi)\). The goal is to minimize the total traveling time of the tour:

There are \(\frac{(n-1)!}{2}\) different tours to consider, if we assume that the salesman has to start from the first city and travels on a symmetric map where \(d_{i,j} = d_{j,i}\).

## Knapsack Problem (KNP)¶

For the Knapsack Problem a knapsack has to be filled with items without violating the maximum weight constraint. Each item \(j\) has a value \(b_j \geq 0\) and a weight \(w_j \geq 0\) where \(j \in \{1, .., m\}\). The binary decision vector \(z = (z_1, .., z_m)\) defines, if an item is picked or not. The search space of this problem contains 2^n combinations and the goal is to maximize the profit \(g(z)\):

## Traveling Thief Problem (TTP)¶

The TTP is a combinatorial optimization problem that consists of two interweaving problems, TSP and KNP. After explaining the two components separately, the interdependence and the different models of the problem are described.

The Traveling Thief Problem combines the above defined subproblems and lets them interact with each other. The traveling thief can collect items from each city he is visiting. The items are stored in a knapsack carried by him. In more detail, each city \(\pi_i\) provides one or multiple items, which could be picked by the thief. There is an interaction between the subproblems: The velocity of the traveling thief depends on the current knapsack weight \(w\), which is carried by him. It is calculated by considering all cities, which were visited so far, and summing up the weights of all picked items. The weight at city \(i\) given \(\pi\) and \(z\) is calculated by:

The function \(a_j(\pi_k)\) is defined for each item \(j\) and returns \(1\) if the item could be stolen at city \(\pi_k\) and \(0\) otherwise. The current weight of the knapsack has an influence on the velocity. When the thief picks an item, the weight of the knapsack increases and therefore the velocity of the thief decreases.

The velocity \(v\) is always in a specific range \(v = [v_{min}, v_{max}]\) and could not be negative for a feasible solution. Whenever the knapsack is heavier than the maximum weight \(Q\), the capacity constraint is violated. However, to provide also the traveling time for infeasible solutions the velocity is set to \(v_{min}\), if \(w>Q\):

If the knapsack is empty the velocity is equal to \(v_{max}\). Contrarily, if the current knapsack weight is equal to \(Q\) the velocity is \(v_{min}\).

Furthermore, the traveling time of the thief is calculated by:

The calculation is based on TSP, but the velocity is defined by a function instead of a constant value. This function takes the current weight, which depends on the index \(i\) of the tour. The current weight, and therefore also the velocity, will change on the tour by considering the picked items defined by \(z\). In order to calculate the total tour time, the velocity at each city needs to be known. For calculating the velocity at each city the current weight of the knapsack must be given. Since both calculations are based on \(z\) and \(z\) is part of the knapsack subproblem, it is very challenging to solve the problem to optimality. In fact, such problems are called interwoven systems as the solution of one subproblem highly depends on the solution of the other subproblems.

Here, we leave the profit unchanged to be calculated as in the KNP problem. Finally, the TTP problem is defined by

In order to illustrate the equations and interdependence, an example scenario is presented in the following. The thief starts at city 1 and has to visit city 2, 3, 4 exactly once and to return to city 1. In this example, each city provides one item and the thief must decide to steal item or not.

A permutation vector, which contains all cities exactly once, and a binary picking vector are needed to calculate the objectives. Even though, this is a very small example with four cities and three items the solution space consists of \((n-1)! \cdot 2^m = 6 \cdot 8 = 48\) combinations.

In order to understand how the objectives are calculated, an example hand calculation for the tour *[1,3,2,4]* and the packing plan *[1,0,1]* is done as follows:
The thief starts with the maximum velocity, because the knapsack is empty. He begins his tour at city *1* and picks no item there.

For an empty knapsack \(w(1,\pi,z) = 0\) the velocity is \(v(0) = v_{max} = 1.0\). The distance from city *1* to city *3* is \(9.0\) and the thief needs \(9.0\) time units.
At city *3* the thief will not pick an item and continue to travel to city *2* with \(w(2,\pi,z) = 0\) and therefore with \(v_{max}\) in additional \(5.0\) time units.
Here he picks item *1* with \(w_1 = 30\) and the current weight becomes \(w(2,\pi,z) = 30\),
which means the velocity will be reduced to \(v(30) = 1.0 - (\frac{1.0 - 0.1}{80}) \cdot 30 = 0.6625\).
For traveling from city *2* to city *4* the thief needs the distance divided by the current velocity \(\frac{5.0}{0.6625} \approx 7.5472\).
At city *4* he picks item *3* with \(w_3 = 21\) and the current knapsack weight increases to \(w(4,\pi,z) = 30 + 21 = 51\).
For this reason the velocity decreases to \(v(51) = 1.0 - (\frac{1.0 - 0.1}{80}) \cdot 51 = 0.42625\).
For returning to city *1* the thief needs according to this current speed \(\frac{3.0}{0.42625} \approx 7.0381\) time units.
Finally, we sum up the time for traveling from each city to the next \(\sum_{k=1}^{4} t_{\pi_k, \pi_{k+1}} = 9 + 5 + 7.5472 + 7.0381 = 28.5853\) to calculate the whole traveling time.

The final profit is calculated by summing up the values of all items which is \(34 + 25 = 59\). So the variable *[1,3,2,4]* *[1,0,1]* is mapped to the point \((28.59, 59.0)\) in the objective space.
Below you can find all pareto-optimal solutions of this example. The Pareto front contains 8 solutions and our hand calculation is printed bold.

Additionally, the figure below shows the objective space colored by tour. As it can be observed pareto-optimal solutions can have different underlying tours. Please also not that the point where no items are picked consists of two different solutions with a symmetric tour. Also, the Pareto front is non-convex.

# Contact¶

# References¶

- 1
M. R. Bonyadi, Z. Michalewicz, and L. Barone. The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In

*2013 IEEE Congress on Evolutionary Computation*, volume, 1037–1044. June 2013. doi:10.1109/CEC.2013.6557681.- 2(1,2)
Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, and Frank Neumann. A comprehensive benchmark set and heuristics for the traveling thief problem. In

*Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation*, GECCO ‘14, 477–484. New York, NY, USA, 2014. ACM. URL: http://doi.acm.org/10.1145/2576768.2598249, doi:10.1145/2576768.2598249.- 3
Julian Blank, Kalyanmoy Deb, and Sanaz Mostaghim. Solving the bi-objective traveling thief problem with multi-objective evolutionary algorithms. In

*9th International Conference on Evolutionary Multi-Criterion Optimization - Volume 10173*, EMO 2017, 46–60. Berlin, Heidelberg, 2017. Springer-Verlag. URL: https://doi.org/10.1007/978-3-319-54157-0_4, doi:10.1007/978-3-319-54157-0_4.