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

Kabir Murjani; Abhay Sobhanan

cs.AIAug 17, 2026

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

Authors: Kabir Murjani, Abhay Sobhanan

Organizations: Nirma University, SG Highway, Ahmedabad 382481, Gujarat, India · Indian Institute of Management Bangalore, Bannerghatta Road, Bengaluru 560076, Karnataka, India

Abstract

In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency. An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit. However, travel time remains load-dependent, and each item collected by the ground vehicle shifts the arrival times that govern the drone's launch and rendezvous points. This paper introduces the Travelling Thief Problem with Drone (TTP-D), which maximises the collected profit, net of a time-based rental cost, by jointly optimising item selection, vehicle routing, and flight synchronisation. We formulate a mixed-integer linear program that solves small instances to optimality, and develop both metaheuristics and an attention-based Deep Reinforcement Learning (DRL) policy for larger instances. We further propose a learner-initialised hybrid solver, in which the DRL policy constructs an initial solution that a short annealing run subsequently refines. On two benchmark sets, this hybrid recovers most of the metaheuristic baseline's quality at a fraction of its computational budget, although the largest instances still require the baseline at its full budget. Finally, a sensitivity analysis reveals that the rental ratio is the primary driver of profitability, whereas the fleet parameters affect profit only at the margin.

Figures & tables

Figure 1: Truck speed over a ten-customer TTP-D instance, drawn against mission time, with the two sortie windows shaded, waiting shown in grey, and the truck’s load annotated as a percentage of capacity.

Figure 2: TTP-D optimal plan on two instances with

N=10

and

N=15

customers. Each colour represents the visit mode. A filled circle marks a customer whose item is collected, and an open circle marks one who is visited but whose item is left behind.

Symbol	Type	Meaning
Sets and indices
$\mathcal{N}$	set	Customers, indexed $\mathcal{N}=\{1,\ldots,n\}$
$N$	$\mathbb{N}$	Number of customers, $N=\|\mathcal{N}\|$
$\mathcal{V}$	set	Nodes, $\mathcal{V}=\{0,0^{\prime}\}\cup\mathcal{N}$ , the source and sink depots and the customers
$\mathcal{A}$	set	Arcs, $\mathcal{A}=\{(i,j):i,j\in\mathcal{V},\ i\neq j\}$
$\delta^{+}(i),\delta^{-}(i)$	set	Out-arcs and in-arcs at node $i$ , respectively

Table 1: Notation for the TTP-D formulation.

Symbol	Type	Meaning
Metaheuristics (Section 5.1 )
$\mathbf{x},\mathbf{x}^{\prime}$	tuple	Incumbent solution $\mathbf{x}=(\mathbf{r},\mathcal{S},\mathbf{z})$ , and a feasible neighbour $\mathbf{x}^{\prime}$
$\mathbf{r}$	vector	Order in which the truck visits its customers
$\mathcal{S}$	set	Drone sorties, each defined as a triple $(\ell,k,j)$
$\mathbf{z}$	vector	Packing configuration, with binary components $z_{i}$
$\Delta G$	$\mathbb{R}$	Change in objective function value from a move; $G(\mathbf{x}^{\prime})-G(\mathbf{x})$

Table 2: Notation for the solution methods.

Figure 3: The LISA framework. The upper track depicts offline policy distillation, while the lower track depicts online inference, where the cloned policy

\pi_{\theta}

warm-starts SA.

Parameter	Value
Instance name	a280-TTP
Dimensions	280 nodes, 1395 items
Renting ratio ( $R$ )	72.70
Knapsack capacity	$637{,}010$ (scaled per size to $W=637{,}010\,N/280$ )
Truck speed range	$v\in[0.1,1.0]$
Drone speed factor	$2.0\times v_{\max}$

Table 3: Parameters of the a280 -derived TTP-D benchmark.

Figure 4: MILP solver convergence on a benchmark instance for each of the two largest solvable problem sizes. The plot shows the evolution of the primal incumbent, the dual bound, and the resulting optimality gap (shaded area).

