  Unmanned aerial vehicles or drones are becoming increasingly popular due to
their low cost and high mobility. In this paper we address the routing and
coordination of a drone-truck pairing where the drone travels to multiple
locations to perform specified observation tasks and rendezvous periodically
with the truck to swap its batteries. We refer to this as the Nested-Vehicle
Routing Problem (Nested-VRP) and develop a Mixed Integer Programming (MIP)
formulation with critical operational constraints, including drone battery
capacity and synchronization of both vehicles during scheduled rendezvous.
Given the NP-hard nature of the Nested-VRP, we propose an efficient
neighborhood search (NS) heuristic where we generate and improve on a good
initial solution (i.e., where the optimality gap is on average less than 6% in
large instances) by iteratively solving the Nested-VRP on a local scale. We
provide comparisons of both the MIP and NS heuristic methods with a relaxation
lower bound in the cases of small and large problem sizes, and present the
results of a computational study to show the effectiveness of the MIP model and
the efficiency of the NS heuristic, including for a real-life instance with 631
locations. We envision that this framework will facilitate the planning and
operations of combined drone-truck missions.
