# Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem

arXiv: https://arxiv.org/abs/2505.00269 · HTML: https://mlsanity.com/paper/2505.00269/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2025.

## Built on by (most cited first, 1 of 1)

- [The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics](https://mlsanity.com/paper/2604.06724/) (2026)

## Abstract (arXiv)

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.