Method	$N=5$		$N=10$		$N=15$		$N=20$		$N=30$		$N=40$		$N=50$		Mean
Method	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Mean
MILP	0.00	0.5	0.00	49.1	0.36	66,945	2.61	86,400	$-$		$-$		$-$		$-$
SA	0.00	10	0.22	30	0.00	120	0.09	301	0.00	451	0.00	600	0.00	750	0.04
VNS	0.00	10	0.22	30	0.32	120	0.19	300	5.14	450	17.28	600	27.07	750	7.17
MLP	0.00	3.6	4.85	9.6	3.88	25	5.41	43	15.09	25.8	21.30	58.6	19.12	40.6	9.95
GAT	0.34	3.5	2.69	11	3.91	25	4.91	40	11.48	23.1	15.68	50.3	19.92	41.6	8.42

Table 4: Performance gap (%) and mean runtime per instance (seconds) on the a280 TTP-D benchmark, per instance size. The results for LISA are categorised by the budget fraction

\beta

, with its runtime dependent on the corresponding budget

\beta B(N)

Parameter	Value
Topology	Uniform integer coordinates on $[0,300]^{2}$ , ceiling of Euclidean distance
Sizes	$N\in\{10,20,30,40,50,75,100\}$ , 5 layouts (L1–L5) each
Items	$5$ per customer, $w\sim U[1000,1009]$ , $p\sim U[1,1000]$
Capacity	$W=\lfloor 2275.0357\,N\rceil$ , fixed per size
Rental ratio ( $R$ )	$50.0$
Truck speed range	$v\in[0.1,1.0]$

Table 5: Parameters of the ttd300 TTP-D benchmark.

Panel of Figure 5 — Figure 5: The full-budget SA reference across the four endurance fractions, on instance sizes of ttd300 . Each point is the mean over the five layouts at that setting.

Method	$N=10$		$N=20$		$N=30$		$N=40$		$N=50$		$N=75$		$N=100$		Mean
Method	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Mean
SA (reference)	0.00	120	0.00	300	0.00	450	0.00	600	0.00	750	0.00	975	0.00	1,200	0.00
GAT	2.37	25	18.04	72	29.77	137	26.05	260	37.84	458	33.26	1,372	51.05	3,098	28.34
LISA, $\beta=5\%$	0.00	6	0.85	15	5.81	22.5	5.23	30	13.60	37.5	17.82	48.8	31.65	60	10.71
LISA, $\beta=10\%$	0.00	12	0.76	30	2.64	45	6.51	60	10.83	75	15.33	97.5	18.00	120	7.72
LISA, $\beta=20\%$	0.00	24	0.33	60	2.95	90	4.09	120	8.38	150	11.80	195	17.62	240	6.45

Table 6: Performance gap (%) to the SA metaheuristic reference and mean runtime per instance (seconds) on the ttd300 benchmark.

Figure 6: Profit against rental cost at the ttd300 SA reference, where endurance fraction

f=0.5

. Each bar is the mean over the five layouts at that size, annotated with the net objective

G

Panel of Figure 7 — Figure 7: Performance of LISA on the ttd300 L1 layouts.

Panel of Figure 8 — Figure 8: Comparison of single-item and multi-item collection on ttd300 . The objective gains in (a) are directly driven by the higher capacity utilisation shown in (b).

Figure 9: Mean objective versus drone speed factor (

\phi

) across problem sizes. Initial speed increases yield the largest gains, followed by diminishing returns. Short endurance (

f=0.25

) severely restricts these gains, completely flattening the curve at

N=10

where no sorties are feasible.

Constraints	big- $M$	Tight Bound	Comment
Drone payload, weight propagation	$M_{\mathrm{W}}$	$w_{\mathrm{tot}}=\sum_{i\in\mathcal{N}}w_{i}$	Total weight of all available customer items.
Truck timing	$M_{\mathrm{T}}$	$d_{\max}(N+1)/v_{\min}$	Worst-case traversal time assuming $N+1$ arcs at distance $d_{\max}$ and minimum velocity $v_{\min}$ .
Drone timing	$M_{\mathrm{D}}$	$d_{\mathrm{NN}}/v_{\min}$	Makespan of a nearest-neighbour warm-start tour evaluated at minimum velocity $v_{\min}$ .

Table 7: Value for big-

M

s. These constraint groups comprise the travel-time and synchronisation constraints presented in the manuscript.

Group	Parameter	Value
Encoder	layers / model dim / heads / FF dim	$3$ / $128$ / $8$ / $512$
	activation / normalisation / dropout	GELU / pre-norm LayerNorm / $0$
	node features	coordinates, $p_{i}/p_{\max}$ , $w_{i}/W$
