Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper tackles the Travelling Thief Problem with Drone (TTP-D), which optimizes the joint selection of items, vehicle routing, and drone flight synchronization to maximize profit while considering time-based rental costs. By formulating a mixed-integer linear program for small instances and employing both metaheuristics and an attention-based Deep Reinforcement Learning (DRL) policy for larger cases, the authors demonstrate significant improvements in operational efficiency. The hybrid solver, which combines DRL with a short annealing refinement, achieves near-optimal results with reduced computational resources compared to traditional metaheuristic approaches, revealing that rental ratios critically influence profitability.
A hybrid solver combining deep reinforcement learning and annealing refinement can achieve near-optimal routing solutions for the Travelling Thief Problem with Drone at a fraction of the computational cost.
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.