PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kabir Murjani, Abhay Sobhanan

arXiv:2608.16435v1cs.AIcs.NEmath.OC

TL;DR

The Travelling Thief Problem with Drone jointly optimizes load-dependent collection routing, item selection, and synchronized drone flights. Using exact, metaheuristic, DRL, and hybrid methods, the paper finds that LISA approaches metaheuristic quality at substantially lower computational cost, though the largest instances still require the full annealing budget.

  • Problem

    The TTP-D must jointly handle load-dependent travel, packing, routing, and temporally valid truck-drone synchronization decisions.

  • Method

    The paper formulates an MILP and develops simulated-annealing and variable-neighborhood-search metaheuristics, an attention-based DRL policy, and the LISA hybrid solver.

  • Results

    Mean gaps of 1.6% and 5.1% were achieved with half the metaheuristic computational budget, although the largest instances still required the full annealing budget.

  • Takeaways & Limitations

    The rental ratio overwhelmingly determines mission profitability, while vehicle capacity and speed affect profit only marginally.

  • Takeaways & Limitations

    The heuristic search methods do not guarantee strictly improving performance, reflecting their heuristic nature.

Abstract

from arXiv · show

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.

1 Introduction · 2 Literature Review

The paper introduces TTP-D to jointly model load-dependent collection routing and synchronised truck–drone operations, addressing a gap between the Travelling Thief Problem and delivery-focused truck-and-drone routing. It combines exact optimisation, metaheuristics, DRL, and the LISA hybrid solver, while reviewing related work across TTP, collaborative routing, learning-based methods, and neural hybrids.

  • 1 Introduction: TTP-D addresses collection settings where accumulating vehicle load creates operational penalties and a drone retrieves outlying items within its range.The motivating applications include rural-clinic sample collection, recycling, and relief operations across damaged road networks.
  • 1 Introduction: The model bridges the TTP’s load-dependent routing and packing with truck-and-drone routing’s time-synchronised sorties.TTP omits multi-vehicle dynamics, while truck-and-drone routing is generally designed for delivery rather than collection.
  • 1 Introduction: A capacitated truck and single-package drone jointly choose collected customers, vehicle visits, launches, and rendezvous points from a common depot.The drone can collect at an outlying customer after launch from a truck-visited node and transfer the item at a later rendezvous node.
  • 1 Introduction: The study develops an exact MILP for small instances, SA and VNS metaheuristics for scalability, and a DRL construction policy for larger benchmarks.The MILP uses a piecewise-linear velocity approximation, while the metaheuristics use a common neighbourhood library and feasibility-preserving evaluation.
  • 1 Introduction: LISA combines a behaviour-cloned DRL policy with simulated annealing, achieving comparable performance with only 5–50% of the runtime budget.On the benchmarks, the hybrid reaches mean gaps of 1.6% and 5.1% using half of the baseline metaheuristic’s computational budget.
  • 2 Literature Review: The literature review covers four streams: the TTP, truck-and-drone collaborative routing, learning-based methods, and hybrid algorithms.The review frames TTP as the single-vehicle variant, collaborative routing as the basis for synchronised sorties, and learning and hybrid methods as motivations for the DRL policy and LISA.
  • 2 Literature Review: TTP couples TSP and KP through weight-dependent velocity, making routing and packing inseparable, while established heuristics remain hand-crafted and exact formulations become intractable beyond larger instances.The a280 benchmark is drawn from TSPLIB, which became the standard benchmark suite for this literature.
  • 2 Literature Review: Prior truck-and-drone research began with the Flying Sidekick TSP and expanded to exact methods, multi-drone fleets, two-echelon systems, and arc routing; neural hybrids similarly combine learned construction with search.Related learning work includes attention-based construction, imitation learning, learned branching or repair decisions, and search over trained policies.

3 Problem Description