Decoder	pointer clipping constant $C$	$10$
	state scalars	$7$
	binary heads	MLP $(2d_{\mathrm{model}}\to d_{\mathrm{model}}\to 2)$ , GELU

Table 8: Policy and training hyperparameters. Here

d_{\mathrm{model}}=128

is the model dimension and

N

is the number of customers.

Figure 10: Decode-strategy ablation on the a280 MILP-anchored instance sizes. Each panel plots the gap to the certified MILP optimum against decode runtime (log scale) for seven decoding strategies under one trained policy, one run per strategy. The strategies form a ladder of increasing decode compute, shaded light to dark in that order, with a connector following the ladder within each panel and a ring on the selected decoder.

Method	$N=5$	$N=10$	$N=15$	$N=20$	$N=30$	$N=40$	$N=50$
SA	0.00	0.33	0.76	0.94	1.98	1.94	2.34
VNS	0.01	0.00	0.42	3.02	5.04	5.49	4.96

Table 9: Seed-to-seed dispersion of the objective (%) on the a280 benchmark.

$N$	$f$	$G_{\mathrm{MI}}$	$G_{\mathrm{SI}}$	$\Delta G$	Cities	Avg	Max	Util	Tr	Dr
10	0.25	$-$ 43,618	$-$ 45,243	1,626	4.0	2.50	4.0	44%	4.0	0.0
	0.50	$-$ 37,994	$-$ 41,253	3,259	4.0	3.25	5.0	57%	2.0	2.0
	0.75	$-$ 30,665	$-$ 34,623	3,958	6.0	2.83	5.0	75%	3.0	3.0
	1.00	$-$ 25,665	$-$ 29,670	4,004	7.0	2.57	5.0	80%	3.0	4.0
20	0.25	$-$ 46,906	$-$ 54,905	7,998	13.0	2.85	5.0	82%	8.0	5.0
	0.50	$-$ 38,310	$-$ 48,705	10,395	13.0	2.92	5.0	84%	8.0	5.0

Table 10: Performance comparison of multi-item versus single-item collection strategies on the ttd300 benchmark. Each row reports the best result across independent runs with the same per-size budget on the first layout (L1), across varying instance sizes

N

and drone endurance fractions

f=E_{\mathrm{D}}/d_{\max}

. The objective values for the multi-item and single-item models are denoted by

G_{\mathrm{MI}}

and

G_{\mathrm{SI}}

, respectively, alongside their exact difference

\Delta G=G_{\mathrm{MI}}-G_{\mathrm{SI}}

. Operational metrics include the total number of collected cities (“Cities”), the average (“Avg”) and maximum (“Max”) number of items retrieved per collected city, the capacity utilisation fraction (“Util”), and the split of collected cities between the truck and the drone (“Tr”/“Dr”). The better objective value for each configuration is marked in bold.

$N$	$\phi$	$G$	T/D/C	$G$	T/D/C	$G$	T/D/C	$G$	T/D/C
		$f=0.25$		$f=0.50$		$f=0.75$		$f=1.00$
10	0	$-$ 45,243	5.0/0.0/0.0	$-$ 45,243	5.0/0.0/0.0	$-$ 46,738	3.0/0.0/0.0	$-$ 45,819	5.0/0.0/0.0
	0.5	$-$ 45,243	5.0/0.0/0.0	$-$ 43,646	4.0/1.0/1.0	$-$ 41,515	4.0/1.0/2.0	$-$ 40,142	5.0/1.0/1.0
	1	$-$ 45,243	5.0/0.0/0.0	$-$ 42,123	5.0/2.0/2.0	$-$ 38,215	5.0/4.0/4.0	$-$ 36,644	5.0/3.0/4.0
	2	$-$ 45,243	5.0/0.0/0.0	$-$ 41,253	3.0/2.0/2.0	$-$ 34,623	4.0/3.0/4.0	$-$ 29,670	4.0/5.0/5.0
	3	$-$ 45,243	5.0/0.0/0.0	$-$ 41,253	3.0/2.0/2.0	$-$ 33,877	3.0/3.0/4.0	$-$ 28,486	4.0/3.0/5.0

Table 11: Drone speed sensitivity analysis on the ttd300 benchmark. For each instance size

N

and speed factor

\phi=v_{\mathrm{D}}/v_{\max}

(where

\phi=0

establishes the truck-only baseline), each endurance-fraction column group reports the objective value

G

