The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Helen Yuliana Angmalisang; Frank Neumann

cs.NEApr 8, 2026

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Authors: Helen Yuliana Angmalisang, Frank Neumann

Organizations: Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, SA 5000

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.

Figures & tables

Instance	$l$	S4	S5	C5	LKH-3	VSR-LKH-3
51-A	100	$40\%$	$0\%$	$0\%$	$100\%$	$13\%$
	1000	$100\%$	$0\%$	$0\%$	$100\%$	$50\%$
	-100	$0\%$	$0\%$	$0\%$	$100\%$	$0\%$
	-1000	$0\%$	$0\%$	$0\%$	$0\%$	$0\%$
100-A	100	$0\%$	$0\%$	$0\%$	$97\%$	$0\%$
	1000	$0\%$	$0\%$	$0\%$	$100\%$	$0\%$

Table 1: Feasible Rate of S4, S5, C5, LKH-3, and VSR-LKH-3 on TTPTW Benchmark

Variant	O1	O2	Packing Plan Repair
DSEA 1	Topo	Rain	No Repair
DSEA 2	Topo	Rain	Repack
DSEA 3	ITP	IIP	Integration of Repair and Optimizer

Table 2: Variants of DSEA

Original Instance Name	Type	Alias
eil51_n50_bounded-strongly-corr_01.ttp	A	51-A
eil51_n50_bounded-strongly-corr_02.ttp	A	51-2
eil51_n50_uncorr_01.ttp	A	51-u
eil51_n50_uncorr-similar-weights_01.ttp	A	51-usw
eil51_n50_bounded-strongly-corr_01.ttp	B	51-B
kroC100_n99_bounded-strongly-corr_01.ttp	A	100-A

Table 3: List of TTP Instances Used in This Paper

Instance	$l$	DSEA 1 (1)				DSEA 2 (2)				DSEA 3 (3)
Instance	$l$	mean OB	std OB	FR	stat	mean OB	std OB	FR	stat	mean OB	std OB	FR	stat
51-A	100	3834.78	28.99	$100\%$	2(),3()	3836.13	36.09	$100\%$	1(),3()	3847.39	57.81	$100\%$	1(),2()
	1000	3749.81	199.21	$100\%$	2(*),3(-)	3715.53	208.95	$100\%$	1(*),3(-)	3936.83	156.35	$100\%$	1(+),2(+)
	-100	3468.07	0	$100\%$	2(+),3(*)	3467.91	0.20	$100\%$	1(-),3(-)	3524.47	87.85	$100\%$	1(*),2(+)
	-1000	-581.81	78.99	$0\%$	2(),3()	-607.15	34.79	$0\%$	1(),3()	-645.55	111.49	$0\%$	1(),2()
100-A	100	4533.98	0	$100\%$	2(),3()	4533.98	0	$100\%$	1(),3()	4533.98	0	$100\%$	1(),2()

Table 4: Comparison on Different Packing Plan Repair Algorithms

Instance	$l$	S4-Initial			S5-Initial			C5-Initial			DSEA 1
Instance	$l$	mean OB	std OB	FR	mean OB	std OB	FR	mean OB	std OB	FR	mean OB	std OB	FR
51-A	100	1120.40	1047.96	$100\%$	308.65	0	$100\%$	1323.34	1069.58	$100\%$	3834.78	28.99	$100\%$
	1000	2638.16	366.31	$100\%$	498.85	0	$100\%$	2876.58	305.54	$100\%$	3749.81	199.21	$100\%$
	-100	1948.84	0	$100\%$	1948.84	0	$100\%$	1948.84	0	$100\%$	3468.07	0	$100\%$
	-1000	-2842.08	0	$0\%$	-2842.08	0	$0\%$	-2842.08	0	$0\%$	-581.81	78.99	$0\%$
100-A	100	4533.98	0	$100\%$	4533.98	0	$100\%$	4533.98	0	$100\%$	4533.98	0	$100\%$

Table 5: Performance of S4, S5, and C5 with Tour Initialization on TTPTW Benchmark and Their Comparison to DSEA 1

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints
Apr 16, 2026Hy Nguyen, Thanh Nguyen Pham, Helen Yuliana Angmalisang +2Traveling Salesperson Problem Metaheuristic Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints
Apr 15, 2026Thilina Pathirage Don, Aneta Neumann, Frank NeumannGreedy Optimization Combinatorial Optimization
Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia
Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
Jun 17, 2026Allen George Philip, Anoop Bhat, Sivakumar Rathinam +1Traveling Salesperson Problem Combinatorial Optimization
Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123 · Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA · Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123

Apr 16, 2026J/K move · Enter open · S save

On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints

Hy Nguyen, Thanh Nguyen Pham, Helen Yuliana Angmalisang, Liam Wigney+1

Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

Traveling Salesperson Problem Metaheuristic Optimization Combinatorial Optimization

Open paper AskPDF arXiv

In many real-world settings, problem instances that need to be solved are quite similar, and knowledge from previous optimization runs can potentially be utilized. We explore this for the Traveling Salesperson problem with time windows (TSPTW), which often arises in settings where the travel-time matrix is fixed but time-window constraints change across related tasks. Existing TSPTW studies, however, have not systematically compared solving such task sequences independently with sequential transfer from previously solved tasks. We address this gap using a multi-task benchmark in which each base instance is expanded into five related tasks under two environments: partial time-window expansion and swap-additive time reassignment. We compare a standard from-scratch protocol with an iterative protocol that initializes each task from the best tour of the previous task, using the popular local search approaches LNS, VNS, and LKH-3 under a common penalized-score objective. Our experimental results show that the iterative protocol is consistently superior in the progressive-relaxation setting and generally competitive under swap-additive changes, with improvements increasing on more difficult instances.

Abstract

Combinatorial Optimization

Explore similar work

On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints

Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles