Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918005740404736 |
|---|---|
| author | Don, Thilina Pathirage Neumann, Aneta Neumann, Frank |
| author_facet | Don, Thilina Pathirage Neumann, Aneta Neumann, Frank |
| contents | 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 the problem definition. In this work, we characterise the chance constrained TTP using a limited number of weighted scenarios. Each scenario represents a similar TTP instance, differing slightly in the weight profile of the items and associated with a certain probability of occurrence. Collectively, the weighted scenarios represent a relaxed form of a stochastic TTP instance where the objective is to maximise the expected benefit while satisfying the knapsack constraint with a larger probability. We incorporate a set of evolutionary algorithms and heuristic procedures developed for the classical TTP, and formulate adaptations that apply to the weighted scenario-based representation of the problem. The analysis focuses on the performance of the algorithms on different settings and examines the impact of uncertainty on the quality of the solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00269 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem Don, Thilina Pathirage Neumann, Aneta Neumann, Frank Neural and Evolutionary Computing 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 the problem definition. In this work, we characterise the chance constrained TTP using a limited number of weighted scenarios. Each scenario represents a similar TTP instance, differing slightly in the weight profile of the items and associated with a certain probability of occurrence. Collectively, the weighted scenarios represent a relaxed form of a stochastic TTP instance where the objective is to maximise the expected benefit while satisfying the knapsack constraint with a larger probability. We incorporate a set of evolutionary algorithms and heuristic procedures developed for the classical TTP, and formulate adaptations that apply to the weighted scenario-based representation of the problem. The analysis focuses on the performance of the algorithms on different settings and examines the impact of uncertainty on the quality of the solutions. |
| title | Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2505.00269 |