on the first layout (L1), alongside the division of collected cities across the truck, drone, and rendezvous points. The best objective value per

(N,f)

block is highlighted in bold.

Param	Value	$f$	$N=10$	$N=20$	$N=30$	$N=40$	$N=50$	$N=75$	$N=100$
baseline	—	0.25	$-$ 45,243	$-$ 54,905	$-$ 52,774	$-$ 43,626	$-$ 45,767	$-$ 43,424	$-$ 44,720
		0.50	$-$ 41,253	$-$ 48,705	$-$ 36,715	$-$ 32,699	$-$ 27,221	$-$ 33,963	$-$ 38,322
		0.75	$-$ 34,623	$-$ 29,439	$-$ 30,404	$-$ 32,804	$-$ 27,166	$-$ 34,561	$-$ 32,453
		1.00	$-$ 29,670	$-$ 27,953	$-$ 29,843	$-$ 32,515	$-$ 27,858	$-$ 31,554	$-$ 38,929
$R$	1	0.25	7,415	16,039	23,626	32,842	38,891	56,857	81,349
		0.50	7,507	16,178	24,009	33,063	39,240	57,062	81,543

Table 12: One-at-a-time sensitivity analysis on the ttd300 benchmark across all four endurance fractions, Part 1 (

R

and

W

). Each parameter block evaluates variations from a shared baseline configuration (

R=50

W=1\times

nominal capacity,

v_{\min}=0.1

\phi=2

). Within each tested parameter value, the four rows correspond to the endurance fractions

f=E_{\mathrm{D}}/d_{\max}\in\{0.25,0.5,0.75,1.0\}

. Every entry details the objective value

G

for that size, obtained from a single run on the first layout (L1). The highest

G

in each (block, size,

f

) subset is in bold. Part 2 (Table 13 ) reports on

v_{\min}

and

\phi

Param	Value	$f$	$N=10$	$N=20$	$N=30$	$N=40$	$N=50$	$N=75$	$N=100$
$v_{\min}$	0.05	0.25	$-$ 45,335	$-$ 55,161	$-$ 54,348	$-$ 45,032	$-$ 46,223	$-$ 45,123	$-$ 46,756
		0.50	$-$ 41,376	$-$ 48,976	$-$ 36,955	$-$ 34,944	$-$ 29,299	$-$ 35,728	$-$ 38,455
		0.75	$-$ 34,792	$-$ 29,434	$-$ 32,166	$-$ 33,620	$-$ 29,972	$-$ 33,541	$-$ 40,192
		1.00	$-$ 29,826	$-$ 28,415	$-$ 30,050	$-$ 33,627	$-$ 29,838	$-$ 36,160	$-$ 41,311
	0.1	0.25	$-$ 45,243	$-$ 54,905	$-$ 52,774	$-$ 43,626	$-$ 45,767	$-$ 43,424	$-$ 44,609
		0.50	$-$ 41,253	$-$ 48,705	$-$ 36,715	$-$ 32,699	$-$ 27,221	$-$ 33,963	$-$ 37,082

Table 13: One-at-a-time sensitivity analysis on the ttd300 benchmark, Part 2 (

v_{\min}

and

\phi

), continuing from Table 12 . As in Part 1, parameter blocks evaluate variations from the shared baseline (

R=50

W=1\times

v_{\min}=0.1

\phi=2

). Within each value, the four rows represent the endurance fractions

f\in\{0.25,0.5,0.75,1.0\}

, and each entry is the objective

G

derived from a single run on the first layout (L1). The highest

G

in each (block, size,

f

) subset is in bold.

Net objective $G$
$f$	$N=10$	$N=20$	$N=30$	$N=40$	$N=50$	$N=75$	$N=100$
0.25	$-$ 41,934	$-$ 51,283	$-$ 47,430	$-$ 48,082	$-$ 47,842	$-$ 36,661	$-$ 35,002
0.50	$-$ 38,444	$-$ 39,297	$-$ 33,850	$-$ 33,602	$-$ 31,221	$-$ 29,438	$-$ 29,890
0.75	$-$ 31,818	$-$ 28,656	$-$ 29,228	$-$ 32,053	$-$ 30,681	$-$ 30,538	$-$ 29,639
1.00	$-$ 25,790	$-$ 27,292	$-$ 29,213	$-$ 31,902	$-$ 31,671	$-$ 30,654	$-$ 31,986
Makespan $\tau_{0^{\prime}}$

