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.