The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms
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.
Code (1)
Tasks
Evolutionary AlgorithmsvalidSimilar Papers 제목 키워드 기반
Evolutionary Computation plus Dynamic Programming for the Bi-Objective Travelling Thief Problem
This research proposes a novel indicator-based hybrid evolutionary approach that combines approximate and exact algorithms. We apply it to a new bi-criteria formulation of the travelling thief problem, which is known to …
On the Fitness Landscapes of Interdependency Models in the Travelling Thief Problem
Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling t…
Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem
The chance constrained travelling thief problem (chance constrained TTP) has been introduced as a stochastic variation of the classical travelling thief problem (TTP) in an attempt to embody the effect of uncertainty in …
Evolutionary AlgorithmsSolving Travelling Thief Problems using Coordination Based Methods
A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattere…
Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation
The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem that attracts many scholars. The TTP interconnects two well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1…
Combinatorial Optimization