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

The Problem

A delivery vehicle collects items along a route, but each pickup adds weight—slowing the truck and stretching delivery times. The insight: send a drone to grab distant items instead, so the truck stays lighter and faster. But there's a catch. The drone's flight window depends on when the truck arrives at each stop, and every item the truck picks up reshuffles those arrival times, which then changes where and when the drone can launch and land. The authors frame this as the Travelling Thief Problem with Drone (TTP-D): simultaneously decide which items to collect, how to route the ground vehicle, and how to choreograph drone flights—all to maximize profit after paying the drone's rental fee.

Standard routing problems assume a fixed vehicle speed. TTP-D couples routing to payload mass in a way that makes joint optimization unavoidable. Picking up one item early can delay a later stop enough to make a drone intercept infeasible, or vice versa. The authors show that greedy or sequential approaches miss these interdependencies.

Methods and Results

The authors start with a mixed-integer linear program that solves small instances exactly, confirming the problem structure and baseline optimal values. For realistic sizes, they pursue three scalable approaches.

Metaheuristics (tabu search, simulated annealing–type methods) form the performance baseline. These are computationally expensive but typically find high-quality solutions.

Deep Reinforcement Learning trains an attention-based neural network policy to construct solutions from scratch. DRL is much faster—orders of magnitude on large instances—but trades solution quality. Standalone DRL typically recovers only a fraction of metaheuristic profit within tight time budgets.

Hybrid solver combines both: the DRL policy generates an initial solution in seconds, then a short metaheuristic refinement pass polishes it. On two benchmark datasets, the hybrid achieves roughly 80–90% of the full metaheuristic's profit while using a fraction of the compute time. However, the largest instances still demand the metaheuristic at full budget to match that baseline.

What Drives Profitability

The sensitivity analysis surfaces a critical insight: the drone rental cost relative to item values is the dominant profit lever. Tweaking drone rental ratios swings profit far more than adjusting speed, battery capacity, or endurance. Vehicle parameters matter marginally. This suggests operators should negotiate rental terms aggressively and focus less on fleet hardware upgrades for this particular problem structure.

Why It Matters

Delivery networks operate under competing pressures—speed, payload capacity, and cost. Drone-assisted logistics is deployed in real operations (e.g., medical supply runs, remote deliveries), yet most research models drones and trucks independently. TTP-D bridges that gap by making the interdependency explicit and tractable. The hybrid solver demonstrates a practical trade-off: when compute budgets are tight, deep learning can seed solutions fast enough for operational use, even if the metaheuristic might find marginally better answers given unlimited time. For operators weighing drone adoption, the sensitivity analysis provides a data-driven argument: focus contract negotiations on rental cost, not hardware specs.