The TTP-D jointly determines truck–drone routes, customer visit modes, item collection, packing, and temporally valid sorties under load-dependent truck travel times. The problem uses a single truck and drone that start and finish at the depot, with capacity, speed, and sortie constraints shaping feasible plans.

  • Visit and collection decisions: Every customer is visited exactly once by either the truck or drone, but only selected visited customers have their items collected.Visitation and collection are distinct decisions, so visiting a customer does not imply collecting its item.
  • Joint decisions: The TTP-D simultaneously optimises customer-visit modes, packing configurations, vehicle routes, and temporally valid launch-and-rejoin pairings.Payload-dependent truck speeds create nonlinear travel times and complicate truck–drone synchronisation; the problem is NP-hard.
  • Modelling assumptions: The static deterministic setting uses one truck and one drone starting and ending at the depot, one item per customer, constant drone speed vD, and shared symmetric Euclidean distances.Loading, unloading, and handover delays are negligible or incorporated into travel distances.
  • Drone operations: A drone sortie launches where the truck is present, visits one target customer, and rejoins the truck later, with the first vehicle waiting at rendezvous while rental time continues.Each sortie contains exactly two drone arcs, and the drone-collected weight transfers to the truck after rendezvous.
  • Vehicle and capacity constraints: The truck has knapsack capacity W, while its speed decreases affinely from vmax when empty to vmin at capacity; arc travel time uses departing load.Because capacity is finite, collecting every item may be infeasible.

4 Mathematical Formulation

The TTP-D formulation maximises collected profit minus makespan-proportional rental cost while jointly modelling truck routing, drone sorties, payload tracking, load-dependent travel time, synchronisation, and valid makespan bounds. Nonlinear travel-time and weight terms are handled through SOS2 piecewise linearisation and McCormick envelopes.

  • 4.1 Objective, Routing, and Assignment: The objective maximises total collected profit minus a rental cost proportional to the makespan τ0′.
  • 4.1 Objective, Routing, and Assignment: Each customer is assigned exactly one visitation mode: truck-only, drone-only, or truck service at a rendezvous node.
  • 4.1 Objective, Routing, and Assignment: Truck flow conservation and node restrictions define routes through truck-only or rendezvous-designated nodes.
  • 4.1 Objective, Routing, and Assignment: Drone degree and anchor constraints structure sorties as launch and return legs containing at least one rendezvous node, preventing inter-customer hopping.
  • 4.2 Payload and Weight Tracking: The drone collects at most one item per sortie, bounded by its payload limit W D.
  • 4.2 Payload and Weight Tracking: Truck weight propagates along active arcs from initial zero load, incorporating truck pickups and drone-item transfers; McCormick envelopes linearise the bilinear transfer term.The formulation imposes 0 ≤Wi ≤W and uses an auxiliary variable λkj ∈[0, 1].
  • 4.3 Travel Time and Synchronisation: Truck velocity decreases affinely with load, making reciprocal travel time strictly convex and increasing; SOS2 chord interpolation over K uniform breakpoints provides the approximation.The breakpoints span the realisable load range [0, wtot].
  • 4.3 Travel Time and Synchronisation: The SOS2 chord lies above the true reciprocal travel-time curve, guaranteeing a conservative approximation of the travel-time function.

5 Solution Methods

Because MILP is tractable only for small instances, the paper develops scalable metaheuristic, DRL, and hybrid solution methods for the coupled route–pack–sortie problem. The hybrid LISA approach combines a learned construction policy with simulated annealing to bridge rapid inference and high-quality instance-specific optimisation.

  • Overview: Three scalable approaches are introduced: per-instance metaheuristic search, offline-trained reinforcement learning for single-pass construction, and a learner-initialised hybrid solver.The approaches increase in sophistication and shift computational effort progressively from instance-time search to offline training.
  • Metaheuristics: Metaheuristics explore the joint route–pack–sortie space using a shared move library and feasibility-preserving evaluation, with VND, SA, and VNS search strategies.The move library modifies collection decisions, truck routes, and drone sorties; larger instances sample at most 30N candidates per operator per pass.
  • Metaheuristics: Simulated annealing starts from a nearest-neighbour solution, initially accepts roughly 80% of worsening moves, cools with α = 0.97, and reheats below 10−4T0.It uses a single VND descent for initialization and a final descent to polish the best solution found.
  • Deep Reinforcement Learning: The DRL policy constructs feasible TTP-D solutions sequentially with an encoder–decoder architecture, modelling the problem as a finite-horizon deterministic MDP.The state tracks truck position, elapsed time, load, visited customers, and drone status; training uses PPO and a POMO multi-start group baseline.
  • Learner-Initialised Simulated Annealing: LISA distils full-budget SA solutions into certified MDP action sequences, trains the attention policy by behaviour cloning, and uses the policy to initialise a short SA refinement run.It bridges rapid single-pass inference from the learned policy with the instance-specific optimisation of SA.

