  The idea of deploying electric vehicles and unmanned aerial vehicles (UAVs),
also known as drones, to perform "last-mile" delivery in logistics operations
has attracted increasing attention in the past few years. In this paper, we
propose the electric vehicle traveling salesman problem with drone (EVTSPD), in
which the electric vehicle (EV) and the drone perform delivery tasks
coordinately while the electric vehicle may need to visit charging stations
occasionally to recharge. We further assume that the EV can refresh its energy
to full battery capacity with fixed time at charging stations. Thus, the
proposed problem is termed EVTSPD-FF. In this paper, an arc-based mixed-integer
programming model defined in a multigraph is presented for EVTSPD-FF. An exact
branch-and-price (BP) algorithm and a variable neighborhood search heuristic
are developed to solve instances with up to 25 customers in one minute.
Numerical experiments show that the heuristic is much more efficient than
solving the arc-based model using the ILOG CPLEX solver and BP algorithm. A
real-world case study on the Austin network and the sensitivity analysis of
different parameters are also conducted and presented. The results indicate
that drone speed has a more significant effect on delivery time than the EV's
driving range.
