  This paper presents a new approach for formulating the delivery problem by
drones with general energy consumption models where the drones visit a set of
places to deliver parcels to customers. Drones can perform multiple trips that
start and end at a central depot while visiting several customers along their
paths. The problem determines the routing and scheduling decisions of the
drones in order to minimize the total transportation cost of serving customers.
For the first time, the new formulation approach enables us to use the best
available energy consumption model without the need of any extra
approximations. Though the approach works in a very general setting including
non-convex energy consumption models, it is also computationally efficient as
the resulting optimization model has a linear relaxation. A numerical study on
255 benchmark instances with up to 50 customers and a specific energy function
indicate that all the instances can be solved 20 times faster on average using
the new formulation when compared to the best existing branch-and-cut
algorithm. All the 15 benchmark instances with 50 customers are solved exactly,
whereas none of them has been solved optimally before. Moreover, new instances
with up to 150 customers are solved with small error bounds within a few hours.
The new approach can be simply applied to consider the extra energy required
when a drone needs to continue hovering until opening the delivery time window.
It can also be applied to the case where the flight time is dependent on the
drone's payload weight. Owing to the flexibility of the new approach, these
challenging extensions are formulated as linear optimization models for the
first time.
