Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

Thilina Pathirage Don; Aneta Neumann; Frank Neumann

cs.NEApr 15, 2026

Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

Authors: Thilina Pathirage Don, Aneta Neumann, Frank Neumann

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

Abstract

The travelling thief problem (TTP) is a well-known multi-component optimisation problem that captures the interdependence between two components: the tour across cities and the packing of items. The packing while travelling problem (PWT) is an NP-hard subproblem of TTP where the packing of items should be optimised for a given fixed tour. In many solvers, the packing component is often addressed using greedy heuristics. Here, the use of suitable greedy functions is essential for the success of greedy algorithms. In this paper, we introduce new reward functions tailored to the PWT and extend them to a hyper-heuristic framework to achieve further advantage. Furthermore, we investigate the chance constrained PWT for greedy approaches and adopt the newly introduced reward functions for stochastic weights. The experimental results clearly demonstrate the benefit of the tailored heuristics over the standard heuristics in both deterministic and stochastic constraints.

Figures & tables

Panel of Figure 1 — Figure 1: Example TSP tour to represent the weight accumulation in $r4$ reward function. See the discussion in the text.

problem type	algorithm	initialisation	heuristics used
deterministic	$HH_{1}$	$r1$	{ $r1,r2,r3$ }
	$HH_{2}$	best	{ $r1,r2,r3$ }
	$HH_{3}$	$r1$	{ $r1,r2,r3,r4,r5$ }
	$HH_{4}$	best	{ $r1,r2,r3,r4,r5$ }
stochastic	$HH_{5}$	$r1$	{ $r1,r6,r7$ }
	$HH_{6}$	best	{ $r1,r6,r7$ }

Table 1: Initialisation techniques and the reward functions used in the hyper-heuristic algorithms.

heuristics/algorithm	Pack modification
$r1,r2,r3$	Pack
$r4,r5$	Pack for iterative reward functions
$r6,r7$	$\textsc{Pack}_{SF}$ for iterative reward functions
$HH_{1},HH_{2}$	Pack for hyper-heuristics
$HH_{3},HH_{4}$	Pack for hyper-heuristics and
	iterative reward functions

Table 2: Modifications done for the Pack algorithm to implement the reward functions and algorithms.

instance	$r$ 1		$r2$		$r3$		$r4$		$r5$
	mean	std	mean	std	mean	std	mean	std	mean	std
unc_51	1368.04	476.93	1444.64	309.07	1820.21	169.68	1108.05	691.93	1775.67	147.59
unc_152	2754.18	921.60	2153.71	695.75	3727.24	1062.50	2700.60	970.43	3701.47	1012.03
unc_280	10637.54	986.40	12683.06	661.05	16535.55	1531.58	12273.59	549.02	16345.35	1322.97
unc_575	20604.12	1235.43	19020.23	2178.85	30702.12	860.41	15587.63	1928.82	30833.99	631.09
unc_1000	104190.60	2489.20	90115.00	0.00	165486.00	0.00	90115.00	0.00	165486.00	0.00

Table 3: Performance of the Pack algorithm with different reward functions on the PWT with deterministic constraints.

instance	$HH_{1}$		$HH_{2}$		$HH_{3}$		$HH_{4}$
	mean	std	mean	std	mean	std	mean	std
unc_51	1864.76	171.12	1925.51	125.61	1876.87	232.16	1915.51	111.23
unc_152	3472.97	1120.34	3865.93	1078.53	3424.79	1089.50	3865.93	1078.53
unc_280	15734.58	671.98	16840.14	1286.13	15590.71	946.79	16908.97	1265.31
unc_575	29444.28	868.48	31511.08	652.25	29227.75	1420.34	31767.77	606.75
unc_1000	127662.70	4200.46	165486.00	0.00	130883.07	4595.76	165486.00	0.00

Table 4: Performance of Pack algorithms with different hyper-heuristics on the PWT with deterministic constraints.

instance	p value	$r5$	$HH_{4}$
unc_51	0.0002	(-)	(+)
unc_152	0.0012	(-)	(+)
unc_280	0.0026	(-)	(+)
unc_575	1.80e-07	(-)	(+)
unc_1000	1.0000
bsc_51	8.26e-11	(-)	(+)

Table 5: Statistical analysis of best performing algorithms for PWT with deterministic constraints.

instance	$\alpha$	$\delta$	$r1$		$r6$		$r7$		$HH_{5}$		$HH_{6}$
			mean	std	mean	std	mean	std	mean	std	mean	std
unc_51	0.9	20	1480.11	389.67	1108.05	680.30	1788.41	163.12	1519.44	414.30	1853.82	153.64
unc_51	0.999	20	1451.51	409.89	1104.94	654.95	1691.28	199.48	1464.50	428.26	1915.51	109.36
unc_152	0.9	20	2751.33	905.66	2225.26	1238.71	3701.47	995.02	2974.88	661.36	3802.90	1077.78
unc_152	0.999	20	2724.08	910.39	2094.89	1312.99	3533.24	837.81	2944.65	679.81	3540.27	832.94
unc_280	0.9	20	10297.09	983.66	11784.74	629.92	16337.69	1293.67	14569.46	668.68	16634.86	1168.34

Table 6: Performance of

\textsc{Pack}_{SF}

with different reward functions and hyper-heuristics on PWT with stochastic constraints

instance	$\alpha$	p value	$r7$	$HH_{6}$
unc_51	0.9	0.0002	(-)	(+)
unc_51	0.999	0.0002	(-)	(+)
unc_152	0.9	0.5027
unc_152	0.999	0.0012	(-)	(+)
unc_280	0.9	0.0493	(-)	(+)
unc_280	0.999	0.0211	(-)	(+)

Table 7: Statistical analysis of best performing algorithms for PWT with stochastic constraints.

Greedy Optimization

See all 12 papers

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics
Apr 8, 2026Helen Yuliana Angmalisang, Frank NeumannCombinatorial Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, SA 5000
Drive, Pack, Fly: The Travelling Thief Problem with Drone
Aug 17, 2026Kabir Murjani, Abhay SobhananCombinatorial Optimization Metaheuristic Optimization
Nirma University, SG Highway, Ahmedabad 382481, Gujarat, India · Indian Institute of Management Bangalore, Bannerghatta Road, Bengaluru 560076, Karnataka, India
Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems
Oct 22, 2026Haohui Zhang, Xinyu Hu, Wouter van Heeswijk +2RL for Combinatorial Optimization Combinatorial Optimization
University of Twente, Enschede, Netherlands · University of Bath, Bath, United Kingdom · Delft University of Technology, Delft, Netherlands

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

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Helen Yuliana Angmalisang, Frank Neumann

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

Combinatorial Optimization

Open paper AskPDF arXiv

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.

Abstract

Greedy Optimization

Explore similar work

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Drive, Pack, Fly: The Travelling Thief Problem with Drone

Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems