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, the maximizing material utilization while respecting a production schedule,
and the 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.

The set of benchmarks used in this competition follows the idea of the "Travelling Thief Problem" (Mohammad Reza Bonyadi, Zbigniew Michalewicz, Luigi Barone: The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. IEEE Congress on Evolutionary Computation 2013: 1037-1044). Euclidian 2D Traveling Salesperson instances are combined with 0-1-Knapsack instances in such a way that it reflects aspects of problems from the real-world; for example, the total weight of the items in the knapsack influences the travel speed of a traveller. This introduced interdependence sets our benchmarks apart from capacitated vehicle routing problem instances, where this interdependence does not exist. For technical details on how the benchmarks were created, please see the manual (identical to the GECCO 2014 article "A comprehensive benchmark set and heuristics for the traveling thief problem").

Some related work (including approximate approaches, instance analyses, and code) can be found at the University of Adelaide’s TTP Project Page.

All 9720 instances are available for researchers to experiment with: http://cs.adelaide.edu.au/~optlog/CEC2014COMP_InstancesNew/. In order to encourage researchers during the weeks before the submission deadline, we invite you to submit solutions for the sample instances - the system to do this will be setup soon. If you are interested in an access ID, please contact Kelly. These results will be displayed online (without a reference to the authors) and then will serve as performance indications for other researchers.

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.

The set of benchmarks used in this competition follows the idea of the "Travelling Thief Problem" (Mohammad Reza Bonyadi, Zbigniew Michalewicz, Luigi Barone: The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. IEEE Congress on Evolutionary Computation 2013: 1037-1044). Euclidian 2D Traveling Salesperson instances are combined with 0-1-Knapsack instances in such a way that it reflects aspects of problems from the real-world; for example, the total weight of the items in the knapsack influences the travel speed of a traveller. This introduced interdependence sets our benchmarks apart from capacitated vehicle routing problem instances, where this interdependence does not exist. For technical details on how the benchmarks were created, please see the manual (identical to the GECCO 2014 article "A comprehensive benchmark set and heuristics for the traveling thief problem").

Some related work (including approximate approaches, instance analyses, and code) can be found at the University of Adelaide’s TTP Project Page.

All 9720 instances are available for researchers to experiment with: http://cs.adelaide.edu.au/~optlog/CEC2014COMP_InstancesNew/. In order to encourage researchers during the weeks before the submission deadline, we invite you to submit solutions for the sample instances - the system to do this will be setup soon. If you are interested in an access ID, please contact Kelly. These results will be displayed online (without a reference to the authors) and then will serve as performance indications for other researchers.

Tracks

Track 1: The original TTP formulation is used, as defined in the documents above.

Track 2: A relaxed TTP formulation is used, in which not all cities need to be visited, and more than one thief can be used (Shelvin Chand, Markus Wagner: Fast Heuristics for the Multiple Traveling Thieves Problem. Genetic and Evolutionary Computation Conference 2016).

In both tracks, the same 9720 instances will be used.

Individuals and teams can make one competition submission per track.

Track 2: A relaxed TTP formulation is used, in which not all cities need to be visited, and more than one thief can be used (Shelvin Chand, Markus Wagner: Fast Heuristics for the Multiple Traveling Thieves Problem. Genetic and Evolutionary Computation Conference 2016).

In both tracks, the same 9720 instances will be used.

Individuals and teams can make one competition submission per track.

Evaluation

In contrast to previous years, **we will not run the code, and we also do not impose any resource limits. **
The participants will send us the solutions (one solution per instance) in the pre-defined format.
This relaxation has the advantage that researchers are no longer bounded by the established “10 minutes of 1 CPU core”, opening up the research on multi-component problems to new approaches.

Prize

Markus Wagner provides AUD 1000 in cash. Additional sponsors are being sought right now.

Conference Participation

We encourage the entrants to write papers on their methods and to submit those to an relevant conference. Examples include, among other, CEC 2017, SEA 2017, GECCO 2017, ... (please do not submit the same research several times in parallel, of course)

While we do not require this, we strongly encourage the participants to register for a conference due to the advantages.

Instances and Code

We provide a range of sample instances that are representative for the instances that your algorithms will have to solve. In brackets, we list some decent objective values.

- 280 cities
- 1 item per city, lowest knapsack capacity, strongly correlated item weights/profits (18049)
- 5 items per city, medium knapsack capacity, uncorrelated but similar item weights/profits (109221)
- 10 items per city, highest knapsack capacity, uncorrelated item weights/profits (428117)
- 4461 cities
- 1 item per city, lowest knapsack capacity, strongly correlated item weights/profits (256591)
- 5 items per city, medium knapsack capacity, uncorrelated but similar item weights/profits (1611342)
- 10 items per city, highest knapsack capacity, uncorrelated item weights/profits (6536729)
- 33810 cities

Technical Details and Submission

Please note:

- Output: the file with the result for a single iteration should follow the following naming convention: <ttpfile>.<algorithmname>.<systemtime>, e.g.,

a280_n279_bounded-strongly-corr_02.ttp.thisIsMyAlgorithm.12345678912

- The file needs to contain the following information as comma-separated values in square brackets: the permutation of the cities in the first line (note: the first city is "1", do not print the "1" at the end), and the list of packed items in the second line (the numbering of the items starts with "1"). For example:

[1,5,4,2,3]

[20,113]

which means that only the items with the numbers 20 and 113 are picked, and the sequence of visited cities is <1,5,4,2,3,1>. Note that this format can easily be achieved in Java with the function Arrays.toString(...). The provided Java package provides all necessary helper function, but you might decide to implement your own internal representation for the optimisation.

We will inform you in time how you can send us your solutions. We will most likely prefer download links from servers, or links to archives on Google Drive, Dropbox, and so on.

The file format is quite straightforward and can be generated easily by the provided Java code above. A sample file for the instance a280_n279_bounded-strongly-corr_01.ttp is the following: a280_n279_bounded-strongly-corr_01.ttp.rt3.1480595860887.

On our side, we will take your solution files and then evalute them. This will include the checking of constraints, such as, knapsack capacity considered, all cities visited (when applicable), starting and end city is city with ID 1, etc.

We are currently developing an online leaderboard that will allow all participants to continuously compare their performances. Potentially, this system will replace your submission via email - we will inform you in time.

Important Dates

Please contact us if you want to receive notifications via email.

Competition Organizers

School of Computer Science

The University of Adelaide

Adelaide, Australia