An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
Abstract
Rural last-mile logistics remains challenging because of sparse demand, limited road infrastructure, and long travel distances. We study a Truck-as-Hub Vehicle Routing Problem with Drones in Rural Areas, in which multiple trucks each carry a dedicated fleet of drones. Drone launch and retrieval are restricted to predesignated passive synchronization pads, where a visiting truck temporarily acts as a mobile hub, may dispatch multiple drones simultaneously, and must wait until all launched drones return before continuing its route. We formulate a mixed-integer quadratic programming model that jointly accounts for customer delivery delays, truck return times, and operating costs. To solve the problem exactly, we transform the original truck--drone network so that each feasible route can be represented as a single path and develop a branch-price-and-cut algorithm with tailored pricing, cutting, branching, and parallel-computing procedures. Computational experiments show that the proposed algorithm proves optimality for most large-scale test cases and achieves optimality gaps of no more than 4% for the remaining cases, whereas Gurobi reaches the 1,800-second time limit on all large-scale instances when applied directly to the compact formulation. Sensitivity analyses show that drone operating costs and managerial priorities substantially affect drone utilization and customer delays, providing practical guidance for balancing service quality and operating cost in rural delivery systems.
Related
- RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- Carbon-Aware Electric Vehicle Routing Problem with Decision-Focused Learning
- KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version
- An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem
BibTeX
@misc{pu2026exact,
title = {{An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones}},
author = {Fan Pu and Sivakumar Rathinam and Yunlong Zhang and Xiaopeng Li and Xiubin Wang and Yang Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15016},
eprint = {2610.15016},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15016},
}
RIS
TY - UNPB
TI - An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
AU - Fan Pu
AU - Sivakumar Rathinam
AU - Yunlong Zhang
AU - Xiaopeng Li
AU - Xiubin Wang
AU - Yang Zhou
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15016
UR - https://arxiv.org/abs/2610.15016
AB - Rural last-mile logistics remains challenging because of sparse demand, limited road infrastructure, and long travel distances. We study a Truck-as-Hub Vehicle Routing Problem with Drones in Rural Areas, in which multiple trucks each carry a dedicated fleet of drones. Drone launch and retrieval are restricted to predesignated passive synchronization pads, where a visiting truck temporarily acts as a mobile hub, may dispatch multiple drones simultaneously, and must wait until all launched drones return before continuing its route. We formulate a mixed-integer quadratic programming model that jointly accounts for customer delivery delays, truck return times, and operating costs. To solve the problem exactly, we transform the original truck--drone network so that each feasible route can be represented as a single path and develop a branch-price-and-cut algorithm with tailored pricing, cutting, branching, and parallel-computing procedures. Computational experiments show that the proposed algorithm proves optimality for most large-scale test cases and achieves optimality gaps of no more than 4% for the remaining cases, whereas Gurobi reaches the 1,800-second time limit on all large-scale instances when applied directly to the compact formulation. Sensitivity analyses show that drone operating costs and managerial priorities substantially affect drone utilization and customer delays, providing practical guidance for balancing service quality and operating cost in rural delivery systems.
ER -