Table 14: Full-budget SA reference solutions for the ttd300 instances, categorised by size

N

and endurance fraction

f

. The table reports the net objective

G

, the makespan

\tau_{0^{\prime}}

, and the time at which the search last improved (expressed as a percentage of the computational budget

B(N)

Combinatorial Optimization

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

See all 382 papers

Jun 26, 2026

Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones

Truck-drone delivery is an emerging last-mile logistics mode combining the long-haul capacity of trucks with the flexible service capability of drones. In locker-based operations, smart lockers serve not only as temporary parcel storage facilities but also as automated drone docking and service nodes. These automated nodes support drone takeoff, landing, parcel handover, and battery replacement, thereby significantly extending the service range and operational flexibility of drone-assisted delivery networks. However, practical locker-based delivery systems face complex real-world challenges, requiring the integrated coordination of not only parcel delivery, return pickup, battery-constrained and load-dependent drone flights, but also necessary detours around restricted airspace. To address this practical and multifaceted challenge, this paper introduces a locker-based truck-drone routing problem with integrated considerations of pickups, deliveries, and no-fly zones (LTDRP-PDNF), with the objective of minimizing the total operational cost of a fleet of drone-equipped trucks. We formulate the route construction process as a Markov Decision Process and develop a two-stage deep reinforcement learning-based neural heuristic. The first stage utilizes an attention-based encoder and a Bidirectional Gated Recurrent Unit decoder to solve the truck-only routing problem, formulated as a capacitated vehicle routing problem. The second stage combines a policy-transfer strategy with a hybrid dispatch assignment heuristic to construct fully coordinated truck and drone routes for LTDRP-PDNF. Experiments on instances of different scales demonstrate that the proposed method outperforms metaheuristic and neural heuristic baselines in most cases while maintaining exceptionally short computation times, offering an effective, scalable solution framework under practical operational constraints.

Xuanyu Liu, Hui Hu, Jiao Zhao +2

College of Transportation Engineering, Chang’an University, China · Faculty of Science and Technology, University of Nottingham Ningbo China

Combinatorial Optimization Vehicle Routing RL for Combinatorial Optimization

Ask PDF

Jul 7, 2026

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time, establishing Pareto dominance over all competing methods on the reward-versus-compute frontier. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment.

Manish Kolachalam, Rani Malhotra

Autonomous Machines Applied Research Center Infosys Center for Imaging Technologies, Infosys Bengaluru, India

Vehicle Routing Greedy Optimization

Ask PDF

Oct 4, 2026

Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization

This paper investigates the real-time dispatch of a shared drone fleet for on-demand food delivery and urban road network monitoring. We consider a courier-drone collaborative setting in which couriers transport orders to launchpads and drones complete the final delivery leg to kiosks. Drones may consolidate multiple origin-destination orders within one flight and make monitoring-aware route adjustments to collect real-time traffic information subject to delivery-time constraints. This yields a joint decision problem coupling dynamic order-to-drone matching, multi-order pooling, routing, and time-varying monitoring under fleet-level competition and uncertainty. We propose monitoring-task orderization, which periodically converts road-network nodes with high congestion and stale information into virtual monitoring orders. Pooling these virtual tasks with food-delivery orders creates a unified heterogeneous task set and transforms the coupled matching-and-routing problem into an order-level decision process. Building on this abstraction, we formulate a decentralized graph-interdependent Multi-Agent Markov Decision Process and develop Graph Multi-Agent Q-Learning (Graph-MAQL), which captures localized inter-agent dependencies through bipartite match coordination graphs. Agent-task value estimates are then used as edge weights in a dynamic heterogeneous bipartite matching program for globally feasible execution. Experiments using real-world data reveal strong operational synergy between delivery and monitoring. Monitoring-task orderization improves monitoring performance by 25.1% with less than a 1% reduction in delivery performance, while Graph-MAQL improves the aggregate objective by up to 20.8%, reduces deadline violations by over 40%, and transfers zero-shot to higher demand intensity without retraining.

Yulong Hu, Meng Xu, Sen Li +1

Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Hong Kong, China · School of Architecture, Civil and Environmental Engineering (ENAC), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

Aerial Robotics Intelligent Transportation Systems Multi-Robot Task Allocation Cooperative MARL

Ask PDF

Abstract

Combinatorial Optimization

Explore similar work

Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization