Truck–drone routing problem with stochastic demand

Truck–drone combination involves launch/retrieval of rotary-wing drones on trucks, which can address the issues of limited endurance and capacity of rotary-wing drones in delivery systems. Truck–drone combination technologies provide a compelling alternative to traditional emergency logistics systems that rely on on-ground transportation networks. Thus far, little research has been conducted on the truck–drone routing variant with stochastic demand, which is closely related to emergency logistics systems. Herein, we formally define the truck–drone routing problem with stochastic demand (TDRP-SD), which involves drones responding quickly to stochastic demands and restocking the supply. In particular, a new restocking policy, termed the truck–drone synchronized (TDS) restocking policy, is introduced to complement the traditional restocking operations that rely on ground vehicles. We analyze the characteristics of the introduced restocking policy and develop several propositions to address the computational burden caused by the dynamic programming computation of the expected cost. We propose a hybrid heuristic that combines the state-of-the-art Slack Induction by String Removals (SISRs) and greedy insertion utilizing blink rules. Several mechanisms, such as short-route deep search, lower-bound and upper-bound guiding, and simulated annealing, are adopted to ensure the algorithm performance. In computational experiments, the hybrid heuristic solves two types of benchmark instances and achieves new solutions. In addition, a collection of converted instances with up to 302 customers is effectively solved. The sensitivity analysis demonstrates the performance of the TDS restocking policy.