Real-world optimization problems often consist of combined NP-hard combinatorial optimization problems that interact with each other. Such multi-component optimization problems are difficult to solve not only because of the hard optimization problems themselves, but in particular, because of the interdependencies between the different components. Interdependence complicates decision making by forcing each sub-problem to influence the quality and feasibility of solutions for 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 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 the Travelling Salesperson Problem (TSP) and the Knapsack problem. 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: free PDF, "The travelling thief problem: The first step in the transition from theoretical problems to realistic problems" (IEEE PDF)). 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 the TTP apart from capacitated vehicle routing problem instances, where this interdependence does not exist. For technical details on our fitness function and on how the benchmark instances were created, please see the manual (free PDF) (identical to "A comprehensive benchmark set and heuristics for the traveling thief problem" (ACM PDF)).

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

  Tracks

There will be a number of tracks, because the available instances (from https://dl.acm.org/doi/10.1145/2576768.2598249, http://cs.adelaide.edu.au/~optlog/CEC2014COMP_InstancesNew/) vary massively and across multiple orders of magnitude. 

Track 1: Analysis of results produced by candidates' code. No code required.

Track 1.1: Three small instances: a280_n279_bounded-strongly-corr_01.ttp, a280_n1395_uncorr-similar-weights_05.ttp, a280_n2790_uncorr_10.ttp

Track 1.2: Three medium-sized instances: fnl4461_n4460_bounded-strongly-corr_01.ttp, fnl4461_n22300_uncorr-similar-weights_05.ttp, fnl4461_n44600_uncorr_10.ttp

Track 1.3: Three large instances: pla33810_n33809_bounded-strongly-corr_01.ttp, pla33810_n169045_uncorr-similar-weights_05.ttp, pla33810_n338090_uncorr_10.ttp

Note: these are the nine “Sample Instances” listed further below.

Track 2: Code execution. Compute resources: 1 core (cloud-computing CPU), 16GiB RAM, 10 minutes execution time.

Track 2.1: Three small instances

Track 2.2: Three medium-sized instances

Track 2.3: Three large instances

  Prize

Markus Wagner provides AUD 1000 in cash. Adriano Torres provides will handle cloud infrastructure costs related to Track 2.

  Conference Participation

We encourage the entrants to write papers on their methods and to submit those to a relevant conference in 2024 or 2025. However, we do not require this. Attendance to the event is not required.

  Instances and Code

Sample Instances

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

  • 1 item per city, lowest knapsack capacity, strongly correlated item weights/profits (1810973)

  • 5 items per city, medium knapsack capacity, uncorrelated but similar item weights/profits (1.536E7)

  • 10 items per city, highest knapsack capacity, uncorrelated item weights/profits (5.732E7)

Code

The objective function: C#, Java (including basic heuristic algorithms), Matlab

  Technical Details and Submission

Technical Details

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.

Submission

By the deadline, please send us the results. We prefer download links from servers, or links to archives on Google Drive, Dropbox, OneDrive, and so on.

Track 1

Please provide only 1 file for each instance, meaning that you will submit at most 9 files.

Track 2

Please provide the code, as well as instructions on how to execute it.

Submission details: 

• Your code has to run on a Linux server machine via the command-line interface. This means that solutions developed in integrated development environments must be executable via the CLI as well.

• Please provide a README file with clear, step-by-step instructions on how to execute your code. 

• Please do not containerise your application. Solutions that require container runtimes and/or orchestrators will not be accepted.

• Please ensure that your code produces a solution file within 10 minutes, because we will terminate your code after 10 minutes. For practical reasons, we will grant a few seconds as a grace period.

If you cannot provide results for all instances, then we are happy to accept partial submissions as well.

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 evaluate them. This will include the checking of constraints, such as, knapsack capacity considered, all cities visited, starting and end city is city with ID 1, etc.

  Online leaderboard

To encourage an ongoing competition over the next months, we are going to maintain several leaderboard graphs in this section.