Drive, Pack, Fly: The Travelling Thief Problem with Drone
Summary
This paper introduces the Travelling Thief Problem with Drone (TTP-D), which jointly optimizes ground routing, drone synchronization, and item selection using mixed-integer programming, metaheuristics, and attention-based deep reinforcement learning.
View Cached Full Text
Cached at: 08/18/26, 07:52 AM
Paper page - Drive, Pack, Fly: The Travelling Thief Problem with Drone
Source: https://huggingface.co/papers/2608.16435 Published on Aug 17
·
Submitted byhttps://huggingface.co/Murjani
Kabiron Aug 18
Abstract
The Travelling Thief Problem with Drone jointly optimizes ground routing, drone synchronization, and item selection to maximize profit, using mixed-integer programming, metaheuristics, and attention-based deep reinforcement learning with a hybrid refinement approach.
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 theTravelling 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 amixed-integer linear programthat solves small instances to optimality, and develop bothmetaheuristicsand anattention-based Deep Reinforcement Learning(DRL) policy for larger instances. We further propose alearner-initialised hybrid solver, in which theDRL policyconstructs an initial solution that a shortannealingrun 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.
View arXiv pageView PDFProject pageGitHub3Add to collection
Get this paper in your agent:
hf papers read 2608\.16435
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper1
#### Murjani/ttpd-weights Reinforcement Learning• Updatedabout 3 hours ago • 1
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2608.16435 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2608.16435 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
DRIFT: Decoupled Rollouts and Importance-Weighted Fine-Tuning for Efficient Multi-Turn Optimization
This paper proposes DRIFT, a framework that combines offline trajectories with importance-weighted supervised fine-tuning to efficiently achieve multi-turn interactive learning performance comparable to reinforcement learning.
Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints
This paper presents a modified JAMPR deep reinforcement learning model to solve the Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW), offering fast optimal solutions for small to medium-sized instances and suboptimal solutions for larger ones.
Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking
The paper proposes an event-driven framework using Transformer and deep reinforcement learning for dynamic multi-depot vehicle routing, comparing it with heuristic and optimization methods.
Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
This paper proposes a reward-density heuristic for dynamic multi-vehicle routing problems that matches the solution quality of metaheuristics like ALNS, GA, and SA while requiring two to three orders of magnitude less planning time, demonstrated on drone task allocation and urban taxi dispatch scenarios.
Vehicle routing problem using deep reinforcement learning - A case study about truck planning in the industry
This paper presents a deep reinforcement learning approach for solving vehicle routing problems, demonstrated through three industrial truck planning case studies. The proposed method achieves over 10% cost reduction compared to baseline results and discusses generalization to more VRP variants.