6 Computational Study

The computational study shows that exact optimisation is practical only on small instances, while simulated annealing provides the strongest scalable performance. On the ttd300 benchmark, expanding drone endurance improves objectives, but rental costs still exceed collected profit at the tested rental ratio.

  • Exact optimisation: The MILP solves all N = 5 and N = 10 instances to proven optimality, but reaches mean relative gaps of 5.94% at N = 15 and 40.05% at N = 20.Mean total runtimes are 0.5 and 49.1 seconds for N = 5 and N = 10; larger exact runs are constrained by the 24-hour limit.
  • Solution structure: Across instance classes, drone offloading covers 3/5, 4/10, 7/15, and 10/20 customer visits for N = 5, 10, 15, and 20, respectively.Offloading preserves higher truck travel speeds by maintaining a lighter ground-vehicle payload.
  • Mid-sized instances: LISA bridges metaheuristics and learned policies, reaching gaps of 0.11% at N = 15 and 1.38% at N = 20 with computational budget β ≥33.3%.At N = 20, five minutes of simulated annealing achieves superior objective values to the exact solver after 24 hours.
  • Large instances: At N ≥30, SA establishes all BKS solutions and achieves the lowest mean gap of 0.04%, while VNS, GAT, and MLP reach 7.17%, 8.42%, and 9.95%.VNS deteriorates from 5.14% at N = 30 to 27.07% at N = 50.
  • Endurance sensitivity: On ttd300, increasing endurance from f = 0.25 to f = 0.50 improves the objective across all 35 layouts, by 8.3% of |G| at N = 10 and 34.7% at N = 50.Beyond f = 0.50, improvement flattens; at N ≤20, objectives continue improving through f = 1.00.
  • Profitability sensitivity: At R = 50 and f = 0.50, the rental term exceeds collected profit at every size, so no operating point is purely profitable.The shortfall narrows as N grows because profit accumulates faster than mission duration lengthens.

7 Sensitivity Analysis

Sensitivity analysis shows that multi-item collection and faster drones can improve outcomes, but endurance limits the value of drone speed. Economic conditions dominate profitability, with renting ratio exerting the strongest influence and capacity the most influential physical parameter.

  • Multi-item collection: Allowing multiple items per city improves the objective at every size and endurance fraction, with gains rising from 1,626–4,004 at N = 10 to 40,058–53,945 at N = 100.At N = 100, the improvement reaches +13,342 for f = 1.00 and produces positive objectives at every endurance fraction.
  • Drone speed: Drone speed produces non-decreasing objective values in nearly every (N, f) block, with the largest gains from initial speed increases and diminishing returns thereafter.At N = 100 and f = 0.50, the objective improves from −89,453 with no drone to −27,590 at ϕ = 3.
  • Drone speed: Endurance constrains drone-speed benefits: at N = 10 and f = 0.25, the objective remains −45,243 across all speeds, while ϕ = 3 improves N = 100 by only 33,617.The tight flight radius prevents sorties under the shortest endurance, forcing the truck to visit collected customers alone.
  • Parameter sensitivity: Renting ratio dominates physical parameters, ranging from +81,408 at R = 1 to −382,171 at R = 200 for N = 100 and f = 1.00.Lowering R to 25 makes operations profitable for N ≥40 when f ≥0.5, or from N = 75 at the tightest radius, without hardware upgrades.
  • Parameter sensitivity: Among physical parameters, capacity has the strongest effect, improving the objective from −82,931 to −17,648, followed by drone speed from −57,656 to −23,416 and minimum truck speed from −41,311 to −18,705.At f = 0.25, endurance compresses the N = 100 performance range of ϕ to roughly 27,000 and eliminates it at N = 10, while leaving renting-ratio and capacity impacts comparatively unaffected.

8 Conclusions

