| title | Drive, Pack, Fly: The Travelling Thief Problem with Drone |
|---|---|
| authors | Kabir Murjani, Abhay Sobhanan |
| date | 2026-08-17 |
| venue | arXiv (preprint, not peer reviewed) |
| id | arXiv:2608.16435 |
| upvotes | 2 (Hugging Face Daily Papers, 2026-11-01) |
| links | abs pdf hf code |
| 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. |
cite
@misc{murjani2026drive,
title={Drive, Pack, Fly: The Travelling Thief Problem with Drone},
author={Kabir Murjani and Abhay Sobhanan},
year={2026},
eprint={2608.16435},
archivePrefix={arXiv},
url={https://arxiv.org/abs/2608.16435}
}