  In the Traveling Salesman Problem with Drones (TSP-mD), a truck and multiple
drones cooperate to serve customers in the minimum amount of time. The drones
are launched and retrieved by the truck at customer locations, and each of
their flights must not consume more energy than allowed by their batteries.
Most problem settings in the literature restrict the feasible truck routes to
cycles, i.e., closed paths, which never visit a node more than once. Revisiting
a node, however, may lower the time required to serve all the customers.
Additionally, we observe that optimal solutions for the TSP-mD may retraverse
arcs, i.e., optimal truck routes may contain the same arcs multiple times. We
refer to such solutions as arc-retraversing, and include them in our solution
space by modeling the truck route as a closed walk. We describe Euclidean
instances where all the optimal solutions are arc-retraversing. The necessity
of arc retraversals does not seem to have been investigated in previous
studies, and those that allow node revisits seem to assume that there always
exists an optimal solution without arc retraversals. We prove that under
certain conditions, which are commonly met in the literature, this assumption
is correct. When these conditions are not met, however, excluding
arc-retraversing solutions might result in an increase of the optimal value; we
identify cases where a priori and a posteriori upper bounds hold on such
increase. Finally, we prove that there is no polynomial-time heuristic that can
approximate the metric TSP-mD within a constant factor, unless P=NP. We
identify a (non-constant) approximation factor explicitly when the truck can
visit all the nodes.
