A Branch-and-Price Algorithm for Robust Drone-Vehicle Routing Problem with Time Windows

This paper considers a cooperative routing problem in which trucks and multiple drones serve a set of customers collaboratively. A truck can operate as a drone station, dispatching and collecting multiple drones for nearby customers to overcome the drone’s short operation range. Each customer has a time window, so either a truck or a drone must serve the customer within the time window. The travel time uncertainties of the truck and drone are addressed by adopting the robust optimization approach. We first present a compact mathematical formulation for the problem. Then, we develop a decomposition approach based on the branch-and-price framework. After defining extended variables for trucks and drones separately, we decompose the column generation subproblem into two optimization problems, resulting in a two-phase column generation algorithm. We also develop a heuristic algorithm based on the proposed column generation scheme for larger instances. The results of numerical experiments, including real-life benchmark instances, show that the proposed algorithm outperforms the state-of-the-art mixed-integer programming solver. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Financial support from the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT & Future Planning [Grant NRF-2021R1F1A1 048540] is gratefully acknowledged. C. Lee was supported by the Hankuk University of Foreign Studies Research Fund. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0484 ), as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0484 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .