The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
This work addresses a gap in dynamic optimization for real-world domains like logistics, but it is incremental as it extends an existing benchmark problem.
The paper tackles the lack of research on dynamic multi-component optimization problems by defining scenarios based on the Travelling Thief Problem, and finds that in 72 scenarios with seven algorithms, the best approach (restarting or continuing) depends on instance specifics, change magnitude, and algorithm portfolio.
Many real-world optimisation problems involve dynamic and stochastic components. While problems with multiple interacting components are omnipresent in inherently dynamic domains like supply-chain optimisation and logistics, most research on dynamic problems focuses on single-component problems. With this article, we define a number of scenarios based on the Travelling Thief Problem to enable research on the effect of dynamic changes to sub-components. Our investigations of 72 scenarios and seven algorithms show that -- depending on the instance, the magnitude of the change, and the algorithms in the portfolio -- it is preferable to either restart the optimisation from scratch or to continue with the previously valid solutions.