Drive, Pack, Fly: The Travelling Thief Problem with Drone
This paper introduces TTP-D, combining MILP, metaheuristics, and DRL to optimize truck-drone collection, boosting profit and efficiency.
Key Findings
Methodology
The TTP-D model employs a mixed-integer linear programming (MILP) formulation for small instances, ensuring optimality. For larger problems, the authors develop metaheuristics like Simulated Annealing (SA) and Variable Neighborhood Search (VNS) to rapidly generate high-quality solutions. Additionally, a deep reinforcement learning (DRL) policy based on attention mechanisms (GAT and MLP encoders) is trained via Proximal Policy Optimization (PPO) to construct feasible routes efficiently. The innovative hybrid approach, LISA, combines DRL-generated solutions with limited local search, enabling near-optimal solutions within reduced computational budgets. Extensive experiments on benchmark datasets demonstrate that this integrated framework achieves solutions close to the best-known results with significantly less computational effort.
Key Results
- On the a280 benchmark set, the MILP solver finds optimal solutions within minutes, achieving 100% of the benchmark profit. For the larger ttd300 instances, the hybrid LISA algorithm recovers approximately 95% of the optimal profit while reducing computation time by over 50%. The DRL policy accelerates solution construction by a factor of three compared to traditional heuristics, with stable performance across multiple runs.
- Sensitivity analysis reveals that the rental ratio (R) is the dominant factor influencing profitability, with higher R values leading to increased net gains. The drone’s endurance and speed parameters have a secondary effect, mainly constraining the feasible solution space. The hybrid method maintains robustness across different parameter settings, outperforming pure heuristics in both solution quality and efficiency.
- The combination of learning-based and heuristic methods yields solutions that are both high-quality and computationally efficient, making the approach suitable for real-time applications in logistics and disaster relief scenarios.
Significance
This research advances the state-of-the-art in multi-agent routing by integrating drone scheduling with load-dependent vehicle paths, a previously underexplored area. The hybrid framework effectively balances solution optimality and computational cost, addressing practical challenges in logistics operations. Its ability to handle complex constraints and large-scale instances paves the way for deploying autonomous multi-vehicle systems in real-world settings, such as rural healthcare, disaster response, and urban delivery. The combination of MILP, metaheuristics, and deep learning offers a versatile toolkit adaptable to various logistical problems, marking a significant step toward intelligent, scalable logistics automation.
Technical Contribution
The paper’s core technical innovation lies in the seamless integration of deep reinforcement learning with classical optimization and heuristic algorithms. The attention-based DRL policy learns to construct feasible routes, reducing reliance on computationally expensive exact methods for large instances. The LISA hybrid algorithm leverages imitation learning to produce high-quality initial solutions, which are then refined via limited local search, effectively combining learning and search paradigms. The SOS2 piecewise linear approximation of the load-dependent speed function ensures model tractability while accurately capturing non-linearities. These contributions collectively push the frontier of combinatorial optimization in multi-agent, load-dependent routing problems.
Novelty
This work is the first to explicitly model and solve the Travelling Thief Problem with Drone (TTP-D), integrating load-dependent vehicle speeds with synchronized drone sorties. Unlike prior studies focusing solely on delivery or single-vehicle routing, this research addresses the complex coupling of packing, routing, and timing constraints in a multi-agent setting. The innovative hybrid approach, combining deep learning with metaheuristics, provides a scalable solution framework that balances solution quality and computational efficiency, representing a significant leap forward in autonomous logistics research.
Limitations
- The model assumes static, deterministic parameters, which limits its applicability in dynamic, uncertain environments. Real-world scenarios often involve unpredictable travel times, variable payloads, and environmental factors that are not captured here.
- Training the DRL policy requires substantial computational resources and large datasets, which may hinder deployment in resource-constrained settings. Its generalization to unseen or highly variable instances remains an open question.
- Despite improvements, MILP-based solutions still face scalability issues for extremely large instances, necessitating further algorithmic innovations or distributed computing approaches.
Future Work
Future research should focus on extending the model to dynamic, stochastic environments, incorporating real-time data streams for adaptive scheduling. Developing multi-drone and multi-vehicle coordination frameworks will enhance scalability and robustness. Additionally, exploring transfer learning techniques could improve the generalization of DRL policies across diverse scenarios. Integrating these advances will facilitate deployment in complex, real-world logistics and emergency response systems, pushing autonomous multi-agent operations toward practical maturity.
AI Executive Summary
In recent years, the rapid development of drone technology has transformed logistics and collection operations, especially in remote or inaccessible areas. Traditional routing problems like the Traveling Salesman Problem (TSP) and Knapsack Problem (KP) have long served as foundational models for optimizing routes and payloads. However, real-world scenarios often involve complex interactions, such as load-dependent vehicle speeds and the need for precise synchronization between ground vehicles and aerial drones. These challenges have limited the effectiveness of classical approaches, especially in large-scale, dynamic environments.
This paper introduces the Travelling Thief Problem with Drone (TTP-D), a comprehensive framework that captures the intertwined nature of load-dependent routing and drone scheduling. The authors formulate the problem as a mixed-integer linear program (MILP), enabling exact solutions for small instances. For larger problems, they develop scalable heuristics based on Simulated Annealing (SA) and Variable Neighborhood Search (VNS), which provide high-quality solutions within practical timeframes. The most innovative contribution is the integration of deep reinforcement learning (DRL), specifically attention-based neural networks, trained via Proximal Policy Optimization (PPO). This approach allows the model to learn effective route construction policies offline, which can then be deployed rapidly.
Building on these methods, the authors propose LISA (Learner-Initialised Simulated Annealing), a hybrid algorithm that combines the strengths of learning and local search. LISA uses the DRL policy to generate an initial solution, then refines it through limited local optimization, achieving near-optimal solutions with significantly reduced computational costs. Extensive experiments on benchmark datasets, including the well-known a280 and the newly introduced ttd300 instances, demonstrate that LISA and the other scalable methods can recover most of the solution quality of the exact MILP while using only a fraction of the computational resources.
The results reveal critical insights: the rental ratio (cost per unit time) is the primary driver of profitability, overshadowing the influence of drone endurance or speed parameters. This highlights the importance of economic factors over purely technical constraints in operational planning. The approach’s ability to balance solution quality and computational efficiency makes it highly promising for real-world deployment, especially in scenarios requiring rapid decision-making under complex constraints.
Looking ahead, future work will explore dynamic environments, multi-drone systems, and real-time adaptive scheduling. Incorporating environmental uncertainties and expanding the model to multi-agent coordination will further enhance its practical relevance. Overall, this research marks a significant advance in autonomous logistics, offering a versatile, scalable framework that integrates classical optimization with modern machine learning techniques, paving the way for smarter, more efficient collection operations worldwide.
Deep Dive
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.
References (20)
Solving biobjective traveling thief problems with multiobjective reinforcement learning
Gemilang Santiyuda, Retantyo Wardoyo, Reza Pulungan
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim et al.
The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery
Chase C. Murray, Amanda Chu
Attention, Learn to Solve Routing Problems!
W. Kool, H. V. Hoof, Max Welling
Proximal Policy Optimization Algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal et al.
Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing
Mohamed El Yafrani, B. Ahiod
A branch-and-price algorithm for emergency humanitarian logistics with a mixed truck-drone fleet
Abhay Sobhanan, Sasan Mahmoudinazlou, Hadi Charkhgard et al.
The blood is here: Zipline's medical delivery drones are changing the game in Rwanda
E. Ackerman, Michael A. Koziol
Knapsack Problems: Algorithms and Computer Implementations
S. Martello, P. Toth
Learning to Branch in Mixed Integer Programming
Elias Boutros Khalil, P. L. Bodic, Le Song et al.
Neural Combinatorial Optimization with Reinforcement Learning
Irwan Bello, Hieu Pham, Quoc V. Le et al.
NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
Liang Xin, Wen Song, Zhiguang Cao et al.
Approximate Approaches to the Traveling Thief Problem
Hayden Faulkner, S. Polyakovskiy, Tom Schultz et al.
Optimization by Simulated Annealing
S. Kirkpatrick, C. D. Gelatt, M. Vecchi
Efficient Active Search for Combinatorial Optimization Problems
André Hottung, Yeong-Dae Kwon, Kevin Tierney
A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
Sasan Mahmoudinazlou, C. Kwon
Deep Reinforcement Learning for Dynamic Order Picking in Warehouse Operations
Sasan Mahmoudinazlou, Abhay Sobhanan, Hadi Charkhgard et al.
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
Chaitanya K. Joshi, T. Laurent, X. Bresson
A comprehensive benchmark set and heuristics for the traveling thief problem
S. Polyakovskiy, M. Bonyadi, Markus Wagner et al.