CSIT Seminar (005.03.001): A talk from Prof. Frank Neumann: Exact Approaches for Packing While Traveling and the Traveling Thief Problem

Title:  Exact Approaches for Packing While Traveling and the Traveling Thief Problem

Abstract: 

Multi-component problems play a crucial role in real-world applications, especially in the area of supply chain management. Recently, the traveling thief problem (TTP) has been introduced to study multi-component problems in a systematic way and many heuristic search algorithms have been proposed for the TTP. Although a lot of algorithmic advances have been made on this problem, determining an optimal solution, even for small instances, is very challenging. In this talk, I will present exact approaches for this problem. I start by investigating the already NP-hard Packing While Traveling (PWT) problem which results from TTP when the TSP tour is fixed. I present an exact dynamic programming approach for PWT and give a fully polynomial time approximation scheme (FPTAS) for PWT over its baseline travel cost. Afterwards, I extend the approach to give a dynamic programming approach for TTP and report on some experimental results.

Joint work with Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu, Markus Wagner


Bio-sketch:

Frank Neumann received his diploma and Ph.D. from the Christian-Albrechts-University of Kiel in 2002 and 2006, respectively. He is a professor and leader of the Optimisation and Logistics Group at the School of Computer Science, The University of Adelaide, Australia. Frank has been the general chair of the ACM GECCO 2016. With Kenneth De Jong he organised ACM FOGA 2013 in Adelaide and together with Carsten Witt he has written the textbook "Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity" published by Springer. He is an Associate Editor of the journals "Evolutionary Computation" (MIT Press) and "IEEE Transactions on Evolutionary Computation" (IEEE). In his work, he considers algorithmic approaches in particular for combinatorial and multi-objective optimization problems and focuses on theoretical aspects of evolutionary computation as well as high impact applications in the areas of renewable energy, logistics, and mining.