Institute of Transportation, MOTC

       This study proposes an optimization model an algorithm to solve the scheduling problem of unmanned aerial vehicles (UAV) for meal delivery services. This problem considers a fixed size fleet of UAVs owned and operated by a chain restaurant . The UAVs pick up meals from the spe cified restaurants and deliver orders to customers within designed time windows. These restaurants a re also the bases for re placing the batteries for UAVs. This study applies the time space network flow technique to develop the optimal UAV scheduling model for meal delivery services. The model takes
into account the battery capacity constraint of UAVs and aims to minimize the total distribution cost. The proposed model is a multi depot vehicle scheduling problem, which is characterized as NP hard. In order to efficiently solve large problem instances, this study develops a math heuristic, network decomposition by drones, which integrates Gurobi solver to solve the decomposed sub problems. The model and the algorithm are examined and evaluated using the test instances generated based on
Solomon’s VRPTW benchmark instances. The heuristic is able to obtain good quality solutions in a reasonable amount of time. The differences between the objective valuesof the heuristic solutions and those of the lower bounds produced by Gurobi are less than 5% for all the test instances. The results show that the proposed model and the heuristic can be applied to solve the problem instances with practical sizes. The finding of this study can provide a reference on scheduling U AVs to operators who plan to use drones for meal delivery services.