The paper introduced TTP-D and a suite of exact, metaheuristic, learning-based, and hybrid solution methods. Experiments show that LISA narrows the quality gap at lower computational cost, while rental ratio and drone endurance dominate operational profitability.

  • Problem and methods: TTP-D couples load-dependent travel times and knapsack packing with time-synchronised, single-package drone sorties.The paper addresses the problem with an exact MILP formulation, SA and VNS metaheuristics, an attention-based DRL policy, and the LISA hybrid algorithm.
  • Computational findings: N = 10 is the largest instance size for which the exact solver certifies optimality, while SA provides a robust larger-scale quality reference.Learned policies construct solutions rapidly but struggle to match metaheuristic quality on larger instances.
  • Computational findings: LISA recovers near-metaheuristic performance at a fraction of the computational budget by warm-starting a truncated search with the learned policy.This hybrid approach bridges the quality gap between learned construction policies and metaheuristic solutions on larger instances.
  • Operational implications: The time-based rental ratio overwhelmingly dictates mission profitability, overshadowing vehicle capacity and speed.The sensitivity analysis identifies rental ratio as the primary operational driver.
  • Operational implications: Drone endurance is a strict bottleneck, making extended operational range a higher priority than increased flight speed.The paper frames endurance as a limiting operational factor for logistics operators.

Supplementary Material for Drive, Pack, Fly: The Travelling Thief Problem with

The supplementary material is organized into six sections covering model-supporting tables and analyses, sensitivity results, and endurance information for the ttd300 benchmark.

  • Sections S1–S4: Sections S1–S4 provide constant tables, a piecewise-linear error-bound derivation, an ablation study, and a seed-dispersion table.These sections contain the supplementary material’s methodological and experimental support.
  • Section S5: Section S5 details the sensitivity analysis results.The supplementary material separates sensitivity findings into their own section.
  • Section S6: Section S6 provides the endurance reference for the ttd300 benchmark.This benchmark-specific endurance information is included as the final supplementary section.

S1. Constants of the model and the learning pipeline

This section specifies the disjunctive constants and learning hyperparameters supporting the formulation and training pipeline. It also records the implementation stack, reproducibility settings, batched decoding strategy, and checkpoint-selection rule.

  • Model constants: Table 7 provides the big-M values for the formulation’s travel-time and synchronisation constraints.These disjunctive constants support the mixed-integer formulation described in the manuscript.
  • Implementation: The model and training pipeline use PyTorch 2.4.0, with NumPy supporting the environment.Training configuration is shared through Table 8.
  • Training and selection: The pipeline maintains high accelerator utilisation through lockstep batched decoding and fixes instance-sampling and weight-initialisation randomness at 2026.For each problem size, the final solver is the checkpoint with the lowest held-out gap during training.

S2. Error of the piecewise-linear travel time

The SOS2 formulation exactly evaluates a piecewise-linear interpolant that conservatively overestimates truck travel times, yielding a worst-case objective-error bound that decreases as O(K−2). The bound is conservative in practice, but explains discrepancies between interpolant-optimised MILP objectives and exact-law evaluations.

  • Exact SOS2 evaluation: The SOS2 constraints evaluate the piecewise-linear interpolant exactly, so the model’s approximation error is precisely the interpolation error.At most two consecutive interpolation weights can be nonzero, making the evaluated value equal to the chord at the realised load.
  • One-sided error: Because reciprocal speed is strictly convex, the chord interpolant never underestimates travel time: ˆψi ≥1/vi and ϵψ ≥0.Equality holds at the breakpoints.
  • Objective-error bound: The per-node interpolation error, propagated over at most N + 1 truck arcs, produces an objective-error bound that decreases as O(K−2).The bound is conservative because it charges the maximum interpolation error, maximum arc length, and full-capacity speed to every relevant term.
  • Computational interpretation: The conservative residual error explains why MILP values at N = 15 can fall below the annealing optimum when K = 10 interpolant break-points are optimised but objectives use the exact load–speed law.Instances whose collected weight remains well below capacity can realise substantially less error than the worst-case bound.

S3. Decode-strategy ablation

The learned policy’s decoder is selected from seven strategies arranged by increasing computational cost. Beam search is chosen because it achieves the lowest gap at three of four instance sizes while remaining far cheaper than the metaheuristic budgets used at relevant sizes.

  • Decoder selection: Seven decoding strategies are evaluated in an increasing-compute progression, from greedy rollout through POMO variants, sampling, beam search, and active search.The progression includes active search both alone and combined with beam search.
  • Decoder selection: Greedy decoding trails the MILP optimum by 9.5% to 36.0%, while plain POMO multi-start trails it by 7.8% to 21.9% with augmentation.These gaps are reported consistently across the four instance sizes.
  • Decoder selection: Beam search attains the lowest gap at three of the four instance sizes.The selected decoder is marked in the ablation plots comparing gap to certified MILP optimum against decode runtime.
  • Decoder selection: The beam-search cost is accepted because per-instance decoding remains far below the metaheuristic budgets at the sizes where the policy is used.The resulting quality is also distilled into the LISA hybrid’s warm start.

