Further Enquiries

School of Computer Science
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

Coordinator: Prof Frank Neumann and Dr Sergey Polyakovskiy

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 we will organise another competition on this topic again.

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". For the results, please click here.