GECCO2019 - Bi-objective Traveling Thief Competition

_images/logo.png

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!

_images/rank.png

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:

RankTeamPoints
1HPI26
2jomar14
3NTGA5
SSteam5
4ALLAOUI2
shisunzhang2
5FRA0
JG0
SamirO-ETF-ba0
faria0
sinc0

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

ProblemTeamHypervolumeEstimated Ideal PointEstimated Nadir Point
a280_n279 HPI 0.8984 (2613.0, -42036.0) (5444.0, -0.0)
jomar0.8956
shisunzhang0.8866
NTGA0.8837
ALLAOUI0.8735
SSteam0.8706
faria0.6026
SamirO-ETF-ba0.5385
sinc0.3775
FRA0.2256
JG0.1663
a280_n1395 HPI 0.8259 (2613.0, -489194.0) (6573.0, -0.0)
jomar0.8217
shisunzhang0.8209
NTGA0.8115
ALLAOUI0.809
SSteam0.7871
faria0.7595
SamirO-ETF-ba0.4921
sinc0.2634
JG0.1088
FRA0.107
a280_n2790 jomar 0.8879 (2613.0, -1375443.0) (6646.0, -0.0)
HPI0.8876
ALLAOUI0.8851
NTGA0.8826
shisunzhang0.8744
SSteam0.8651
SamirO-ETF-ba0.6046
sinc0.4199
faria0.4055
FRA0.2202
JG0.0302
fnl4461_n4460 HPI 0.9339 (185359.0, -645150.0) (442464.0, -0.0)
jomar0.9327
NTGA0.914
ALLAOUI0.8892
SSteam0.8542
shisunzhang0.8258
faria0.5896
FRA0.0045
SamirO-ETF-ba0.0
sinc0.0
JG0.0
fnl4461_n22300 HPI 0.8189 (185359.0, -7827881.0) (452454.0, -0.0)
jomar0.8146
NTGA0.8035
SSteam0.7815
ALLAOUI0.7605
shisunzhang0.7267
faria0.1259
FRA0.002
SamirO-ETF-ba0.0
sinc0.0
JG0.0
fnl4461_n44600 HPI 0.8829 (185359.0, -22136989.0) (459901.0, -0.0)
jomar0.8747
SSteam0.8569
shisunzhang0.8503
NTGA0.8248
ALLAOUI0.8182
faria0.0391
FRA0.0152
SamirO-ETF-ba0.0
sinc0.0
JG0.0
pla33810_n33809 HPI 0.9272 (66048945.0, -4860715.0) (168432301.0, -0.0)
NTGA0.8887
ALLAOUI0.8737
jomar0.8451
SSteam0.8326
shisunzhang0.7085
faria0.1146
SamirO-ETF-ba0.0
FRA0.0
sinc0.0
JG0.0
pla33810_n169045 HPI 0.8183 (66048945.0, -59472432.0) (169415148.0, -0.0)
SSteam0.7766
NTGA0.7736
ALLAOUI0.7691
jomar0.7385
shisunzhang0.5361
faria0.0037
SamirO-ETF-ba0.0
FRA0.0
sinc0.0
JG0.0
pla33810_n338090 HPI 0.8761 (66048945.0, -168033267.0) (168699977.0, -0.0)
SSteam0.8538
jomar0.8537
ALLAOUI0.837
NTGA0.7813
shisunzhang0.7232
faria0.0008
SamirO-ETF-ba0.0
FRA0.0
sinc0.0
JG0.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

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

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

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

  4. 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:

\begin{eqnarray} min & & f(\pi) \\ s.t. & &\pi = (\pi_1, \pi_2, ..., \pi_n) \in P_n \\[1mm] & &\pi_1 = 1 \\[1mm] f(\pi) & = & \sum_{i=1}^{n-1} \frac{ d_{\pi_i, \pi_{i+1}}}{v} \; + \; \frac{ d_{\pi_n, \pi_{1}}}{v}\nonumber \end{eqnarray}

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)\):

\begin{eqnarray} max & & g(z) \\ \text{s.t.} & & \sum_{j=1}^m z_j \, w_j \leq Q\\ & & z = (z_1, .., z_m) \in \mathbb{B}^m\\ g(z) & = & \sum_{j=1}^{m} z_j \, b_j \\ \end{eqnarray}

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:

\begin{equation} w(i, \pi, z) = \sum_{k=1}^{i} \sum_{j=1}^{m} a_j(\pi_k)\; w_j z_j \end{equation}

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\):

\begin{align} v(w) &= \begin{cases} \; v_{max} - \frac{w}{Q} \cdot (v_{max} - v_{min}) & \text{if } w \leq Q \\ \; v_{min} & \text{otherwise} \end{cases} \end{align}

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:

\begin{equation} f(\pi, z) = \sum_{i=1}^{n-1} \frac{ d_{\pi_i, \pi_{i+1}}}{ v( w(i,\pi,z) ) } \; + \; \; \frac{ d_{\pi_n, \pi_{1}}}{ v( w(n,\pi,z) )} \\ \end{equation}

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

\begin{eqnarray} min & & f(\pi, z) \\ max & & g(z) \\ f(\pi, z) & = & \sum_{i=1}^{n-1} \frac{ d_{\pi_i, \pi_{i+1}}}{ v( w(i,\pi,z) ) } \; + \; \; \frac{ d_{\pi_n, \pi_{1}}}{ v( w(n,\pi,z) )} \\[1mm] g(z) & = & \sum_{j=1}^{m} z_j \, b_j \\ s.t. & &\pi = (\pi_1, \pi_2, ..., \pi_n) \in P_n \\[1mm] & & \pi_1 = 1 \\[1mm] & & z = (z_1, .., z_m) \in \mathbb{B}^m\\ & & \sum_{j=1}^m z_j \, w_j \leq Q\\ \end{eqnarray}

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.

_images/scenario.svg

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.

_images/scenario_table.svg

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.

_images/scenario_front.svg

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.

_images/scenario_obj_space.svg

Contact

Julian Blank (blankjul [at] egr.msu.edu)
Michigan State University
Computational Optimization and Innovation Laboratory (COIN)
East Lansing, MI 48824, USA
Markus Wagner (markus.wagner [at] adelaide.edu.au)
The University of Adelaide, Australia
Adelaide, SA 5005, Australia

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.