A time–space network model for a truck and multi-drone delivery system with battery recharging and variable speeds

We present a multiperiod mixed-integer quadratic programming formulation based on a time–space network for a delivery problem with a mothership and a fleet of drones. The system is imagined as operating in European cities with high congestion, very narrow streets not reachable by trucks, no parking areas, but where customer demand is located. The mothership only stops at a set of locations where parking is possible, which are different from the customers’ locations. During mothership stops, deliveries are performed by drones that can fly at different speeds. The proposed formulation integrates the routing of the mothership and scheduling of the drone problems, also including the charging cycles of drone batteries. The optimization is performed by minimizing the total energy consumption (proportional to the distances traveled by the drones and truck) and by maximizing the number of customers served. The formulation is also exploited to design an effective matheuristic algorithm. A case study related to the city of Rome with up to 200 customers is presented to validate the model and illustrate the solution structure. Extensive computational results on a large testbed of artificial instances, up to 200 customers, are reported both for the formulation and the matheuristic algorithm.