The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics
This work addresses a specific optimization problem for researchers and practitioners in logistics and scheduling, but it is incremental as it extends a known problem with time windows.
The paper tackles the traveling thief problem with time window constraints, a multi-component optimization variant relevant to real-world scenarios, and shows that a newly designed heuristic algorithm outperforms existing approaches on a wide range of benchmark instances.
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.