The Chance Constrained Travelling Thief Problem: Problem Formulations and Algorithms
Files
(Published version)
Date
2024
Authors
Pathirage Don, T.
Neumann, A.
Neumann, F.
Editors
Li, X.
Handl, J.
Handl, J.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2024), 2024 / Li, X., Handl, J. (ed./s), pp.214-222
Statement of Responsibility
Thilina Pathirage Don, Aneta Neumann, Frank Neumann
Conference Name
The Genetic and Evolutionary Computation Conference (GECCO) (14 Jul 2024 - 18 Jul 2024 : Melbourne, Australia and Virtual Online)
Abstract
The travelling thief problem (TTP) is a multi-component combinatorial optimization problem that has gained significant attention in the evolutionary computation and heuristic search literature. In this paper, we introduce the chance constrained TTP which involves stochastic weights. Our problem formulation captures the stochastic aspect of the knapsack in the form of a chance constraint. Such a constraint can only be violated with a small probability. We introduce surrogate and sampling-based approaches for the chance constrained TTP to optimize the expected objective score under the condition that the solution is feasible with a high probability. We use these approaches to evaluate the feasibility of solutions and incorporate our approaches into high-performing algorithms for deterministic TTP. In our experimental investigations, we compare the performance of these algorithms and show the impact of uncertainty in connection with the underlying stochastic model.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2024 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution International 4.0 License.