Robust optimization for truck-and-drone collaboration with travel time uncertainties

Abstract

Truck-and-drone collaborations have shown great potential in reducing operational costs by fully utilizing the advantages of both trucks and drones. This study considers a Vehicle Routing Problem with Drones (VRPD) for delivery and surveillance tasks after disasters with travel time uncertainties. The trucks and drones can collaborate flexibly to complete all rescue tasks. Specifically, trucks can travel to other nodes after dispatching drones at a node. Each drone can perform multiple types of tasks at various nodes and return to a truck different from the one it originally took off from. In disaster response, trucks and drones often face uncertainty in travel times. To tackle this challenge, this paper develops a robust route optimization method for the proposed truck-and-drone collaborative system. We first formulate the problem as a min-max-min Mixed Integer Linear Programming (MILP) model. Then, we develop a Branch-and-Bound (BnB) algorithm integrated with the Benders Decomposition (BD) method and the Column-and-Constraint Generation (CCG) method. The BnB algorithm can get a better solution with a much smaller optimality gap, compared with the commercial solver Gurobi. Finally, we conduct extensive numerical studies to evaluate the proposed algorithm and test the benefits of robust routing. Numerical results show that the robust route can reduce the average cost by about 5 %, in contrast to the route without considering uncertainties. Sensitivity analysis is also carried out to compare different parameters in the uncertainty set and the truck-and-drone system.