Further Enquiries

School of Computer and Mathematical Sciences
Ingkarni Wardli Building
The University of Adelaide
SA 5005
AUSTRALIA
Email

Telephone: +61 8 8313 5586
Facsimile: +61 8 8313 4366

Combinatorial Optimization and Logistics

Director: Prof Frank Neumann

Travelling thief problem: a transition from theoretical problems to realistic problems

Real-world optimization problems usually consist of several problems that interact with each other. In order to solve such problems it is important to understand and deal with these interactions. So far, the research literature is lacking systematic approaches for dealing with such interdependent problems.

Therefore, a new problem called travelling thief problem (TTP) has been introduced, which is more similar to real-world problems. In fact, the interdependency between the sub-components of real-world problems (that was missed in the previous benchmark problems) has been incorporated in this new problem. It is a combination of two of the most prominent combinatorial optimization problems, namely the traveling salesperson problem (TSP) and the knapsack problem (KP). Both problems have been considered in numerous theoretical and experimental studies, and very effective solvers are known that perform well on a variety of benchmarks. It is important to note that the TTP is unlike many capacitated vehicle-routing problems in the area of Green Logistics. In our case, we add to the routing problem not only a load-dependent feature, but also the NP-hard optimization problem of deciding which items are to be packed.

There has been a competition at IEEE WCCI 2014 related to TTP, and again at IEEE CEC 2015, and again at IEEE CEC 2017 and GECCO 2017, and again at GECCO 2023

In 2019, there have been two competitions on the bi-objective TTP: EMO 2019, GECCO 2019

Best TTP objective score: if you are here to find the best known TTP scores, have a look at the Journal of Heuristics 2017 paper below. This is a comprehensive comparison of many algorithms that had a single-run with 10-minute per instance time limit.
Below, at the 2017 competition competition, there is also a comprehensive comparison of algorithm with some competition submissions -- note that the competition participants did not have any time limit.

Published papers:

Optimisation of Professional Cycling Strategies

Team pursuit track cycling is a bicycle racing sport held on velodromes and it is part of the Summer Olympics. It involves the use of strategies to minimize the overall time that a team of cyclists needs to complete a race.

We developed an optimisation framework for team pursuit track cycling and showed how to evolve strategies using metaheuristics for this interesting real-world problem. Our experimental results show that these heuristics lead to significantly better strategies than state-of-art strategies that are currently used by teams of cyclists.

For optimizers, this problem is challenging as optimal solutions are close to infeasible solutions. In order to achieve good racing times, the cyclists tend to use up all their energy. Infeasible solutions ask the cyclists to use more energy than they have at their disposal.

Software

The simulator is available for download: Source Code: Java implementation (Maintainer: Markus Wagner).

Usage in Classrooms

We have used this problem (and this code) as a group project in our course on "Evolutionary Computation" (single-objective simulator: simulator code). For the results, please click here.