S4. Seed dispersion on the a280 benchmark

On the a280 benchmark, seed-to-seed dispersion measures run-to-run variability in the objective across ten seeds, averaged over five instances per size. Simulated annealing remains highly concentrated, with dispersion below 1% through N = 20 and below 2.4% through N = 50, while VNS matches this concentration only through N = 15.

  • Dispersion metric: Table 9 reports seed-to-seed dispersion of the objective (%) on the a280 benchmark.The comparison covers the two per-instance searches.
  • Dispersion metric: Dispersion is the standard deviation of the objective across ten seeds, expressed as a percentage of each instance’s mean absolute objective and averaged over five instances per size.Mean gaps alone can hide run-to-run variability.
  • Simulated annealing: Below 1%: simulated annealing’s dispersion stays below 1% of the objective through N = 20.This indicates concentration as well as strong performance over these instance sizes.
  • Simulated annealing: Below 2.4%: simulated annealing’s dispersion stays below 2.4% through N = 50.The stated threshold applies through the largest reported size in the passage.
  • VNS: VNS matches simulated annealing’s concentration only through N = 15.The supplied passage does not report VNS dispersion beyond this size.

S5. Details of the sensitivity analysis

The sensitivity analysis evaluates drone-collection strategies and parameter effects on the ttd300 benchmark under controlled solver, layout, endurance, and budget settings. It covers multi-item collection, drone speed, and one-at-a-time parameter sweeps, with larger-instance deviations attributed to limited runtime coverage of the expanding search space.

  • Experimental setup: All sensitivity entries use simulated annealing with ttd300 per-size budgets across seven instance sizes, layout L1, and four endurance fractions.Every plan is validated by the exact endurance-aware evaluator before scoring.
  • Experimental setup: Experiments use layout L1 and a single seed, except Table 10, which uses five seeds for the larger multi-item search space.The objective is G = PΣ_i p_i z_i − Rτ′_0, where less negative values are better.
  • Interpretation of larger instances: Minor deviations from general trends in instances with N ≥50 reflect fixed runtime budgets covering a diminishing share of the expanding solution space.This is identified as standard metaheuristic behaviour rather than a change in the underlying experimental design.
  • Multi-item comparison: Table 10 compares multi-item and single-item collection, reporting G_MI, G_SI, ΔG, and operational metrics across instance sizes and endurance fractions.The comparison uses the best result across independent runs under the same per-size budget on layout L1.
  • Drone-speed sensitivity: Table 11 sweeps the drone speed factor ϕ, including ϕ = 0 as the truck-only baseline, and reports objective values and collection allocation across truck, drone, and rendezvous points.Results are grouped by instance size and endurance fraction on layout L1.
  • Parameter sweeps: Tables 12 and 13 vary R, W, v_min, and ϕ one at a time from a shared baseline across four endurance fractions, reporting objective G for each tested size and parameter value.Tables 12 and 13 use a single run on layout L1, with the highest G highlighted within each block, size, and endurance subset.

S6. The endurance axis on ttd300 instances

The endurance-axis evaluation on ttd300 instances uses full-budget simulated-annealing reference solutions because no exact method can certify optimality. Table 14 reports averaged net objective, rental-cost-determining makespan, and search-improvement timing across instance sizes and endurance fractions.

  • Evaluation basis: No exact method can certify optimality on the ttd300 benchmark, so the endurance axis is evaluated using reference solutions.These reference solutions are evaluated in Section 6.2.2 of the main paper.
  • Reported measures: Each cell averages five layouts and reports the net objective G, makespan τ0′, and last-improvement time as a percentage of computational budget B(N).The makespan τ0′ dictates the rental cost, while the last-improvement point indicates when the search last improved.
  • Reference solutions: Table 14 categorises full-budget simulated-annealing reference solutions by instance size N and endurance fraction f.The table presents the reference values for the ttd300 instances.
Loading 2608.16435v1…