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.</p>\n","updatedAt":"2026-08-18T04:34:01.372Z","author":{"_id":"6856a5302e71b207b9704f48","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6856a5302e71b207b9704f48/bWu5bG78A-QLPHp1BzOfk.jpeg","fullname":"Kabir","name":"Murjani","type":"user","isPro":false,"isHf":false,"isHfAdmin":false,"isMod":false,"isUserFollowing":false}},"numEdits":0,"identifiedLanguage":{"language":"en","probability":0.9040355086326599},"editors":["Murjani"],"editorAvatarUrls":["https://cdn-avatars.huggingface.co/v1/production/uploads/6856a5302e71b207b9704f48/bWu5bG78A-QLPHp1BzOfk.jpeg"],"reactions":[],"isReport":false}}],"primaryEmailConfirmed":false,"paper":{"id":"2608.16435","authors":[{"_id":"6a83deef675db694db8cd5cd","name":"Kabir Murjani","hidden":false},{"_id":"6a83deef675db694db8cd5ce","name":"Abhay Sobhanan","hidden":false}],"publishedAt":"2026-08-17T00:00:00.000Z","submittedOnDailyAt":"2026-08-18T00:00:00.000Z","title":"Drive, Pack, Fly: The Travelling Thief Problem with Drone","submittedOnDailyBy":{"_id":"6856a5302e71b207b9704f48","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6856a5302e71b207b9704f48/bWu5bG78A-QLPHp1BzOfk.jpeg","isPro":false,"fullname":"Kabir","user":"Murjani","type":"user","name":"Murjani"},"summary":"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.","upvotes":1,"discussionId":"6a83deef675db694db8cd5cf","projectPage":"https://abhaysobhanan.github.io/team/","githubRepo":"https://github.com/corbit-lab/ttpd","githubRepoAddedBy":"user","ai_summary":"The Travelling Thief Problem with Drone jointly optimizes ground routing, drone synchronization, and item selection to maximize profit, using mixed-integer programming, metaheuristics, and attention-based deep reinforcement learning with a hybrid refinement approach.","ai_keywords":["Travelling Thief Problem with Drone","mixed-integer linear program","metaheuristics","attention-based Deep Reinforcement Learning","DRL policy","learner-initialised hybrid solver","annealing"],"ai_summary_model":"thinkingmachines/Inkling-Small","githubStars":3},"canReadDatabase":false,"canManagePapers":false,"canSubmit":false,"hasHfLevelAccess":false,"upvoted":false,"upvoters":[{"_id":"6856a5302e71b207b9704f48","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/6856a5302e71b207b9704f48/bWu5bG78A-QLPHp1BzOfk.jpeg","isPro":false,"fullname":"Kabir","user":"Murjani","type":"user"}],"acceptLanguages":["en"],"dailyPaperRank":0,"markdownContentUrl":"https://huggingface.co/buckets/huggingchat/papers-content/resolve/2608/2608.16435.md","query":{}}">
Drive, Pack, Fly: The Travelling Thief Problem with Drone
Published on Aug 17
· Submitted by Kabir on Aug 18 Abstract
The Travelling Thief Problem with Drone jointly optimizes ground routing, drone synchronization, and item selection to maximize profit, using mixed-integer programming, metaheuristics, and attention-based deep reinforcement learning with a hybrid refinement approach.
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.
Community
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.
Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.
Tap or paste here to upload images
Cite arxiv.org/abs/2608.16435 in a dataset README.md to link it from this page.
Cite arxiv.org/abs/2608.16435 in a Space README.md to link it from this page.
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.