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

• URL: http://arxiv.org/abs/2608.16435v1
• Date: Mon, 17 Aug 2026 11:34:15 GMT
• Title: Drive, Pack, Fly: The Travelling Thief Problem with Drone
• Abstract summary: In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency.<n>An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit.<n>This paper introduces the Travelling Thief Problem with Drone (TTP-D), which maximises the collected profit, net of a time-based rental cost.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Dynamical Vehicle Orienteering Problem for Multi-Rotor Unmanned Aerial Vehicles [3.5945543871230274]
  The Dynamical Vehicle Orienteering Problem (DVOP) is a generalization of the Orienteering Problem (OP)<n>We study the DVOP in the context of multi-rotor Aerial Unmanned Vehicle (UAV) flight planning.
  arXiv  Detail & Related papers  (2026-07-15T12:48:18Z)
• Fast-dDrive: Efficient Block-Diffusion VLM for Autonomous Driving [54.31800246594724]
  We present Fast-dDrive, a block-diffusion VLA that performs bidirectional refinement within semantic units.<n>We show that Fast-dDrive redefines the speed-accuracy frontier for driving agents.
  arXiv  Detail & Related papers  (2026-05-22T02:31:32Z)
• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• Hybrid Reinforcement Learning and Search for Flight Trajectory Planning [6.651730814910398]
  This paper explores the combination of Reinforcement Learning (RL) and search-based path planners to speed up the optimization of flight paths for airliners.<n>The fundamental idea is to train an RL Agent to pre-compute near-optimal paths based on location and atmospheric data and use those at runtime to constrain the underlying path planning solver.<n>The approach effectively reduces the size of the solver's search space, significantly speeding up route optimization.
  arXiv  Detail & Related papers  (2025-09-04T11:01:43Z)
• Collaborative Last-Mile Delivery: A Multi-Platform Vehicle Routing Problem With En-route Charging [5.93228031688634]
  This research introduces a novel synchronized multi-platform vehicle routing problem with drones and robots.<n>A fleet of $mathcalM$ trucks, $mathcalN$ drones and $mathcalK$ robots cooperatively delivers parcels.<n>Trucks serve as mobile platforms, enabling the launching, retrieving, and en-route charging of drones and robots.
  arXiv  Detail & Related papers  (2025-05-29T15:58:01Z)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• A Multi-Objective approach to the Electric Vehicle Routing Problem [0.0]
  The electric vehicle routing problem (EVRP) has garnered great interest from researchers and industrialists in an attempt to move from fuel-based vehicles to healthier and more efficient electric vehicles (EVs) Previous works target logistics and delivery-related solutions wherein a homogeneous fleet of commercial EVs have to return to the initial point after making multiple stops. We perform multi-objective optimization - minimizing the total trip time and the cumulative cost of charging.
  arXiv  Detail & Related papers  (2022-08-26T05:09:59Z)
• Motion Planning and Control for Multi Vehicle Autonomous Racing at High Speeds [100.61456258283245]
  This paper presents a multi-layer motion planning and control architecture for autonomous racing. The proposed solution has been applied on a Dallara AV-21 racecar and tested at oval race tracks achieving lateral accelerations up to 25 $m/s2$.
  arXiv  Detail & Related papers  (2022-07-22T15:16:54Z)
• Time-Optimal Planning for Quadrotor Waypoint Flight [50.016821506107455]
  Planning time-optimal trajectories at the actuation limit of a quadrotor is an open problem. We propose a solution while exploiting the full quadrotor's actuator potential. We validate our method in real-world flights in one of the world's largest motion-capture systems.
  arXiv  Detail & Related papers  (2021-08-10T09:26:43Z)
• The two-echelon routing problem with truck and drones [0.0]
  We study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems.
  arXiv  Detail & Related papers  (2020-04-05T18:33:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.