Kabir Murjani, Abhay Sobhanan
6 min
Modern collection operations—such as couriers picking up samples from rural clinics, recycling vehicles emptying bins, or relief trucks retrieving supplies—share a dual challenge: vehicles accumulate payload progressively, which slows them down and penalizes routing efficiency, while outlying items are expensive to reach by road. Although drones can bypass road networks to fetch light, high-performance items, their operations must be strictly synchronized with the ground vehicle's schedule. This paper introduces the Travelling Thief Problem with Drone (TTP-D), combining load-dependent vehicle routing, item packing, and flight synchronization to maximize operational profit minus rental costs.
The TTP-D couples the Travelling Salesman Problem, the Knapsack Problem, and truck-drone routing. A capacitated truck and a single-package drone start from a common depot, visit all customer locations, and return to the depot. Every customer is visited exactly once, either by the truck alone, by the drone alone, or by the truck at a rendezvous node. The truck's velocity decreases linearly with its accumulated load, meaning early pickups penalize all subsequent travel times. The drone launches from a node where the truck is present, retrieves an item from an outlying customer, and hands it over to the truck at a subsequent rendezvous node. The objective is to maximize collected profit minus a rental cost proportional to the makespan.
Because the TTP-D is NP-hard and exact mixed-integer linear programs (MILPs) only scale to small instances, the authors develop scalable alternatives. These include Simulated Annealing (SA) and Variable Neighbourhood Search (VNS) metaheuristics, as well as an attention-based Deep Reinforcement Learning (DRL) construction policy. To bridge learning and search, the paper introduces LISA (Learner-Initialized Simulated Annealing). LISA uses a neural policy trained via imitation of metaheuristic solutions to generate a high-quality initial plan, which is then refined by a short local search. This hybrid recovers most of the metaheuristic's solution quality at a fraction of its computational budget.
Computational results across benchmark families indicate that the LISA hybrid achieves mean performance gaps of 1.6% to 5.1% compared to the baseline metaheuristic while utilizing only half the runtime budget. Furthermore, a sensitivity analysis reveals that the rental ratio is the primary driver of fleet profitability, whereas fleet parameters such as drone speed affect profit only at the margin.
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.
Sam: So the machine learning does the rough work, and the search algorithm does the polishing.
Alex: Exactly. Together, they find high-quality routes without burning hours of computing time. That matters because in real logistics, schedules shift. A system that takes three hours to recalculate a route isn't useful.
Sam: That makes sense. What did the researchers actually find when they tested it?
Alex: A few things stood out. The most striking finding was about what actually drives profitability. You might expect that giving the truck more carrying capacity, or making the drone faster, would be the biggest levers. But the research found something different.
Sam: What was it?
Alex: The financial structure of the operation, specifically how the service is priced and rented over time, had a far larger effect on overall mission profitability than any physical upgrade. Tweaking the truck's capacity or the drone's speed produced modest, incremental gains. But changing the pricing model fundamentally altered whether the operation made money at all.
Sam: So the business model matters more than the hardware. That's a useful reality check for anyone thinking about deploying these systems.
Alex: It is. And on the hardware side, the research did identify one physical factor that acts as a genuine bottleneck: drone battery range. A drone that can fly further is far more valuable than a drone that simply flies faster. Speed only helps if the drone has enough battery to reach its target in the first place.
Sam: Range before speed. Got it. What about the rules around how many items can be collected at each stop?
Alex: The original setup allowed only one item per location. When the researchers relaxed that restriction and allowed multiple items per stop, the results were meaningful, particularly at larger scales. Operations that were running at a loss became profitable. The reason is straightforward: if you're already stopping somewhere, collecting more items at that stop costs you very little extra, but it makes much better use of the truck's capacity.
Sam: It's like filling a shopping trolley properly instead of making five separate trips.
Alex: That's exactly the logic. And it's a practical design choice that logistics operators can actually implement without any new hardware.
Sam: So what are the limits of this research? Where does it break down?
Alex: The authors are clear about this. The exact mathematical version of the problem becomes computationally unmanageable once you go beyond roughly twenty customer locations. For larger networks, you have to rely on the approximate solver, which is good but not guaranteed to find the perfect answer.
Sam: And the machine learning component?
Alex: It needs to be retrained if the scale of the problem changes significantly, or if the geographic layout is very different from what it was trained on. So it's not a one-size-fits-all tool yet.
Sam: What comes next for this line of research?
Alex: The paper points toward several open directions: handling multiple drones at once, allowing a single drone flight to serve more than one customer, accounting for the time it takes to hand off packages, and eventually dealing with real-world uncertainty, like weather or traffic, rather than assuming everything goes to plan.
Sam: A lot of moving parts still to work out.
Alex: There are. But the framework this paper establishes gives researchers and logistics planners a clearer picture of where the real constraints lie. And sometimes knowing which knobs actually matter is the most useful starting point. Thanks for listening to ResearchPod.