The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

• URL: http://arxiv.org/abs/2604.06724v1
• Date: Wed, 08 Apr 2026 06:42:55 GMT
• Title: The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics
• Abstract summary: The traveling thief problem (TTP) is a multi-component problem that has been widely studied in the literature.<n>We introduce and investigate the TTP with time window constraints which provides a TTP variant highly relevant to real-world situations.
• Score: 6.164863213336097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While traditional optimization problems were often studied in isolation, many real-world problems today require interdependence among multiple optimization components. The traveling thief problem (TTP) is a multi-component problem that has been widely studied in the literature. In this paper, we introduce and investigate the TTP with time window constraints which provides a TTP variant highly relevant to real-world situations where good can only be collected at given time intervals. We examine adaptions of existing approaches for TTP and the Traveling Salesperson Problem (TSP) with time windows to this new problem and evaluate their performance. Furthermore, we provide a new heuristic approach for the TTP with time windows. To evaluate algorithms for TTP with time windows, we introduce new TTP benchmark instances with time windows based on TTP instances existing in the literature. Our experimental investigations evaluate the different approaches and show that the newly designed algorithm outperforms the other approaches on a wide range of benchmark instances.

Related papers

• MetaTPT: Meta Test-time Prompt Tuning for Vision-Language Models [62.20230218401528]
  We propose Meta Test-Time Prompt Tuning (MetaTPT), a meta-learning framework that learns a self-supervised auxiliary task to guide test-time prompt tuning.<n>By coupling augmentation learning with prompt tuning, MetaTPT improves test-time adaptation under domain shifts.
  arXiv  Detail & Related papers  (2025-12-13T10:23:10Z)
• TSI-Bench: Benchmarking Time Series Imputation [52.27004336123575]
  TSI-Bench is a comprehensive benchmark suite for time series imputation utilizing deep learning techniques. The TSI-Bench pipeline standardizes experimental settings to enable fair evaluation of imputation algorithms. TSI-Bench innovatively provides a systematic paradigm to tailor time series forecasting algorithms for imputation purposes.
  arXiv  Detail & Related papers  (2024-06-18T16:07:33Z)
• BAIT: Benchmarking (Embedding) Architectures for Interactive Theorem-Proving [13.374504717801061]
  We present BAIT, a framework for fair and streamlined comparison of learning approaches in Interactive Theorem Proving. We demonstrate BAIT's capabilities with an in-depth comparison, across several ITP benchmarks. BAIT also allows us to assess the end-to-end proving performance of systems built on interactive environments.
  arXiv  Detail & Related papers  (2024-03-06T01:56:17Z)
• On Pitfalls of Test-Time Adaptation [82.8392232222119]
  Test-Time Adaptation (TTA) has emerged as a promising approach for tackling the robustness challenge under distribution shifts. We present TTAB, a test-time adaptation benchmark that encompasses ten state-of-the-art algorithms, a diverse array of distribution shifts, and two evaluation protocols.
  arXiv  Detail & Related papers  (2023-06-06T09:35:29Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• A Survey on Deep Learning based Time Series Analysis with Frequency Transformation [75.63783789488471]
  Frequency transformation (FT) has been increasingly incorporated into deep learning models to enhance state-of-the-art accuracy and efficiency in time series analysis.<n>Despite the growing attention and the proliferation of research in this emerging field, there is currently a lack of a systematic review and in-depth analysis of deep learning-based time series models with FT.<n>We present a comprehensive review that systematically investigates and summarizes the recent research advancements in deep learning-based time series analysis with FT.
  arXiv  Detail & Related papers  (2023-02-04T14:33:07Z)
• TeST: Test-time Self-Training under Distribution Shift [99.68465267994783]
  Test-Time Self-Training (TeST) is a technique that takes as input a model trained on some source data and a novel data distribution at test time. We find that models adapted using TeST significantly improve over baseline test-time adaptation algorithms.
  arXiv  Detail & Related papers  (2022-09-23T07:47:33Z)
• On the Use of Quality Diversity Algorithms for The Traveling Thief Problem [11.590506672325668]
  In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. In this paper, we investigate the inter-dependency of the traveling salesperson problem(TSP) and the knapsack problem(KP) by means of quality diversity(QD) approaches.
  arXiv  Detail & Related papers  (2021-12-16T05:08:39Z)
• Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation [8.620967398331265]
  The Travelling Thief Problem (TTP) is a challenging optimization problem that attracts many scholars. In this paper, TTP is investigated theoretically and empirically. An algorithm based on the score value calculated by our proposed formulation in picking items and sorting items in the reverse order is proposed to solve the problem.
  arXiv  Detail & Related papers  (2020-12-16T12:06:05Z)
• Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
  The Traveling Thief Problem (TTP) addresses such interactions by combining two optimisation problems. A new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function.
  arXiv  Detail & Related papers  (2020-06-05T07:07:28Z)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components. Recent state-of-the-art TTP solvers modify the underlying TTP and KP solutions in an iterative and interleaved fashion. We propose to make the search more efficient through an adaptive surrogate model that learns the characteristics of initial TSP tours that lead to good TTP solutions.
  arXiv  Detail & Related papers  (2020-05-14T02:49:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.