AI summaryⓘ
The authors study a problem where a vehicle collecting items gets slower as it carries more, but a drone can help by picking up distant items to save time and earn more profit. They introduce a new model called the Travelling Thief Problem with Drone (TTP-D), which plans what items to pick, the vehicle's route, and the drone's flights to maximize profit after costs. They create mathematical methods to solve small cases exactly and develop advanced machine learning and metaheuristic techniques for bigger cases. Their hybrid approach uses learning to start and then improves solutions quickly, performing well on tests but still using more computing for very large problems. They also find that the cost of renting the vehicle is the main factor influencing profits, while other factors have little effect.
Travelling Thief ProblemDrone routingMixed-integer linear programmingMetaheuristicsDeep Reinforcement LearningVehicle routingMakespanSensitivity analysisHybrid solverOperational profit
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.